Schnelles suchen in einfach verketeter Liste

Für Fragen zur Programmiersprache auf welcher Lazarus aufbaut
Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6209
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Beitrag von af0815 »

ch hab da mal n kleines Problem für die alten Hasen.
Ich hab ne einfach verkettete Liste, die ich komplett durchgehn muss um ein Element zu finden.
Gibt es einen einfachen Weg, um das zu beschleunigen ?
Ich dachte daran die Liste zu sortieren und dann je nach irgendwo in de Mitte anzufangen zu suchen jedoch wird das immer alles so verdammt komplex. Ich lande immer wieder bei Bäumen. Gibt es da keine einfachere Möglichkeit ?


So wie du es in den letzten Posts beschreibst, gibt es nur eine Lösung : BÄUME !

Alles andere Sortierte Listen, Hash-Listen, Indexdateien,... ist für das was du willst nicht brauchbar. Sehe es wie das Rad. Wenn du was rollen willst, so wirst du immer wieder auf das Rad zurück kommen.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Benutzeravatar
theo
Beiträge: 10497
Registriert: Mo 11. Sep 2006, 19:01

Beitrag von theo »

af0815 hat geschrieben:So wie du es in den letzten Posts beschreibst, gibt es nur eine Lösung : BÄUME !


Ein sortiertes Array mit Binärsuche ginge wohl auch.
Für eine einfache, nicht indizierte verkettete Liste sehe ich aber keine andere Möglichkeit als die lineare Suche.

Christian
Beiträge: 6079
Registriert: Do 21. Sep 2006, 07:51
OS, Lazarus, FPC: iWinux (L 1.x.xy FPC 2.y.z)
CPU-Target: AVR,ARM,x86(-64)
Wohnort: Dessau
Kontaktdaten:

Beitrag von Christian »

Nein ein Binary Search muss doch nicht mir arrays gemacht werden. Ne Liste ist schon recht ideal dafür. Solange sie sortiert ist.
W.m.k.A.h.e.m.F.h. -> http://www.gidf.de/

Benutzeravatar
theo
Beiträge: 10497
Registriert: Mo 11. Sep 2006, 19:01

Beitrag von theo »

Christian hat geschrieben:Nein ein Binary Search muss doch nicht mir arrays gemacht werden. Ne Liste ist schon recht ideal dafür. Solange sie sortiert ist.


Kommt drauf an wie man's verstehen will.
Ich gehe doch recht in der Annahme, dass du ein spezifisches Element nur erreichst, indem du dich vom ersten an durchhangelst.
Also musst du bei einer linked List und binary search mehrmals durch das ganze durchrattern um die mittleren Elemente zu lokalisieren.
Du brauchst aber weniger Stringvergleiche, das stimmt schon. (falls ich alles richtig verstehe).

Christian
Beiträge: 6079
Registriert: Do 21. Sep 2006, 07:51
OS, Lazarus, FPC: iWinux (L 1.x.xy FPC 2.y.z)
CPU-Target: AVR,ARM,x86(-64)
Wohnort: Dessau
Kontaktdaten:

Beitrag von Christian »

Ne man hangelt sich net durch sondern teilt die Bereiche immer wieder.

Also fängst zuerst an und teilst deine Liste in oberen und unteren bereich und schaust nach ob der anfangsbuchstabe > dem oberen ist dann muss er im unteren sein oder umgedreht dann teilst den gefundenen bereich weiter ...
W.m.k.A.h.e.m.F.h. -> http://www.gidf.de/

Benutzeravatar
theo
Beiträge: 10497
Registriert: Mo 11. Sep 2006, 19:01

Beitrag von theo »

Ja klar, ich glaube wir verstehen uns falsch.
Ich meinte, dass du keinen direkten Zugriff hast auf z.B. Element 100.
Beim Array geht, das: MyArray[100] aber bei einer verketteten Liste musst du doch solange zum nächsten Element hüpfen, bis das hunderste Element erreicht ist.
Also muss du bei binary search mindestens einmal durch die Halbe Liste eiern, dann noch durch einen Viertel usw.
Oder nicht?
Wie gesagt: Es ist schon klar, dass das weniger Stringvergleiche braucht und deshalb wahrscheinlich trotzdem schneller ist als die lineare Suche.
Sortieren kostet aber auch Zeit. Hängt halt von der konkreten Anwendung ab.

