Der Mamimumsalgorithmus

[mathemanu]

Hey Leute,

ich habe für ein Praktikum einen Algorithmus anzufertigen und der ist auch schon fast fertig. Jetzt habe ich nur noch ein Problem. Ich habe eine Datendatei und einen Suchalgorythmus, der mir die ganzen lokalen Maxima ausspucken soll. Da viele Messwerte (besonders bei den Minima und den Maxima) mehrfach vorkommen, habe ich eine Genauigkeit eingebaut.

Der mit meinen bescheidenen Informatikkentnissen programmierte Algorythmus findet mir aber keine Maxima und gibt ganz komisches Zeug aus. kmax[] ist das Array, in dem ich die Stelle des Maximas in beidemessungen[][0] speichern will. Könnt ihr mir sagen, was da schiefläuft?

float max[50];

int kmax[50];

int i=0;


for(int k=1;k<10000;k++)

{

if (beidemessungen[k-1][0]<beidemessungen[k][0])

{

for(int g=genau;g>0;g--)

{

if (beidemessungen[k][0]>=beidemessungen[k+g][0]){;}

else

goto raus;

}


max[i]=beidemessungen[k][0];

kmax[i]=k;

i++;


}

raus: ;

}

MfG Manu

[mathemanu]

Habe eben nochmal ein wenig geschaut.

Das Problem ist der Laufindex i. Ich schreibe einfach sehr oft in max[50]. Wesentlcih öfter als ich möchte. Da sollen ja nur die "echten" Maxima drinstehen, da stehen aber auch noch alle anderen Zahlen drin, die die if-Bedingung

if (beidemessungen[k-1][0]<beidemessungen[k][0])

erfüllen.

Kann mir da jemand helfen?

Manu

[TDM]

da stehen aber auch noch alle anderen Zahlen drin, die die if-Bedingung

if (beidemessungen[k-1][0]<beidemessungen[k][0])

erfüllen.

Sowas wie -21053478...wasweißich?

Könnte daran liegen, weil du dein Array deklarierst, aber nicht initialisierst.

Außerdem würd ich mir goto gar nicht erst angewöhnen.

[mathemanu]

Wenn ich mein Array deklariere, aber nciht initialisiere, steht dann nicht automatisch erstmal 0 in jedem Eintrag?

Gruß Manu

[TDM]

C++ Notes: Array Initialization

If an array has no initialization, the values are undefined.

-> Nein.

(hmm, Punkt 4 klingt interessant.)

[mathemanu]

aber wenn ich ein array teilinitialisiere, dann klappt das? hab ich in nem c++ heft gelesen. also sowas hier:

float array[20]={1,3}

dann ist doch

array[0]=1

arrray[1]=3

array=0 ; 1<i<20

oder?

Manu

[mathemanu]

Außerdem ist das auch nicht Kern meiner Frage. Spätestens wenn ich was in das Array reinschreibe habe ich es doch initialisiert und dann sollten doch auch meine Werte drinstehen, oder?

Manu

PS: Selber lesen macht schlau. Damit hat sich meine Frage nach der Teilinitialisierung auch erledigt.

[TDM]

Spätestens wenn ich was in das Array reinschreibe habe ich es doch initialisiert und dann sollten doch auch meine Werte drinstehen, oder?

Nein, dann hast du undefinierte Werte verändert.

Unter Initialisierung (vgl. engl. to initialize) versteht man in der Programmierung die Zuweisung eines Initial- oder Anfangswertes zu einem Objekt oder einer beliebigen Variablen im Quellcode.

(Damit wir uns nicht falsch verstehen: Deine Werte stehen drin, aber wenn du Wert[0] änderst wird folglich nicht Wert[49] auf 0 gesetzt.)

[mathemanu]

Ok. Ich hab es jetzt natürlich mit

 float max[50]={0};

