Listen sind dynamische Arrays

Für Fragen zur Programmiersprache auf welcher Lazarus aufbaut
mschnell
Beiträge: 3417
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

Re: Listen sind dynamische Arrays

Beitrag von mschnell »

Ich würde vermuten, dass eine Datenbank balancierte Binärbäume verwendet, um den Aufwand an Move-Operationen zu minimieren.
Man kann natürlich auch über einen Hash-Algorithmus nachdenken. Der hat aber wieder andere Nachteile (feste gesamt Größe, schlechte Cache-Ausnutzung).
-Michael
Zuletzt geändert von mschnell am Di 15. Sep 2020, 14:11, insgesamt 1-mal geändert.

Warf
Beiträge: 1480
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Listen sind dynamische Arrays

Beitrag von Warf »

Socke hat geschrieben:
Mo 14. Sep 2020, 16:20
Dann stellt sich aber auch hier die Frage: Welche Datenstruktur nutzt die Datenbank? Sind es Arrays, verkettete Listen oder vielleicht sogar Bäume? Bäume? Warum wurden Pascal-Listen nicht als Bäume implementiert?!
In der C++ STL werden bäume als arrays implementiert, um sich die cache lokalität und schnellen zugriffszeiten zunutze zu machen :mrgreen:

Das gesagt benutzen Datenbanken sehr gerne B-Bäume. Aber vor allem haben Datenbanken einen ganz großen vorteil, sie halten mehrere Indize strukturen vor. So kann man in einer Relationalen Datenbank durch das Indizieren mehrere Spalten das suchen und sortieren nach mehreren Feldern optimieren, statt wie bei einer Normalen Liste/Map nur nach einem.

Das benötigt aber viel mehr Speicher und hat einen deutlich größeren Konstanten overhead, dafür ist man extrem viel flexibler

PascalDragon
Beiträge: 55
Registriert: Mi 3. Jun 2020, 07:18
OS, Lazarus, FPC: L 2.0.8, FPC Trunk, OS Win/Linux
CPU-Target: Aarch64 bis Z80 ;)
Wohnort: München

Re: Listen sind dynamische Arrays

Beitrag von PascalDragon »

mschnell hat geschrieben:
Mo 14. Sep 2020, 10:20
PascalDragon hat geschrieben:
Fr 11. Sep 2020, 16:36
Timm Thaler hat geschrieben:
Fr 11. Sep 2020, 16:03
Warum hat Pascal das nicht so implementiert?
Weil du mit Arrays 'nen schnelleren indexbasierten Zugriff hast. Dafür ist halt Einfügen/Entfernen potentiell langsamer (wobei Einfügen am Ende auch trivial ist, so lange die aktuelle Kapazität noch nicht erreicht ist).
Wenn man einen Kompromiss zwischen Einfüge- und Lese- Effizienz will, muss man eine (Memory-) Datenbank nehmen.
Nein, man nimmt einfach die korrekte Datenstruktur (dafür hat man solche Kurse im Informatikstudium schließlich!). Eine Datenbank (egal ob Memory oder nicht) ist in den meisten Fällen einfach nur Overkill.
FPC Compiler Entwickler

siro
Beiträge: 388
Registriert: Di 23. Aug 2016, 14:25
OS, Lazarus, FPC: Windows 10
CPU-Target: 64Bit
Wohnort: Berlin

Re: Listen sind dynamische Arrays

Beitrag von siro »

Ich habe grade einen 25 Jahre alten Code von mir gefunden. (Turbo Pascal)
Da habe ich eine doppelt dynamisch verkettete Liste programmiert.
Im Prinzip gibt es dort nur folgende Elemnte
FIRST, NEXT, PREV, LAST und das momentan aktive.
Hier hatte ich auch eine Textsuchfunktion sowie das Laden und Speichern der Liste programmiert.
Sinn und Zweck war damals das Aufbewahren von verschieden grossen Objekten für ein Zeichenprogramm,
aber auch von grossen (langen) Texten.

Ist "altbacken" aber trotzdem hier mal der Code :

