Wo binäre Suche schneller, mit Array oder StringList?

[Popov]

@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.

[p80286]

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.

[jobo]

Zitat von p80286:

Darum solltest Du vllt. erst einmal den Worst case deiner Anwendung definieren, und dann zusehen, das Du diesen beherrschst.

Korrekt! Als kleine Ergänzung:
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)).

[Perlsau]

Zitat von AlexII:

Ok... also es ist folgendes, es geht um einen Wecker. Dieser soll nach mehreren (Hunderte, oder Tausende) Terminen "Ausschau" halten, und bei angegebener Zeit Alarm schlagen. Das heißt, dass ich jede Sekunde die aktuelle Uhrzeit mit der in der DB vergleichen muss. Nun suche ich wie ich das am besten mache. Eine binäre Suche wäre schon sinnvoll, oder?

In meiner Terminverwaltung mache ich das so, daß ich im Datenmodul eine Public-Methode bereitstelle. Beim Programmstart wird der nächste Termin in einer Variablen gespeichert:

Delphi-Quellcode:

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;

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.

[Dejan Vu]

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.

[Namenloser]

Zitat von jobo:

P.S: Weiß nicht ob sqLite das kann, aber es gibt Primärschlüsselverfahren, die direkt beim Einfügen nativ sortieren

Das sollte eigentlich jede Datenbank so machen, wenn ein Index auf der Spalte liegt. Der normale Standard-Index ist bei gängigen Datenbanken immer ein balancierter Baum, wenn man nichts anderes spezifiziert. Deswegen kostet das Sortieren bei einer Abfrage auch keine extra Zeit, wenn auf dem Sortierkriterium ein Index liegt.

Du kannst also ruhigen Gewissens jede Sekunde eine Abfrage à la SELECT * FROM termine WHERE t1 <= zeit <= t2 ORDER BY zeit 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).

[Dejan Vu]

[QUOTE=Namenloser;1301129]

Zitat von jobo:

Der normale Standard-Index ist bei gängigen Datenbanken immer ein balancierter Baum, wenn man nichts anderes spezifiziert.

Ein B-Baum ist aber kein 'balancierter Baum' (na ja, irgendwie schon). sondern ein Bayer-Baum.

Zitat von Namenloser:

... WHERE t1 <= zeit <= t2 ...

Geht das mit SQLite? Ich würde zeit BETWEEN t1 and t2 nehmen.

Zitat von Namenloser:

...fast gleich schnell (O(log n))

Die Basis des Logarithmus ist aber sehr groß: PageSize div SizeOf(Key). Das geht gegen O(1).

Kleine Klugscheißerei am Rande

[Namenloser]

Zitat von Dejan Vu:

Zitat von Namenloser:

Der normale Standard-Index ist bei gängigen Datenbanken immer ein balancierter Baum, wenn man nichts anderes spezifiziert.

Ein B-Baum ist aber kein 'balancierter Baum' (na ja, irgendwie schon).

Natürlich ist der balanciert? Erfüllt genau die Definition von Wikipedia: „Ein balancierter Baum (englisch oft self-balancing tree) ist in der Informatik ein Spezialfall der Datenstruktur Baum, der eine maximale Höhe von c⋅log(n) garantiert, wobei n die Anzahl der Elemente im Baum angibt und c eine von n unabhängige Konstante ist.“
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 von Dejan Vu:

Geht das mit SQLite? Ich würde zeit BETWEEN t1 and t2 nehmen.

Keine Ahnung, ich mach nur alle paar Jahre mal was mit SQL.

Zitat von Dejan Vu:

Zitat von Namenloser:

...fast gleich schnell (O(log n))

Die Basis des Logarithmus ist aber sehr groß: PageSize div SizeOf(Key). Das geht gegen O(1).

Ja, „fast gleich schnell“ in der Praxis.

[BUG]

Zitat von Namenloser:

Außerdem muss es ja nicht zwangsläufig ein B-Baum sein. Ich weiß nicht, was da in der Praxis zum Einsatz kommt.

Ich würde wetten das es eine Variante des B+ Baums ist ... Datenbankers Liebling

...

Ich hab nachgeschaut: B+ Tree für Daten und B Trees für Indices.

[Dejan Vu]

@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.