versucht, denn dann habe ich ja alle Werte in dem Array auf Null. Die gibt er mir auch raus (wenn ich i++ weglasse). Das Löst mein Problem aber nicht, dass er mir für alle außer den ersten Eintrag im Array max immer 1.29349e-42 rausspuckt.

Manu

[FinalFantasy]

 float max[50]={0};

versucht, denn dann habe ich ja alle Werte in dem Array auf Null. Die gibt er mir auch raus (wenn ich i++ weglasse). Das Löst mein Problem aber nicht, dass er mir für alle außer den ersten Eintrag im Array max immer 1.29349e-42 rausspuckt.

Das liegt daran, weil du damit auch nur den ersten Wert, also max[0] auf 0 setzt, den Rest aber uninitialisiert lässt.

Du musst schon jeden Wert initialisieren, z.B. mit einer for-Schleife über alle 50 Werte gehen und JEDEN einzelnen Wert erstmal auf 0 setzen.

[TDM]

Das liegt daran, weil du damit auch nur den ersten Wert, also max[0] auf 0 setzt, den Rest aber uninitialisiert lässt.

Dann geht das hier wohl doch nicht?!

[FinalFantasy]

Soweit ich weiß geht das nicht. Dürfte durch den Quellcode hier ja auch bewiesen sein, dass es nicht geht.

Pures C(++) intitialisiert afaik gar nichts, wenn man es nicht selbst tut.

Ausnahmen:

- bei der Verwendung von String/Array Klassen, z.B. STL oder von anderen Frameworks, werden diese für gewöhnlich vom Constructor dieser Klasse initialisiert, falls man nichts angibt.

- Es ist kompilerabhängig, manche Kompiler initialisieren im Debug Build die Variablen mit speziellen Werten (was aber seltenst 0 ist), deswegen steht bei dir vermutlich auch in jedem Feld immer die gleiche Zahl drin. Darauf sollte man sich aber keinesfalls verlassen, sobald man einen Releasebuild verwendet kann dann alles wieder ganz anders aussehen.

[mathemanu]

Hey Leute,

ich habe es natürlich auch mit der Initialisierung des ganzen Arrays probiert. Ist aber auch Käse.

Manu

PS: Das die restlichen Array-Werte bei der Initialisierung eines einzigen Array-Eintrags auf Null gesetzt werden ist Fakt. Ich hab mir das Array mal komplett ausgeben lassen und es standen dann überall Nullen drin!

[FinalFantasy]

versucht, denn dann habe ich ja alle Werte in dem Array auf Null. Die gibt er mir auch raus (wenn ich i++ weglasse). Das Löst mein Problem aber nicht, dass er mir für alle außer den ersten Eintrag im Array max immer 1.29349e-42 rausspuckt.

PS: Das die restlichen Array-Werte bei der Initialisierung eines einzigen Array-Eintrags auf Null gesetzt werden ist Fakt. Ich hab mir das Array mal komplett ausgeben lassen und es standen dann überall Nullen drin!

Ja was denn nun? Beides gleichzeitig ist ja wohl schlecht möglich. Wenn dein Array so initialisiert wird, müsste dein Problem ja gelöst sein, oder?

ich habe es natürlich auch mit der Initialisierung des ganzen Arrays probiert. Ist aber auch Käse.

Wieso sollte das Käse sein?

Edit: Habs jetzt schnell mal ausprobiert: array[10] = {0} initialisiert tatsächlich das ganze Array. Deswegen kam mir jetzt eine Idee. Ich hab mir jetzt deine Algorithmus nicht haarklein angesehen, aber lass die mal die Indices ausgeben... läufst du an den Stellen wo du diese 1.29349e-42 rauskriegst vielleicht über die Arraygrenzen hinaus? Wenn ich mir deine Indexrechnerei so ansehe, kann ich mir das sehr gut vorstellen.

Bearbeitet 30. Juli 2010 von FinalFantasy

[mathemanu]

Also nochmal ne ordentliche Problembeschreibung:

Ich habe den ganz oben angegebenen Quellcode benutzt. Damit wird mir immer diese 1.29349e-42 rausspuckt.

