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
Listen sind dynamische Arrays
-
- Beiträge: 3444
- 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
Zuletzt geändert von mschnell am Di 15. Sep 2020, 14:11, insgesamt 1-mal geändert.
-
- Beiträge: 1909
- Registriert: Di 23. Sep 2014, 17:46
- OS, Lazarus, FPC: Win10 | Linux
- CPU-Target: x86_64
Re: Listen sind dynamische Arrays
In der C++ STL werden bäume als arrays implementiert, um sich die cache lokalität und schnellen zugriffszeiten zunutze zu machen
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
-
- Beiträge: 830
- 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
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.mschnell hat geschrieben: ↑Mo 14. Sep 2020, 10:20Wenn man einen Kompromiss zwischen Einfüge- und Lese- Effizienz will, muss man eine (Memory-) Datenbank nehmen.PascalDragon hat geschrieben: ↑Fr 11. Sep 2020, 16:36Weil 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).
FPC Compiler Entwickler
-
- Beiträge: 732
- Registriert: Di 23. Aug 2016, 14:25
- OS, Lazarus, FPC: Windows 11
- CPU-Target: 64Bit
- Wohnort: Berlin
Re: Listen sind dynamische Arrays
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 :
Siro
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.
Grüße von Siro
Bevor ich "C" ertragen muß, nehm ich lieber Lazarus...
Bevor ich "C" ertragen muß, nehm ich lieber Lazarus...
-
- Lazarusforum e. V.
- Beiträge: 394
- Registriert: Sa 15. Mai 2010, 13:46
- CPU-Target: 64 bit
- Kontaktdaten:
Re: Listen sind dynamische Arrays
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?
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?
-
- Lazarusforum e. V.
- Beiträge: 3158
- 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
Nein. Es gibt lediglich den Bereich zwischen Capacity und Length am Ende der Liste.MitjaStachowiak hat geschrieben: ↑Di 15. Sep 2020, 11:04Auß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?
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein
-
- Beiträge: 830
- 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
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).MitjaStachowiak hat geschrieben: ↑Di 15. Sep 2020, 11:04Hmm, 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?
FPC Compiler Entwickler