www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Speicher durchsuchen


Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Doom (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Baitronic (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: mh789 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: mh789 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Marco S. (masterof)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
abo

Autor: remo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.