Dann habe ich den Laufindex i weggelassen (damit wird natürlich nur der erste Eintrag des Arrays beschrieben, also max[0]) und er hat mir in den ersten Eintrag die richtigen Werte geschrieben.

Mein eigentlcihes Problem ist folgendes: Ich suche ja mehr als ein Maxima (Ich suche 50) und die will ich alle nacheinander in das Array schreiben. Ich frage mich nur warum das mit der Einführung von

i++;

dann auf einmal so furchtbar schief läuft.

Gruß Manu

[FinalFantasy]

Dazu dann erstmal folgende Fragen:

Was ist denn "beidemessungen"? Aus deinem Code schliesse ich, dass es ein zweidimensionales Array ist, habe aber keine Ahnung, wie groß es sein soll. In deiner Schleife gehst du ja mal pauschal von 10000 aus. Grenzen fragst du nirgends ab.

Wieso greiffst du immer auf 0 als zweiten Index zu (beidemessungen[k][0])? Ist das Array wirklich zweidimensional, ignorierst du einfach nur den Rest oder ist hier generell etwas falsch?

Was ist denn "genau"? Du benutzt es als Startwert für deine zweite Schleife, es ist aber nirgends definiert. Folglich kann ich auch nicht sagen, ob dein Indexzugriff mit "k+g" irgendwann mal ins Leere geht.

i zählst du unten hoch, ohne jegliche Grenzprüfung. Ich bin mir ziemlich sicher, dass du hier irgendwann mal in nicht reservierten Speicher schreiben wirst.

Ausserdem:

if (beidemessungen[k][0]>=beidemessungen[k+g][0]){;}

Diese If-Abfrage tut also mal genau garnichts? Sieht mir auch nicht nach Absicht aus.

Geh deinen Algorithmus nochmal durch und überlege dir genau, mit welchen Indices du wo was genau tust. Ich bin mir ziemlich sicher, dass hier der Fehler begraben liegt.

Ansonsten, falls dein realer Code genauso aussieht wie dein geposteter: Gewöhn dir mal an den Code einzurücken. Das macht ihn nicht nur leserlicher, sondern lässt auch so manchen Fehler leichter erkennen.

[mathemanu]

Erstens: genau ist ein int-Wert, der eine Genauigkeit angibt (in meinem Beispiel ist er 24).

Zweitens: beidemessungen [][] ist ein zweidimensionales Array, aus dem ich nachher noch mehr Daten auslesen will im Beispiel sind es jetzt nur 2 Messungen, also gibt es beidemessungen[][0] und beidemessungen[][1].

Drittens: Bei i werd ich mal schauen.

Ich werd an das Einrücken denken.

Vielen Dank. Wenn ich dann immer noch nicht weiter komme melde ich mich hier nochmal.

Manu

[flashpixx]

Zweitens: beidemessungen [][] ist ein zweidimensionales Array, aus dem ich nachher noch mehr Daten auslesen will im Beispiel sind es jetzt nur 2 Messungen, also gibt es beidemessungen[][0] und beidemessungen[][1].

Dein Algorithmus wird sehr aufwändig, wenn Du k Messungen betrachtest dann hast Du O(i*k) Durchläufe, d.h. quadratischer Aufwand. Du solltest Dir etwas besseres einfallen lassen

[FinalFantasy]

Dein Algorithmus wird sehr aufwändig, wenn Du k Messungen betrachtest dann hast Du O(i*k) Durchläufe, d.h. quadratischer Aufwand. Du solltest Dir etwas besseres einfallen lassen

Ich glaube, er ist erstmal ganz froh, wenn es überhaupt mal, wenn auch langsam funktioniert.

[flashpixx]

@FinalFantasy: Das ist ein kleiner Seitenhieb gewesen. Ich wollte ja nur die Anmerkung bezüglich Deiner "In deiner Schleife gehst du ja mal pauschal von 10000 aus"