Logik-Problem (Periodische Wiederholung von Werten in einem Array erkennen)

hmmka

Hallo Leute, brauche dringend einen kleinen Denkanstoß.
Ich überlege schon seit Tagen wie ich dieses Problem lösen kann und komme einfach nicht weiter, ist mir schon etwas peinlich!

Es geht um folgendes:

Ein Array wird mit CRC-Prüfsummen gefüllt. Dabei kann es auftreten, dass nach einiger Zeit eine Periodische Wiederholung eintritt. Dieses soll durch das Programm festgestellt werden.
Eigentlich ganz einfach, das Problem ist, das auch die Periodenlänge berechnet werden soll. Das wird insofern zum Problem, da immer der älteste Wert im Array überschrieben werden soll. D.h. das in dem Beispielarray[10] die ersten 10 CRC-Werte im Array an Stelle 0-9 gespeichert werden.
der 11. Wert geht dann im Array wieder an Stelle 0, der 12. Wert an Stelle 1 usw, der älteste Wert wird also immer überschrieben. Ich weiß jetzt nicht wie ich die Periodenlänge berechnen kann, ohne dass es zu unschönen Effekten kommt.

So stelle ich zurZeit fest ob es überhaupt eine Wiederholung gibt:

for (i = 0; i < 10; i++)
	for (j = 0; j < 10; j++)
		if (CRC32[i] == CRC32[j] && j != i && CRC32[i] != 0) {
				ZyklusErkannt = 1; /* Variable die nur besagt das es eine Wiederholung gibt */
				Periodenlaenge = j-i; /* Hier muss irgendwie erkannt werden wo die Periodische Wiederholung beginnt, bzw. ob j das (in zeitlicher Reihenfolge) erste oder zweite Vorkommen dieses Wertes ist!! */
                }

Beispiel wo dieser Code eine falsche Periodenlänge berechnet:

Werte die nach und nach in das Array geschrieben werden würden:

CRC1
CRC2
CRC3
CRC4
CRC5
CRC6
CRC7
CRC8
CRC9
CRC10
CRC8
CRC9
CRC10
CRC8
CRC9
...
Nach dem ersten Durchgang hätte das Array folgenden Inhalt und jetzt würde erstmals die Schleife aufgerufen werden die auf Wiederholung testet:
CRC1
0
0
0
0
0
0
0
0
0
0

Beim zweiten Durchgang, jetzt würde zum zweiten mal die Test-Schleife drüberlaufen:
CRC1
CRC2
0
0
0
0
0
0
0
0

Im zehnten Durchgang ständ dann folgendes im Array:
CRC1
CRC2
CRC3
CRC4
CRC5
CRC6
CRC7
CRC8
CRC9
CRC10

11. Durchgang bei dem die Periode von der Test-Schleife erkannt werden würde:
CRC8
CRC2
CRC3
CRC4
CRC5
CRC6
CRC7
CRC8
CRC9
CRC10

Hier würde jetzt statt der korrekten Periodenlänge (3) eine falsche Länge von 7 berechnet werden! Das richtige Ergebnis würde ich hier bekommen wenn ich nicht j-i sondern 10-j (=Arraygröße - j) rechnen würde! Nur wie kann ich das hier feststellen das in der Periode ein Umbruch stattgefunden hat und somit das Indexmäßig erste Vorkommen des Wertes im Array Zeitlich eigentlich das zweite und nicht das erste Vorkommen ist??

Die einzige Lösung die mir eingefallen ist die auch wirklich funktioniert wäre halt immer das erste Element des Arrays zu löschen um dann alle anderen Elemente um einen Index nach vorn zu verschieben. So würde die korrekte Reihenfolge immer beibehalten werden. Das kann ich jedoch leider nicht machen, da es halt Vorgabe ist das der 11. Wert an Stelle Null, der 12. Wert an Stelle 1 und so weiter gespeichert wird und es wohl ausserdem erheblich langsamer wäre wenn man alle Arraywerte durchgehen und um einen Index verschieben muss, da die Arraygröße nach dem Debuggen auf X-Tausend angehoben wird!
Trotzdem muss IMMER die richtige Periodenlänge erkannt werden, da eine Wiederholung auch erst nach tausenden Durchgängen auftreten kann und somit diese Problematik trotzdem bestehen bleit!
Bin echt langsam ratlos wie man das Problem angehen kann!

