Re: [de-users] calc - sverweis

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+unsubscribe@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