Suche effizienten Algorithmus für Berechnung von Abständen
-
Hi
Ich habe eine sehr lange Abfolge verschiedener Zahlen. Beispielsweise
1 2 3 2 3 5 4 1 3 3 1Was ich möchte ist folgendes:
Über alle Zahlen der Liste soll folgendes Berechnet werden:
- die Anzahl der verschiedenen Zahlen zwischen zwei gleichen Zahlen.Im Beispiel wären das folgende Ergebnisse:
- zwischen der ersten und zweiten 3: 1
- zwischen der ersten und zweiten 2: 1
- zwischen der ersten und zweiten 1: 4
- zwischen der vorletzten und letzten 3: 0
- zwischen der vorletzten und drittletzten 3: 3Ein naiver Ansatz ist, die Liste der Zahlen solange rückwärts zu durchlaufen, bis man die gesuchte Zahl erneut findet. Das ist aber (bei großen Abständen zwischen den Zahlen, 1000 ist ein normaler Wert in meinem Anwandungsfall) ziemlich zeitaufwändig.
Hat jemand von euch da eine Idee, wie es effizienter geht ?
Ich danke euch !
-
Es gibt 10 Zahlen die du untersuchen musst.
0-9Da "merkst" du dir wo (die 1.Stelle) die Zahl zum ersten mal auftaucht und wenn sie dann nochmal kommt -> Abstand = 2.Stelle - 1.Stelle -1 dann machst du die 1.Stelle = 2.Stelle und suchst weiter.
Das für alle 10 Zahlen. So musst du die ganze reihe auch nur einmal durchlaufen.Daraus dürfte man leicht einen Algorithmus basteln können.
Ist jetzt nur ein kurzer Ansatz. Vll. gibts auch bessere.
-
Die Länge der Liste ist unbestimmt und liegt zwischen 10^6 und 10^9.
Die Menge der Zahlen ist unbestimmt. Schwankt zwischen 10^3 und 10^8
Ferner berechnet dein Algorithmus den Abstand nicht korrekt, da doppelt vorkommende Zahlen nur einfach gezählt werden sollen.
Danke trotzdem !
-
Benja_m schrieb:
Die Länge der Liste ist unbestimmt und liegt zwischen 10^6 und 10^9.
Die Menge der Zahlen ist unbestimmt. Schwankt zwischen 10^3 und 10^8
Ferner berechnet dein Algorithmus den Abstand nicht korrekt, da doppelt vorkommende Zahlen nur einfach gezählt werden sollen.
Danke trotzdem !
Du wirst um eine Laufzeit kleiner O(n) eh nicht rumkommen, also denk ich ist Strom's Grundidee gar nicht mal falsch. Nur "merkst" du dir den 2ten Wert einer Zahl gar nicht (sondern speicherst von mir aus die gefundenen Werte in einer separaten Liste), sondern erst wieder den 3ten.
Was mir spontan sonst noch einfaellt: Du speicherst dir fuer jede Zahl den Wert der Zahl sowie ihre Position in der Uriste. Dann sortierst du die Uriste mit einem stabilen Algorithmus (z. B. Mergesort). Anschliessend hast du die erste 1 gleich vor der 2ten. Dann kommt (falls vorhanden) die dritte 1, dann die vierte... Damit kannst du die Abstaende sehr leicht berechnen. Das Verfahren laeuft halt in O(n * log(n)), weshalb ich eher zu Storm's Idee raten wuerde.