http://en.wikipedia.org/wiki/Linked_lis ... _up_search

Christian
Beiträge: 6079
Registriert: Do 21. Sep 2006, 07:51
OS, Lazarus, FPC: iWinux (L 1.x.xy FPC 2.y.z)
CPU-Target: AVR,ARM,x86(-64)
Wohnort: Dessau
Kontaktdaten:

Beitrag von Christian »

Natürlich kann auch eine Liste Element 100 direkt ansprechen da ja der Speicherverbrauch eines Pointers bekannt ist. TList macht das schon so...
Im Moment benutze ich ja keine verlinkte Liste sondern eine TList kapselung
W.m.k.A.h.e.m.F.h. -> http://www.gidf.de/

Benutzeravatar
theo
Beiträge: 10497
Registriert: Mo 11. Sep 2006, 19:01

Beitrag von theo »

Aha, dann führst du uns aber ganz schön an der Nase rum ;-)
TList benützt ein Array, keine verkettete Liste

TPointerList = array[0..MaxListSize - 1] of Pointer;

Christian
Beiträge: 6079
Registriert: Do 21. Sep 2006, 07:51
OS, Lazarus, FPC: iWinux (L 1.x.xy FPC 2.y.z)
CPU-Target: AVR,ARM,x86(-64)
Wohnort: Dessau
Kontaktdaten:

Beitrag von Christian »

Was es intern benutzt hat mich ehrlich gesagt noch nie interessiert aber hast schon recht hab mich im ersten post falsch ausgedrückt
W.m.k.A.h.e.m.F.h. -> http://www.gidf.de/

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6209
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Beitrag von af0815 »

Und was ist jetzt die korrigierte Version ?
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

pluto
Lazarusforum e. V.
Beiträge: 7178
Registriert: So 19. Nov 2006, 12:06
OS, Lazarus, FPC: Linux Mint 19.3
CPU-Target: AMD
Wohnort: Oldenburg(Oldenburg)

Beitrag von pluto »

Natürlich kann auch eine Liste Element 100 direkt ansprechen da ja der Speicherverbrauch eines Pointers bekannt ist. TList macht das schon so...

und wie ?
ich habe eine kleine unit geschrieben die genauso arbeitet wie TObjectlist nur halt mit doppelt verketten liste. und dazu habe ich eine eigene TStringlist geschrieben abgeleitet von TStringlist. die meine Doppel Verkette Liste intern nutzt.

Wenn ich Eintrag 100 ansprechen möchte, muss ich doch eine schleife starten.
Die Größe des Pointers könnte ich ja heraus finden mit Sicherheit.

Code: Alles auswählen

function TmyObjectList.GetMyListItem(Index: Integer): TObject;
var
  i:Integer;
  obj:TmyObjectListItem;
begin
 
  if Index <=Count-1 then begin
    // Optimierung: Damit nicht bei jeder anfrage
    // Neu gesucht werden muss
    if (oldItemindex > -1) and (index = oldItemIndex) then begin
      obj:=oldObject;
    end
    else begin
      obj:=First;
      oldItemIndex:=index;
      for i:=0 to index-1 do begin
        if obj.nex <> NIL then
          obj:=obj.nex;
      end;
      oldObject:=obj;
    end;
    FehlerIndex:=frNone;
    result:=obj.inhalt;
  end
  else begin
    if Count-1 > 0 then FehlerIndex:=frHihgIndex;
    if Count-1 = 0 then FehlerIndex:=frClearList;
    result:=niL;
  end;
 
end;

so mache ich das im Moment.

Code: Alles auswählen

TmyObjectListItem = class
  private
    parent:TObject;
  public
    prv,nex:TmyObjectListItem;
    inhalt:TObject;
 
  protected
  published
  end;

und sie sieht die Strucktur aus, worauf der "normale" User eigentlich nie von direkt drauf zugreifst. Wie könnte ich jetzt die Speicher Adresse berechnen ? für Element 100 ?
(wobei ja auch unterschiedliche Objekte gespeichert werden könnten, die unterschiedlich groß sind)
MFG
Michael Springwald

Benutzeravatar
theo
Beiträge: 10497
Registriert: Mo 11. Sep 2006, 19:01

Beitrag von theo »