Code: Alles auswählen

UNIT liste;       { Siro 10.08.1995 }

INTERFACE

TYPE L_SelectType = (L_FIRST,L_NEXT,L_PREV,L_LAST);

Procedure L_Clear   (Var Liste:Pointer);
Function  L_Add     (Var Liste:Pointer; Var Data; DataSize:Word):Boolean;
Function  L_Insert  (Var Liste:Pointer; Var Data; DataSize:Word):Boolean;
Function  L_Replace (Var Liste:Pointer; Var Data; DataSize:Word):Boolean;
Function  L_Delete  (Var Liste:Pointer):Boolean;

Function  L_Set(Liste:Pointer; Select:L_SelectType):Boolean;
Function  L_SetFirst (Liste:Pointer):Boolean;
Function  L_SetNext  (Liste:Pointer):Boolean;
Function  L_SetPrev  (Liste:Pointer):Boolean;
Function  L_SetLast  (Liste:Pointer):Boolean;

Function  L_GetEntrys   (Liste:Pointer):Word;
Function  L_GetDataSize (Liste:Pointer):Word;
Function  L_GetDataPtr  (Liste:Pointer):Pointer;
Function  L_GetData     (Liste:Pointer; Var Data):Boolean;

Function  L_Save(Liste:Pointer; FileName:String):Boolean;
Function  L_Load(Var Liste:Pointer; FileName:String):Boolean;

Function  L_TextLoad   (Var Liste:Pointer; Filename:String):Boolean;
Function  L_TextSave   (Liste:Pointer; FileName:String):Boolean;
Function  L_TextSearch (var Liste  : Pointer;
                         SearchStr  : String;
                         Var LineNo : Word;
                         Var PosNo  : Word
                       ):Boolean;

{----------------------------------------------------------------------------}

IMPLEMENTATION

Type EntryType = ^EntryRecord;     { Zeiger auf einen Listeneintrag       }
     EntryRecord = Record          { Ein Listeneintrag besteht aus :      }
       prev : EntryType;           { Zeiger auf Vorgaenger Eintrag        }
       next : EntryType;           { Zeiger auf Nachfolgenden Eintrag     }
       size : Word;                { Anzahl Bytes der Daten des Eintrags  }
       data : Byte;                { 1. Datenbyte des Eintrags            }
     end;

Type ListType = ^ListRecord;       { Zeiger auf Variablen einer Liste     }
     ListRecord = Record           { folgende Variablen hat jede Liste    }
       first   : EntryType;        { Zeiger auf ersten Eintrag            }
       active  : EntryType;        { Zeiger auf momentan aktiven Eintrag  }
       last    : EntryType;        { Zeiger auf letzten Eintrag           }
       Entrys  : Word;             { Anzahl Eintraege in der Liste        }
     end;

CONST MAX_DATA_SIZE = 60000;       { maximale Anzahl Bytes pro Eintrag    }
{----------------------------------------------------------------------------}
{ Haengt an das Ende der Liste einen neuen Eintrag an und setzt diesen neuen }
{ Eintrag als aktives Element. Liefert FALSE wenn nicht genug Speicher auf   }
{ dem Heap vorhanden ist um das neue Element anzuhaengen.                    }

Function L_Add(Var Liste:Pointer; Var Data; DataSize:Word):Boolean;
Var new:EntryType;  EntrySize:Word;
Begin
  L_Add := FALSE;
  if DataSize > MAX_DATA_SIZE then EXIT;
  EntrySize := DataSize + (SizeOf(EntryRecord)-1);
  if MaxAvail < EntrySize then EXIT;
  GetMem(new,EntrySize);
  new^.next := NIL;
  new^.size := DataSize;
  Move(Data,new^.Data,DataSize);

  if Liste = NIL then Begin
    if MaxAvail < SizeOf(ListRecord) then Begin
      FreeMem(new,EntrySize);
      EXIT;
    end;
    GetMem(Liste, SizeOf(ListRecord));
    With ListType(Liste)^ do Begin
      new^.prev := NIL;
      first   := new;
      active  := new;           { muss sein sonst kein Element aktiv }
      last    := new;
      Entrys  := 1;
    end;
  end else With ListType(Liste)^ do Begin
    new^.prev  := last;
    last^.next := new;
    active     := new;       { muss nicht sein ist optional }
    last       := new;
    inc(Entrys);
  end;
  L_Add := TRUE;