Vielleicht hat ja jemand von euch einen Tipp was hier zu tun ist?

Liebe Grüße

redrew99

Man könnte ein zweites Array anlegen und dann die beiden miteinander vergleichen.
Die Länge einer Periode könnte man dann ermitteln, indem man einen Zähler zuschaltet, sobald zwei Werte gleich sind und ihn wieder ausschaltet, wenn die Werte ungleich sind.

hmmka

Hallo,

danke für diesen wirklich guten Hinweis. Hab die ganze Zeit versucht das Problem innerhalb des einen Arrays zu lösen, darauf ein zweites Array zum Vergleichen zu erstellen bin ich garnicht gekommen
Werde das Programm im Laufe des Tages mal umbauen und sehen was sich machen lässt.
Theoretisch brauche ich dann nichtmal einen Zähler um die Periodenlänge festzustellen, da ich mithilfe des Kontrollarrays ja ganz leicht feststellen kann, welcher der beiden identischen Werte zuerst aufgetreten ist, indem ich das Kontrollarray immer eine Generation hinterherhängen lasse. Die Position an welcher der Wert dann in beiden Arrays vorkommt ist dann der Start der Periode. Die Länge sollte man mithilfe dieser Informationen einfach berechnen können!

LG

volkard

Das war kein so guter Tipp.
Anhand der aktuellen Schreib-Position kannste sehr wohl checken, ob i und j auf der selben Seite liegen oder ob sie auf unterschiedlichen Seiten liegen.
Aber sicherlich ist bereits der Ansatz mit den 10 Array-Elementen fraglich, doch leider wissen wir nicht, was Du machen willst.

hmmka

Warum bin ich denn nicht darauf gekommen die aktuelle Schreibposition zu nutzen um die Start/Endposition der Periode zu bestimmen.....
Das erspart mir natürlich das ganze Gehampel mit dem zusätzlichen Kontroll-Array, was jedoch nach ersten Tests auch super funktioniert hat...

Den Ansatz mit dem Array generell kann ich nicht ändern, da es eine (eigentlich fast die einzige) Vorgabe zu dieser Aufgabe ist. Es sind aber natürlich keine 10 Elemente, sondern wird auf 1000 oder mehr erweitert. Es kann jedoch vorkommen das eine Periodische Wiederholung erst so spät auftritt, dass das Problem immer noch zum tragen kommen würde!

Edit: Vielen Dank an volkard, der Tipp war wirklich Gold wert!!!
Mithilfe der Schreibposition war es Problemlos möglich die Periodenlänge zu berechnen!

volkard

hmmka schrieb:

Den Ansatz mit dem Array generell kann ich nicht ändern, da es eine (eigentlich fast die einzige) Vorgabe zu dieser Aufgabe ist.

Konkret die Vorgabe, daß ein Array verwendet werden muß, oder nur, daß mit den letzten 1000 Werten verglichen und ein Zyklus gesucht werden muß? Und kommt's auf Laufzeit an, oder ist die eher egal, Hauptsache es geht überhaupt?

Außerdem brauchst Du bei jeder Einfügung nicht gleich jeden gegen jeden zu vergleichen, sondern es reicht, jeden gegen den Neuen zu vergleichen.

for (i = 0; i < 10; i++)
    for (j = 0; j < 10; j++)
        if (CRC32[i] == CRC32[j] && j != i && CRC32[i] != 0) {
                ZyklusErkannt = 1; /* Variable die nur besagt das es eine Wiederholung gibt */
                Periodenlaenge = j-i; /* Hier muss irgendwie erkannt werden wo die Periodische Wiederholung beginnt, bzw. ob j das (in zeitlicher Reihenfolge) erste oder zweite Vorkommen dieses Wertes ist!! */
                }

zu machen, sondern kannst

//natürlich ungetestet. :)
int i=schreibPos;
do{
   if(CRC32[i]==neueCRC32)
      return (i+arrSize-schreibPos)%arrSize+1;
   i=(i+1)%arrSize;
}while(i!=schreibPos)

volkard