pluto hat geschrieben:Wie könnte ich jetzt die Speicher Adresse berechnen ? für Element 100 ?


Gar nicht Pluto. Christian hat uns auf eine falsche Fährte geführt, indem er von verketter Liste sprach und dabei eine TList meinte, die intern ein Array benützt.
Bei einer einfach verketteten Liste weiss nur das vorherige Element wo das nächste steckt.
Das ist ja der Witz daran. Man muss nicht wie beim Array alles raufkopieren, wenn man was einfügen will, sondern nur nen Zeiger umhängen. Das hat aber den genannten Nachteil, dass man nicht frei zugreifen kann.

pluto
Lazarusforum e. V.
Beiträge: 7178
Registriert: So 19. Nov 2006, 12:06
OS, Lazarus, FPC: Linux Mint 19.3
CPU-Target: AMD
Wohnort: Oldenburg(Oldenburg)

Beitrag von pluto »

Ja dann hatte ich also recht *G*

Aber wie geht das beim Array ? liegt das daran das jedes Element in einem Array im Prinzip gleich groß ist ? aber das stimmt doch auch wieder nicht oder ?
ich habe jetzt eine klasse die unterschiedliche Klassen speichern kann.
damit wäre doch die Größe nicht immer gleich.

Am Anfang dachte ich auch das TObjectlist oder TList eine Verkette Liste nutzt, aber das stimmt leider nicht. Darum habe ich ja auch meine eigene Variante gebaut.

Aber die suche könnte eingedemt werden, bei einer Listbox beispielweise:
der Programmier gibt jetzt genau an: welches das erste und das letzte sichtbare Zeichen ist
und speicher diese Pointer in zwei Gobale Variablen ab. Beim zeichnen müsste ich ja jetzt immer wieder auf items[index] drauf zugreifen. Genau das könnte ich jetzt minimieren.
oder nicht ?

Das wollte ich bei mir noch einbauen. 4 Variablen: 2 Integer zwei Pointer.
Sobald die zwei Integer variablen gesetzt wird, wird einmal der jeweilige Pointer gesetzt. beim suchen könnte ich jetzt einfach vom ersten sichtbaren bis zum letzten sichtbaren Eintrag suchen.

Wobei das auch nur in bestimmten Fällen sinnvoll währe z.b. halt beim Zeichnen. oder bei eine Kollisions Erkennung z.b. mit der Maus.
MFG
Michael Springwald

Benutzeravatar
theo
Beiträge: 10497
Registriert: Mo 11. Sep 2006, 19:01

Beitrag von theo »

pluto hat geschrieben:Aber wie geht das beim Array ? liegt das daran das jedes Element in einem Array im Prinzip gleich groß ist ? aber das stimmt doch auch wieder nicht oder ?
ich habe jetzt eine klasse die unterschiedliche Klassen speichern kann.
damit wäre doch die Größe nicht immer gleich.

Doch, weil das Array (z.B. bei TList) ja nur die Pointer auf die Objekte speichert.
Pointer sind immer 32 bit (resp 64 bit). Auf wieviel Speicherbereich die zeigen ist dann wieder beliebig (Pchar, TObject, etc).

pluto hat geschrieben:Aber die suche könnte eingedemt werden, bei einer Listbox beispielweise:
der Programmier gibt jetzt genau an: welches das erste und das letzte sichtbare Zeichen ist
und speicher diese Pointer in zwei Gobale Variablen ab. Beim zeichnen müsste ich ja jetzt immer wieder auf items[index] drauf zugreifen. Genau das könnte ich jetzt minimieren.
oder nicht ?


Schon, dass wäre dann eine Indizierung. Die musst du aber mitführen beim Einfügen etc.
Eine TList ist da schon viel praktischer.

pluto
Lazarusforum e. V.
Beiträge: 7178
Registriert: So 19. Nov 2006, 12:06
OS, Lazarus, FPC: Linux Mint 19.3
CPU-Target: AMD
Wohnort: Oldenburg(Oldenburg)

Beitrag von pluto »

Wenn jeder Pointer 32 Byte große ist, wie kann damit die genau Position in meiner Doppelt Verketteten Liste ermitteln werden ?
(müsste ja dann auch gehen) z.b. müsste ich einfach nur 32 * Index sagen ?
MFG
Michael Springwald

Antworten