end;
{----------------------------------------------------------------------------}
{ speichert die Textliste danach ist das letzte Element aktiv }
Function L_TextSave(Liste:Pointer; FileName:String):Boolean;
Var F:Text;  Type Sptr=^String;
Begin
  L_TextSave := FALSE;
  Assign(F,FileName);
  Rewrite(F);
  if ioresult <> 0 then EXIT;
  if L_SetFirst(Liste) then With ListType(Liste)^ do Repeat
    Writeln(F,Sptr(active^.data)^);
  until NOT L_SetNext(Liste);
  Close(F);
  L_TextSave:=TRUE;
end;
{----------------------------------------------------------------------------}
{ Loescht eine komplette Liste }

Procedure L_Clear(Var Liste:Pointer);
Begin
  if Liste = NIL then EXIT;
  With ListType(Liste)^ do Begin
    active:=last;                       { von hinten loeschen }
    While last <> NIL do Begin
      active:=active^.prev;
      FreeMem(last,(SizeOf(EntryRecord)-1) + last^.Size);
      last:=active;
    end;
  end;
  FreeMem(Liste,SizeOf(ListRecord));
  Liste := NIL;
end;
{----------------------------------------------------------------------------}
{ laed einen beliebigen Textfile in eine Liste.                              }
{ Die Liste wird zuvor geloescht falls sie nicht schon leer ist.             }
{ das erste Element wird aktiv gesetzt }

Function L_TextLoad(Var Liste:Pointer; Filename:String):Boolean;
Var F:Text;  S:String;
Begin
  L_TextLoad:=FALSE;
  if Liste <> NIL then L_Clear(Liste);
  Assign(F,FileName);
  Reset(F);
  if ioresult <> 0 then EXIT;
  While NOT eof(F) do Begin
    ReadLn(F,S);
    if NOT L_Add(Liste,S,length(S)+1) then Begin
      if ListType(Liste)^.last <> NIL then
        ListType(Liste)^.active:=ListType(Liste)^.last
      else L_Clear(Liste);
      Close(F);
      EXIT;
    end;
  end;
  Close(F);
  ListType(Liste)^.active:=ListType(Liste)^.first;
  L_TextLoad:=TRUE;
end;

{----------------------------------------------------------------------------}
{ liefert die Anzahl Datenbytes des aktiven Elements. Ist die Liste leer }
{ wird 0 zurueckgeliefert }

Function L_GetDataSize(Liste:Pointer):Word;
Begin
  L_GetDataSize:=0;
  if Liste = NIL then EXIT;
  With ListType(Liste)^ do Begin
    if active = NIL then EXIT;
    L_GetDataSize := ListType(Liste)^.active^.Size;
  end;
end;
{----------------------------------------------------------------------------}
{ liefert die Adresse der Eintragsdaten des aktiven Elements. }
{ Ist die Liste leer wird NIL zurueckgeliefert }

Function L_GetDataPtr(Liste : Pointer):Pointer;
Begin
  L_GetDataPtr:=NIL;
  With ListType(Liste)^ do Begin
    if active = NIL then EXIT;
    L_GetDataPtr:=@active^.data;
  end;
end;
{----------------------------------------------------------------------------}
{ copiert die Daten des aktiven Elements an die uebergebene Variable }
{ liefert FALSE wenn die Liste leer ist }
{ !!! der Benutzer muss selbst dafuer sorgen, das die Zielvariable }
{ gross genug ist um die Daten aufzunehmen , eventuell vorher mit }
{ L_GetDataSize die Anzahl Bytes erfragen }

