AW: Wo binäre Suche schneller, mit Array oder StringList?
@AlexII
Hatte ähnliche Aufgabe auch mal, daher kann ich dir sagen: wer beizeiten richtig sortiert, hat später weniger zu suchen. Oder anders ausgedrückt, es ist einfacher (schneller) wenn du die Termine zuerst sortierst und dann suchst, als eine unsortierte Liste jedes Mal komplett durchzusuchen. Ist eine Liste Sortiert, kannst du dir eine Adresse merken, die alte und zukünftige Termine trennt. Das nächste Mal kannst du mit der Suche ab dieser Adresse anfangen. Natürlich mit der Suche aufhören wenn der Termin in der Zukunft liegt. Letztendlich bleiben dir nur eine Handvoll Daten die du durchsuchen musst. Also, besser zuerst sortieren als später suchen. Was die TStringList angeht, kann es sein, dass die Frage lautet: was ist schneller, Array mit TDateTime oder StringList mit einer Datumzeit als String? Da möchte ich dir TObjectList ans Herz legen. Muss man zwar eine kleine Klasse basteln, aber dafür bringt sie paar Vorteile. |
AW: Wo binäre Suche schneller, mit Array oder StringList?
Index: jede Datenbank sollte einen Index auf das/die Felde(r) haben in denen gesucht wird.
Die Abfrage nach den sekundengenauen Terminen, könnte etwas eng werden, da der Komunikationsoverhead etwas groß wird. Daher vllt. alle 10 sec die Daten der nächsten 10 sec holen. Hat natürlich den Nachteil, daß Termine, die zum Abfragezeitpunkt<Eintragungszeitpunkt<Abfragezeitp unkt+10sec eingetragen werden "verschwinden". Darum solltest Du vllt. erst einmal den Worst case deiner Anwendung definieren, und dann zusehen, das Du diesen beherrschst. Gruß K-H P.S. Ob Tlist,TObjectlist oder Array, diese Diskussion halte ich jetzt eigentlich für zweitrangig. |
AW: Wo binäre Suche schneller, mit Array oder StringList?
Zitat:
Du brauchst außerdeme ein minimale Reaktionszeit t für die Routine, um deinen Worstcase von tausenden Weckzeiten abzufackeln. Und Du brauchst eine Entscheidung, was mit timed out Weckzeiten geschieht. Fallen die weg oder baust Du eigentlich eher ne Queue? Also ich persönlich wäre meinem Wecker nicht böse, wenn er mich ein paar millisekunden zu spät, statt gar nicht weckt. Apropos Worstcase, tausende Termine, sqlite: Du bist einer von diesen wichtigen Nerds, die sich bzw. ihren Tagesablauf optimieren und dafür eine Smartphone App (Apple/Android) entwicklen?! ;) P.S: Weiß nicht ob sqLite das kann, aber es gibt Primärschlüsselverfahren, die direkt beim Einfügen nativ sortieren (Wahrscheinlich braucht man dann für identische Weckzeiten noch ein weiteres Schlüsselattribut (Sequenz)). |
AW: Wo binäre Suche schneller, mit Array oder StringList?
Zitat:
Delphi-Quellcode:
Dieses Resultat speichere ich nun in einer Variablen, die in der Ereignisbehandlung vom Timer mit der aktuellen Uhrzeit verglichen wird. Ist das Datum erreicht, klingelts und in der Alarm-Methode wird dann wieder der nächste Termin in diese Variable gesetzt. Empfehlenswert ist auch eine Spalte, die angibt, wieviele Sekunden oder Minuten vor dem eigentlichen Termin der Alarm losgehen soll oder auch eine Variable, die diese Zeit für alle Termine gleich behandelt.
Function DatMod.GetNextAlarmDate : TDateTime;
Begin Query.Active := False; Query.SQL.Clear; Query.SQL.Append('select TERMINDATUM, ALARM from TERMINE'); Query.SQL.Append('where ALARM = 1'); // Boolsche Variablen werden z.B. in Firebird als 0 und 1 gespeichert Query.SQL.Append('order by TERMINDATUM'); // das "kleiste" Datum steht am Anfang Query.Open; Query.Last; // an das "größte" Datum springen Result := Query.FieldByName('TERMINDATUM').AsDateTime; Query.Active := False; Query.SQL.Clear; End; |
AW: Wo binäre Suche schneller, mit Array oder StringList?
Also ich würde ja einfach für jeden Wecker den Zeitpunkt des nächsten Bimmelns in eine sortierte Liste eintragen.
Jede Sekunde schaue ich im ersten Eintrag nach, ob es denn Zeit ist. Wenn ja: Bimmele ich und füge für diesen Wecker den Zeitpunkt des nächsten Bimmelns wieder in die Liste an der richtigen Position ein. So muss ich nie suchen, sondern nur nach dem Bimmeln einmalig per Binärsuche die richtige Stelle finden. Alternativ nehme ich einfach eine Priority Queue. |
AW: Wo binäre Suche schneller, mit Array oder StringList?
Zitat:
Du kannst also ruhigen Gewissens jede Sekunde eine Abfrage à la
Delphi-Quellcode:
machen. Das bleibt auch dann noch fast gleich schnell (O(log n)), wenn die Datenbank sehr groß wird (wobei es natürlich auch noch davon abhängt, wie viele Datensätze zwischen t1 und t2 liegen, logisch).
SELECT * FROM termine WHERE t1 <= zeit <= t2 ORDER BY zeit
|
AW: Wo binäre Suche schneller, mit Array oder StringList?
[QUOTE=Namenloser;1301129]
Zitat:
Zitat:
Delphi-Quellcode:
nehmen.
zeit BETWEEN t1 and t2
Zitat:
Kleine Klugscheißerei am Rande :mrgreen: |
AW: Wo binäre Suche schneller, mit Array oder StringList?
Zitat:
Außerdem muss es ja nicht zwangsläufig ein B-Baum sein. Ich weiß nicht, was da in der Praxis zum Einsatz kommt. Auch wenn es gut sein kann, dass es tatsächlich ein B-Baum ist. Auf jeden Fall ist es aber ein balancierter Baum. Zitat:
Zitat:
|
AW: Wo binäre Suche schneller, mit Array oder StringList?
Zitat:
... Ich hab nachgeschaut: B+ Tree für Daten und B Trees für Indices. |
AW: Wo binäre Suche schneller, mit Array oder StringList?
@Namenloser: Ich schrieb ja, das ein Bayer-Baum auch balanciert ist, nur ist ein 'B'-Baum kein b-alancierter Baum sondern ein B-ayer-Baum und 'fast gleich schnell' wird bei einigen RDBMS zum 'gleich schnell', wegen der Implementierung des Indexes als B+-Baum. Ich habe ja keine Aussage von Dir negiert sondern nur präzisiert.
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 21:45 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz