LinkedList durchsuchen

[Kiffi]

Hallo,

ich muss in regelmäßigen Abständen eine LinkedList nach einem String
durchsuchen. Derzeit verwende ich hierzu unten angefügten Code, welcher
auch zufriedenstellend funktioniert.

Trotzdem: Gibt's was besseres / schnelleres?

Danke im voraus & Grüße ... Kiffi

Code: Alles auswählen

Procedure.l FindElement(ItemToFind$)
  intCounter.l = 0
  ForEach myLinkedList()
    If myLinkedList()\myString= sFilename$
      ProcedureReturn intCounter
    EndIf
    intCounter + 1
  Next      
  ProcedureReturn -1
EndProcedure

[DrShrek]

Ja

Code: Alles auswählen

Procedure.l FindElement(ItemToFind$) 
  ForEach myLinkedList() 
    If myLinkedList()\myString= sFilename$ 
      ProcedureReturn ListIndex(myLinkedList())  
    EndIf 
  Next      
  ProcedureReturn -1 
EndProcedure 

Aber das ist die 'brute force' Methode.
Die inteligente Variante ist noch schneller.
Vieleicht kommst DU ja selbst drauf, was für eine das ist...

[Ynnus]

Ja

Code: Alles auswählen

Procedure.l FindElement(ItemToFind$) 
  ForEach myLinkedList() 
    If myLinkedList()\myString= sFilename$ 
      ProcedureReturn ListIndex(myLinkedList())  
    EndIf 
  Next      
  ProcedureReturn -1 
EndProcedure 

Aber das ist die 'brute force' Methode.
Die inteligente Variante ist noch schneller.
Vieleicht kommst DU ja selbst drauf, was für eine das ist...

Ich weiß ja nicht ob das wirklich schneller ist. Ich stelle mir gerade vor, wenn ListIndex in etwa so vorgeht, dass die komplette Linked List durchlaufen wird bis das aktuelle Element gefunden wird und dann die Anzahl der durchlaufenen Elemente als Index zurückgegeben wird, dann ist diese Methode wesentlich langsamer. Noch dazu, egal ob jetzt intern schon eine Variable das aktuelle Element intern mitloggt und man per ListIndex nicht die Liste neu durchläuft sondern diese Prozedur auch nur eine interne Variable rausgibt, so ist ein Prozeduraufruf doch immer langsamer als der direkte Code im Kontext. Also eine Variable zurückzugeben ist weniger Rechenintensiv als eine Prozedur aufzurufen die nichts weiter tut als eine Variable zurückugeben. Daher wär ich mir nicht so sicher ob diese gepostete Methode oben wirklich die flottere ist.

[Froggerprogger]

Die inteligente Variante ist noch schneller.

Was meinst Du damit ?
Wenn es keine weiteren Infos über die Listelemente gibt, wie z.B. eine Ordnung, dann gibt es nichts schnelleres, als stumpf die Elemente durchzugehen, bis man das richtige gefunden hat.
Also am Prinzip lässt sich da nichts ändern.
In geordneten Arrays hingegen kann man per BinarySearch suchen, was wesentlich schneller geht.

Oder meinst Du, die Laufzeit zu verschnellern, indem man auf PBs eigene Funktionen verzichtet und sich selbst direkt anhand der Pointer der Listelemente durch die Liste hangelt ?

[DrShrek]

Zu Sunnys Aussage: Ausprobieren.

[Ynnus]

Zu Sunnys Aussage: Ausprobieren.

Ne, dafür bin ich jetzt zu müde. Hast du es denn schon getestet?

[DrShrek]

Hast du es denn schon getestet?

Nein!
Ich versuchs mal so zu erklären:
Abhängig davon an welcher Stelle der String gefunden wird, ist Deine Variante die schnellere. Mein Vorschlag ist (wahrscheinlich) besser, wenn der String näher am Ende der Liste liegt.
Das ist natürlich von der Grösse der Liste abhängig.

[Stonedar]

Wenns um eine sortierte Liste geht, würde ich eine binäre Suche empfehlen

[freedimension]

Wie FroggerProgger schon sagte: BinarySearch

Dazu muss die Liste allerdings in sortierter Form vorliegen. Wenn das gegeben ist teilt man diese Liste virtuell in zwei Teile indem man zuerst das mittlere Element vergleicht. Je nach Ergebnis suche ich dann in der einen oder der anderen Hälfte weiter, auch hier nehme ich dann wieder das mittlere Element usw.
Damit hat man eine sehr gute Performance, jede Suche wird dabei in relativ gleichbleibender Zeit durchgeführt. Ob ich eine oder 14 Stringabfragen durchführe ist im Normalfall unerheblich, bei einer oder tausenden, wie es beim sturen Durchgehen der Liste möglich ist, fällt das schon weitaus mehr ins Gewicht.
Mit 14 Abfragen decke ich mit dieser Methode übrigens einen Bereich von ca. 16.000 Datensätzen ab, wenn ich mich nicht verrechnet habe

[Froggerprogger]

Das Problem:
BinarySearch funktioniert in einer LinkedList nicht:
Man kann zwar z.B. per SelectElement() das mittlerste Element 'direkt' anspringen, aber da nirgendwo ein Table mit den Sprungadressen liegt, wird sich durch diesen Befehl ebenfalls einfach von der aktuellen Position bis dahin an den Pointern durchgehangelt. Ebenso muss man sich dann wieder ggf. zurückhangeln, etc.
Da kann man auf dem Weg auch grad noch die Werte vergleichen.

btw: BinarySearch ist enorm schnell in sortierten Arrays.
(logarithmisch statt linear, also z.B. in einem Array mit 10000 Elementen etwa 1100 mal so schnell, in einem Array mit 1000000 Elementen schon etwa 10000 mal schneller )