Function L_GetData(Liste:Pointer; Var Data):Boolean;
Begin
  L_GetData := FALSE;
  if Liste = NIL then EXIT;
  With ListType(Liste)^ do Begin
    if active = NIL then EXIT;
    Move(active^.Data,Data,active^.Size);
  end;
  L_GetData := TRUE;
end;

{----------------------------------------------------------------------------}
{ liefert die Anzahl Elemente in der Liste.                                  }
{ Ist die Liste leer, wird 0 zurueckgeliefert.                               }

Function L_GetEntrys(Liste:Pointer):Word;
Begin
  if Liste=NIL then L_GetEntrys := 0
               else L_GetEntrys := ListType(Liste)^.Entrys;
end;

{----------------------------------------------------------------------------}
Function L_SetNext(Liste:Pointer):Boolean;
Begin
  L_SetNext := FALSE;
  if Liste = NIL then EXIT;
  With ListType(Liste)^ do Begin
    if active^.next = NIL then EXIT;
    active := active^.next;
  end;
  L_SetNext := TRUE;
end;
{----------------------------------------------------------------------------}
Function L_SetPrev(Liste:Pointer):Boolean;
Begin
  L_SetPrev := FALSE;
  if Liste = NIL then EXIT;
  With ListType(Liste)^ do Begin
    if active^.prev = NIL then EXIT;
    active := active^.prev;
  end;
  L_SetPrev := TRUE;
end;
{----------------------------------------------------------------------------}
Function L_SetFirst(Liste:Pointer):Boolean;
Begin
  L_SetFirst := FALSE;
  if Liste = NIL then EXIT;
  With ListType(Liste)^ do Begin
    active := first;
  end;
  L_SetFirst := TRUE;
end;
{----------------------------------------------------------------------------}
Function L_SetLast(Liste:Pointer):Boolean;
Begin
  L_SetLast := FALSE;
  if Liste = NIL then EXIT;
  With ListType(Liste)^ do Begin
    active := last;
  end;
  L_SetLast := TRUE;
end;

Function L_Set(Liste:Pointer; Select:L_SelectType):Boolean;
Begin
  L_Set:=FALSE;
  if Liste = NIL then EXIT;
  With ListType(Liste)^ do Begin
    case Select of
      L_First : active:=first;
      L_Last  : active:=last;
      L_Next  : if active^.next = NIL then EXIT else active:=active^.next;
      L_Prev  : if active^.prev = NIL then EXIT else active:=active^.prev;
    end;
  end; {with}
  L_Set:=TRUE;
end;

{----------------------------------------------------------------------------}
{ sucht ab der momentan aktiven Position einen String in der Liste.     }
{ wird der String gefunden enthaelt LineNo die Zeilennummer, PosNo die  }
{ Position des ersten Buchstabens des Suchstrings und es wird TRUE      }
{ zurueckgeliefert. Das gefundene Element wird aktiv gesetzt.           }
{ Wird der String nicht gefunden wird FALSE zurueckgeliefert und das    }
{ letzte Element wird aktiv gesetzt                                     }

Function L_TextSearch(var Liste      : Pointer;     { Liste }
                      SearchStr  : String;      { Suchstring }
                      Var LineNo : Word;        { Ergebnis ZeilenNo }
                      Var PosNo  : Word         { Ergebnis Position }
                     ):Boolean;                 { TRUE = gefunden }
Type Sptr=^String;   var tmp:EntryType;
Begin
  L_TextSearch:=TRUE;

  tmp:=ListType(Liste)^.active;   { momentan aktives Element merken }
  if L_SetFirst(Liste) then With ListType(Liste)^ do Begin

    LineNo:=1;        { Die aktive Zeilennummer ermitteln }
    while (active <> tmp) do Begin
      if L_SetNext(Liste) then ;
      inc(LineNo);
    end;

    Repeat
      PosNo:=Pos(SearchStr,String(Sptr(@active^.data)^));
      if PosNo > 0 then EXIT;
      inc(LineNo);
    Until NOT L_SetNext(Liste);
  end;
  LineNo:=0;
  PosNo :=0;
  L_TextSearch:=FALSE;
