Hallo!
Das gilt natürlich nur für Datensätze die im Stack abgelegt wurden.
https://de.wikipedia.org/wiki/Stapelspeicher
Bei größeren Datenclouds gibt es natürlich völlig andere
Sortiermethoden, die
einer Stack- Methode völlig überlgen sind.
Die angesprochene Struktur entspricht einem Stack. Durch eine effiziente
Programmierung ließen sich auch hier Sub-Routinen schreiben, die
recourcenschonend und zeitsparend sind. Aber auch hierbei ist eine
saubere Sortierung das A und O.
In der binären Suche werden bedeutende Aspekte der Hardware
unberücksicht gelassen. So wird Im Binärsystem maximal durch I/O mit
einer Wurzel 2 gesucht... Ein 32- Bit System kann problemlos auf 50%
Prozessorkapazität ausgelastet werden; also Wurzel 16; und ein 64-Bit
System auf Wurzel 32; je nach Konfiguration sogar noch höher.
Ein effizienter Suchansatz wäre folgender:
- sortiere die Datei nach der Bezeichnung des möglichen Suchelements und
stelle dies voran
- befindet sich das Suchelement überhaupt in der Datei?
wenn nein: Kein Element gefunden
wenn ja:
- teile die Datei durch 16 bzw 32 und bestimme in welchem Teil der
Suchbegriff sich befindet
- wiederhole recursiv die Teilung bis Disvisor = 0
- gebe das Ergenis aus
Vorteil dieser Suche:
Es wird nicht jede Zeile durchsucht, sondern das Suchergebnis
exponentiell eingeschränkt.
Es wird eine höhere CPU- Auslastung generiert, aber die Suchzeiten sind
minimal.
Ein Suchergebnis ist meist innerhalb weniger Suchvorgängen (idR <10)
gefunden.
Alle Klarheiten beseitigt?
Grüsse Guido
Am 20.01.2016 um 12:21 schrieb Werner Tietz:
Hallo
Im Hinblick auf die _Laufzeit der Funktion_ ist es umso wichtiger zu
sortieren je länger die Suchliste ist:
_Laufzeit im ungünstigsten Fall_:
Listenlänge unsortiert sortiert
10 10 ~4
100 100 ~7
1000 1000 ~10
10000 10000 ~14
100000 100000 ~17
1000000 1000000 ~20
oder allgemein, die Laufzeit mit Sortierparameter 0 steigt linear zur
Listenlänge, die Laufzeit auf _sortierten_ Listen mit entsprechenden
Sortierparameter steigt nur um log2(Listenlänge)
siehe dazu https://de.wikipedia.org/wiki/Bin%C3%A4re_Suche
Werner
--
Liste abmelden mit E-Mail an: users+unsubscr...@de.libreoffice.org
Probleme?
http://de.libreoffice.org/hilfe-kontakt/mailing-listen/abmeldung-liste/
Tipps zu Listenmails: http://wiki.documentfoundation.org/Netiquette/de
Listenarchiv: http://listarchives.libreoffice.org/de/users/
Alle E-Mails an diese Liste werden unlöschbar öffentlich archiviert
