Hallo, ich lege GPS-Daten unter anderem auch das Datum in einem seriellen Flash (1MB)ab. Beim einschalten durchsuche ich den Speicher nach all seinen verschiedenen abgespeicherten Tagen. Also vergleiche 1.Datum mit 2.Datum... bis ein anderes Datum ausgelesen wird usw. Am Schluss habe ich dann alle Datums. Um das ganze zu beschleunigen mach ich immer Sprünge mit 100 Sätzen, vergleiche wenn Datum gleich wieder Sprung mit 100 sonst zurück und mit Sprung 1 weitersuchen. Ich hoffe das war einigermasen verständlich. Hat jemand eine schnellere Suchroutine? Gruß Michael
Hi, versuche es doch mal so: erst sucht Du in 100er-Schritten. Wenn sich das Datum geändert hat, gehst Du 50 zurück. Wenn sich das Datum jetzt wieder geändert hat, gehst Du 25 vorwärts, sonst nochmal 25 zurück. So gehst Du dann in immer kleiner werdenden Schritten immer weiter auf den Datumswechselpunkt zu.
Ich hätte spontan gesagt binäre suche, allerdings wirst du nicht umhin kommen linear den ganzen Speicher zu durchsuchen, da du ja nicht direkt ein bestimmtes Datum suchst... VIelleicht kannst du ja schon beim beschreiben des flashs zwischen den einzelnen Tagen einen "Stopper" setzen. Hilft aber wahrscheinlich auch nicht viel... Gruß Andreas
Oder du baust eine zweite Tabelle auf. Diese enthält die Positionen in die erste Tabelle an der ein Datumswechsel stattfand. Dh. diese zweite Tabelle kannst du als Index benutzen. Andererseits vermute ich mal das du kontinuierlich zb. alle 15 Minuten einen GPS Datensatz abspeicherst. Es wäre dann durchaus sinnvoll das so immer die gleiche Anzahl an Datensätzen pro Tag gesammelt werden, zb. eben 1440 / 15 = 96 Datensätze pro Tag. Dann brauchst du garnicht mehr suchen, sondern musst nur sicherstellen das immer 96 Datenstätze pro Tag an Speicher verbraucht wird. Gruß Hagen
Hier mein Versuch. Unter den Annahme, dass die Längen der einzelnen Tage ungefähr gleich lang sind. Man startet mit einer gut geschätzten Tageslänge (z. B. 100). Zunächst liest man das erste Datum. Dann das Datum an der Position 0 + Tageslänge. Eine binäre Suche würde ich nun nicht machen, weil man ja schon relativ nahe am Ziel ist. Ist man noch beim aktuellen Datum, dann sucht man in größer werdenden Schritten (+4, +8, +16, +32, ...), bis sich das Datum ändert. Ist man dagegen schon beim nächsten Datum, sucht man mit der gleichen Methode in die andere Richtung (-4, -8, -16, -32, ...). Irgendwann hat man einen Bereich, in dem sich die Datumsgrenze befinden muss. Also die höchste Speicherstelle, die man mit dem alten Datum gelesen hat und und die kleinste Speicherstelle mit dem nächsten Datum. In diesem Bereich macht man jetzt einfach eine binäre Suche (also immer in der Mitte nachschauen, wie schonmal erklärt). (Ein bisschen Gehirnschmalz muss man noch für die Fälle gebrauchen, falls die beiden oben gefundenen Daten nicht aufeinanderfolgen. In diesem Fall sucht man einfach binär nach einer Datumsgrenze und wiederholt die Suche in den verbleibenden Bereichen, in denen sich noch andere Datensprünge befinden könnten. - Oder man spart sich den Programmieraufwand und parst diesen kleinen Teil einfach linear durch.) Gut, dachdem man nun die genaue Grenze gefunden hat, bereichnet man die Länge des soeben ermittelten Tages und nimmt an, dass am nächsten Tag ungefähr genausoviele Daten abgelegt wurden. Man springt um diese Größe nach vorn und beginnt wieder mit der Suche in größer werdenden Schritten.
@mh789: dein Vorschlag hat einen Hacken. Du gehst davon aus das circa 100 Datensätze pro Tag vorhanden sind. Rechne doch mal mit 100 Tagen und pro tag mit nur 99 Datensätzen, statt 100. Bei der Suche nach dem 98'ten tag kommst du bei deiner Suche in den 100'ten Tag rein. Sogesehen wäre es dann schon wieder besser einfach über die komplette Tabelle per Binärer Suche zu suchen. Bei 1024 Datensätzen sind das dann nur 11 Zugriffe und bei 65535 nur 16 Zugriffe auf diese nach Zeiten sortierte Tabelle um jeden beliebigen Tag zu finden. Also entweder gleich eine reine binäre Suche verwenden oder aber mit einer zweiten Tabelle als Index arbeiten. Gruß Hagen
> dein Vorschlag hat einen Hacken. Du gehst davon aus das circa 100 > Datensätze pro Tag vorhanden sind. Rechne doch mal mit 100 Tagen und > pro tag mit nur 99 Datensätzen, statt 100. Bei der Suche nach dem > 98'ten tag kommst du bei deiner Suche in den 100'ten Tag rein. Wieso? Wenn ich den 97. Tag habe und dann die Länge dieses Tages dranhänge, dann bin ich doch "spot-on". Ich glaube, Du hast mich da missverstanden. Die 100 wird ja nur einmal für die länge des ersten Tages angenommen. Außerdem suche ich immer ab dem letzten gefundenen Datumswechsel. Außerdem würde es gar nichts ausmachen, wenn ich mal einen Tag überspringe (weil z. B. ein "Feiertag" drin war). Der Algorithmus fängt sich ja wieder.
Die schnellste Methode ist sicherlich schon beim Abspeichern der Werte des ersten Eintrags eines Tages, den eigenen Index in den ersten Eintrag des Tages davor einzutragen. Das kostet zwar etwas mehr speicher, aber man kann die Liste beim Einschalten ganz ohne suchen aufbauen indem man sich an den Indizes entlanghangelt. ciao Remo
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.