end;

{----------------------------------------------------------------------------}
{ loescht das momentan aktive Element aus der Liste }
{ liefert FALSE wenn die Liste leer war. Das Nachfolgende Element wird }
{ wird aktiv gesetzt. Wird das letzte Element geloescht, wird falls    }
{ noch Elemente in der Liste sind der Vorgaenger aktiv.  }

Function L_Delete(Var Liste:Pointer):Boolean;
Var temp : EntryType;
Begin
  L_Delete:=FALSE;
  if Liste = NIL then EXIT;
  L_Delete:=TRUE;
  With ListType(Liste)^ do Begin
    if first^.next = NIL then L_Clear(Liste) { nur 1 Element vorhanden }
    else Begin
      if active = first then Begin     { wenn erste Element }
        first:=active^.next;           { wird erstes der Nachfolger }
        FreeMem(active,(SizeOf(EntryRecord)-1) + active^.Size);
        first^.prev:=NIL;              { erstes Element hat nie einen Vorgaenger }
        active:=first;
        dec(Entrys);
        EXIT;
      end;
      if active^.next = NIL then Begin { wenn letztes Element }
        last:=active^.prev;          { wird der letzte der Vorgaenger }
        FreeMem(active,(SizeOf(EntryRecord)-1) + active^.Size);
        last^.next:=NIL;
        active:=last;
        dec(Entrys);         { Eintrage -1 }
      end else Begin         { wenn Element Vorgaenger und Nachfolger hat }
        temp:=active;           { activen merken wird dann geloescht }
        active:=active^.next;      { aktiv wird der Nachfolger }
        temp^.prev^.next:=active;
        active^.prev    :=temp^.prev;
        FreeMem(temp,(SizeOf(EntryRecord)-1) + temp^.Size);
        dec(Entrys);
      end;
    end;
  end; {with}
end;
{----------------------------------------------------------------------------}
{ fuegt eine neues Element VOR das aktuelle Element ein }
{ das neue Element wird aktiv. Sollte die Liste noch leer sein wird  }
{ dies der erste Eintrag. Um hinter das letzte Element ein neues  }
{ anzufuegen MUSS L_Add benutzt werden. }

Function L_Insert(Var Liste:Pointer; Var Data; DataSize:Word):Boolean;
Var EntrySize:Word; new:EntryType;
Begin
  if Liste = NIL then L_Insert:=L_Add(Liste,Data,DataSize)
  else With ListType(Liste)^ do Begin
    L_Insert:=FALSE;
    EntrySize:=DataSize + (SizeOf(EntryRecord)-1);
    if MaxAvail < EntrySize then EXIT;
    GetMem(new,EntrySize);
    Move(Data,new^.data,DataSize);
    new^.prev:=active^.prev;
    new^.next:=active;
    active^.prev:=new;
    if active = first then first:=new
                      else new^.prev^.next:=new;
    active:=new;
    inc(Entrys);
    L_Insert:=TRUE;
  end;
end;
{----------------------------------------------------------------------------}
{ entfernt das aktuelle Element und fuegt an dessen Stelle das neue }
{ Element ein. Unabhaengig davon wie gross die jeweiligen Elemente sind. }
{ ist die Liste leer wird FALSE zurueckgeliefert }
{ das aktive Element wird das neu ersetzte Element }
 
Function L_Replace(Var Liste:Pointer; Var Data; DataSize:Word):Boolean;
Begin
  L_Replace:=FALSE;
  if L_Delete(Liste) then L_Replace:=L_Insert(Liste,Data,DataSize);
end;
{----------------------------------------------------------------------------}
{ speichert eine Liste in der Form :       }
{  DataSize : Word;                        }
{  Datenbytes (Anzahl Bytes in Datasize)   }
{  DataSize : Word;                        }
{  Datenbytes (Anzahl Bytes in Datasize)   }
{  usw.                                    }