Oder keinen Ringpuffer machen, da Du eh pro Einfügung ganz durchlaufen musst. Da kann man das Bißchen an Mehrkosten auch zahlen, das Array immer rutschen zu lassen.

hmmka

volkard schrieb:

Konkret die Vorgabe, daß ein Array verwendet werden muß, oder nur, daß mit den letzten 1000 Werten verglichen und ein Zyklus gesucht werden muß? Und kommt's auf Laufzeit an, oder ist die eher egal, Hauptsache es geht überhaupt?

Die Vorgabe lautet wortwörtlich: "Vorgabe für die Implementierung: Sie sollen eine Funktion schreiben die eine CRC32-Prüfsumme über das gesamte Spielfeld berechnet.
Die Prüfsummen werden zyklisch in einem Array gespeichert. Das bedeutet Sie müssen den aktuellen Index verwalten, so dass der neue Wert den ältesten überschreibt.
Beispiel: Ihr Array hat die Größe 10: Dann wird die Prüfsumme der ersten Generation mit dem Index 0 gespeichert, die zweite Generation mit Index 1 etc. bis zur Prüfsumme der zehnten Generation mit Index 9, elften Generation mit INdex 0 (erstes Überschreiben), zwöfte Generation mit Index 1 etc.. Die Festlegung der Arraygröße soll aber mit einer definierten Konstanten geschehen. Einen Zyklus erkennen Sie nun daran, dass eine Prüfsumme bereits im Array vorhanden ist."

volkard schrieb:

Außerdem brauchst Du bei jeder Einfügung nicht gleich jeden gegen jeden zu vergleichen, sondern es reicht, jeden gegen den Neuen zu vergleichen.

for (i = 0; i < 10; i++)
    for (j = 0; j < 10; j++)
        if (CRC32[i] == CRC32[j] && j != i && CRC32[i] != 0) {
                ZyklusErkannt = 1; /* Variable die nur besagt das es eine Wiederholung gibt */
                Periodenlaenge = j-i; /* Hier muss irgendwie erkannt werden wo die Periodische Wiederholung beginnt, bzw. ob j das (in zeitlicher Reihenfolge) erste oder zweite Vorkommen dieses Wertes ist!! */
                }

zu machen, sondern kannst

//natürlich ungetestet. :)
int i=schreibPos;
do{
   if(CRC32[i]==neueCRC32)
      return (i+arrSize-schreibPos)%arrSize+1;
   i=(i+1)%arrSize;
}while(i!=schreibPos)

Ja, man kann das ganze noch stark beschleunigen, daran wollte ich mich jetzt machen nachdem die Funktionalität erstmal gegeben ist.
Deine Beispielrechnung sieht ja sehr interessant aus, aber da muss ich gleich in Ruhe mal hintersteigen, ist schon etwas komplizierter für mich!
Ich muss ja eigentlich einfach nurnoch alle Werte gegen den neuesten Prüfen, und kann dann die Periodenlänge berechnen (mit einer unterschiedlichen Formel jenachdem ob (schreibPos > i) oder (schreibPos < i)

for (i = 0; i < MAXZYKLUS; i++)
			if (CRC32[i] == CRC32[crcPos] && crcPos != i && CRC32[i] != 0) {
				ZyklusErkannt = generation;

				if (crcPos > i) {
					Periodenlaenge = crcPos - i;
				} else {
					for (j = (MAXZYKLUS - 1); j > 0; j--)
						if (CRC32[j] == CRC32[i]) {
							Periodenlaenge  = (MAXZYKLUS - 1) - j + (crcPos - 1);
						}
				}
				return;
			}
	return;

Werde gleich mal genauer testen ob denn die Länge immer richtig berechnet wird!

volkard schrieb:

Oder keinen Ringpuffer machen, da Du eh pro Einfügung ganz durchlaufen musst. Da kann man das Bißchen an Mehrkosten auch zahlen, das Array immer rutschen zu lassen.

Das war ja auch meine erste Überlegung, aber da die Aufgabe nunmal explizit so formuliert ist muss ich mich ja wohl daran halten

craiten

Moin moin hmmka,

ich glaube wir sind in der gleichen fachschaft
bist du mit dem problem schon wieter gekommen? bei mir ist das wissen darüber, wie man die prüfsumme bildet noch sehr dunkel gehalten.