AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign FreePascal Wo binäre Suche schneller, mit Array oder StringList?

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

Ein Thema von AlexII · begonnen am 11. Mai 2015 · letzter Beitrag vom 12. Mai 2015
Antwort Antwort
Seite 3 von 4     123 4   
Popov
(Gast)

n/a Beiträge
 
#21

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

  Alt 11. Mai 2015, 16:32
@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.
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

Registriert seit: 28. Apr 2008
Ort: Stolberg (Rhl)
6.659 Beiträge
 
FreePascal / Lazarus
 
#22

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

  Alt 11. Mai 2015, 16:58
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.
Programme gehorchen nicht Deinen Absichten sondern Deinen Anweisungen
R.E.D retired error detector
  Mit Zitat antworten Zitat
jobo

Registriert seit: 29. Nov 2010
3.072 Beiträge
 
Delphi 2010 Enterprise
 
#23

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

  Alt 11. Mai 2015, 17:46
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)).
Gruß, Jo
  Mit Zitat antworten Zitat
Perlsau
(Gast)

n/a Beiträge
 
#24

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

  Alt 11. Mai 2015, 18:07
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.

Geändert von Perlsau (11. Mai 2015 um 22:43 Uhr) Grund: Fehlerkorrektur
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#25

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

  Alt 11. Mai 2015, 21:50
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.
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#26

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

  Alt 11. Mai 2015, 21:57
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).
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#27

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

  Alt 11. Mai 2015, 22:22
[QUOTE=Namenloser;1301129]
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.
... WHERE t1 <= zeit <= t2 ...
Geht das mit SQLite? Ich würde zeit BETWEEN t1 and t2 nehmen.
...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
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#28

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

  Alt 11. Mai 2015, 22:36
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.
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.
...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.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#29

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

  Alt 11. Mai 2015, 23:50
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.
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#30

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

  Alt 12. Mai 2015, 07:43
@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.
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 23:21 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