Function  L_Save(Liste:Pointer; FileName:String):Boolean;
Var F:File;
Begin
  L_Save:=FALSE;
  Assign(F,FileName);
  Rewrite(F,1);
  if ioresult <> 0 then EXIT;
  if L_SetFirst(Liste) then With ListType(Liste)^ do Repeat
      BlockWrite(F,active^.Size,2);
      BlockWrite(F,active^.data,active^.Size);
  Until NOT L_SetNext(Liste);
  Close(F);
  L_Save:=TRUE;
end;
{----------------------------------------------------------------------------}
{ laed eine Liste in der Form wie in L_Save beschrieben }

Function  L_Load(Var Liste:Pointer; FileName:String):Boolean;
Var F:File; Size:Word; P:Pointer;
Begin
  L_Load:=FALSE;
  if Liste <> NIL then L_Clear(Liste);
  Assign(F,FileName);
  Reset(F,1);
  if ioresult <> 0 then EXIT;
  While NOT eof(F) do Begin
    BlockRead(F,Size,2);
    if MaxAvail < Size then Begin
      Close(F);
      EXIT;
    end;
    GetMem(P,Size);
    BlockRead(F,P^,Size);
    if NOT L_Add(Liste,P^,Size) then Begin
      FreeMem(P,Size);
      L_Clear(Liste);
      Close(F);
      EXIT;
    end;
    FreeMem(P,Size);
  end;
  Close(F);
  L_Load:=TRUE;
end;

end.
Siro
Grüße von Siro
Bevor ich "C" ertragen muß, nehm ich lieber Lazarus...

MitjaStachowiak
Lazarusforum e. V.
Beiträge: 357
Registriert: Sa 15. Mai 2010, 13:46
CPU-Target: 64 bit
Kontaktdaten:

Re: Listen sind dynamische Arrays

Beitrag von MitjaStachowiak »

Hmm, die für ein Array reservierte Größe ist doch im Memorymanager auch immer eine 2-er Potenz, oder? Also wenn man nacheinander Elemente an den Array dran hängt, wird er nur bei jeder Verdopplung umkopiert, oder?

Außer man hängt die Elemente vorne an, dann muss man immer explizit Speicher bewegen. Hält TList auch Kapazität vor dem ersten Element frei, um effizient Operationen wie shift/unshift zu ermöglichen?

Socke
Lazarusforum e. V.
Beiträge: 2780
Registriert: Di 22. Jul 2008, 19:27
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 10/Linux/Raspbian/openSUSE
CPU-Target: 32bit x86 armhf
Wohnort: Köln
Kontaktdaten:

Re: Listen sind dynamische Arrays

Beitrag von Socke »

MitjaStachowiak hat geschrieben:
Di 15. Sep 2020, 11:04
Außer man hängt die Elemente vorne an, dann muss man immer explizit Speicher bewegen. Hält TList auch Kapazität vor dem ersten Element frei, um effizient Operationen wie shift/unshift zu ermöglichen?
Nein. Es gibt lediglich den Bereich zwischen Capacity und Length am Ende der Liste.
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein

PascalDragon
Beiträge: 55
Registriert: Mi 3. Jun 2020, 07:18
OS, Lazarus, FPC: L 2.0.8, FPC Trunk, OS Win/Linux
CPU-Target: Aarch64 bis Z80 ;)
Wohnort: München

Re: Listen sind dynamische Arrays

Beitrag von PascalDragon »

MitjaStachowiak hat geschrieben:
Di 15. Sep 2020, 11:04
Hmm, die für ein Array reservierte Größe ist doch im Memorymanager auch immer eine 2-er Potenz, oder? Also wenn man nacheinander Elemente an den Array dran hängt, wird er nur bei jeder Verdopplung umkopiert, oder?
Nein, der Bereich ist nicht reserviert. Wenn zwischenzeitlich eine passende, andere Speicheranfrage reinkommt, dann wird die damit erfüllt. Sollte jedoch beim Vergrößern des Arrays noch Platz sein, so nimmt der Speichermanager diesen (hierfür wird nämlich ReallocMem verwendet, was genau dies behandelt).
FPC Compiler Entwickler

Antworten