Autor Beitrag
Heiko
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 3169
Erhaltene Danke: 11



BeitragVerfasst: Do 13.10.05 10:58 
Ist es irgendwie möglich die Zeiger eines dynamsichen Arrays zu verändern, so dass man nicht den gesamten Inhalt hin und her schieben muss im RAM?
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Do 13.10.05 11:22 
Du meinst, wenn du die Größe des Arrays veränderst? Sodass dann der neue Teil woanders im Speicher liegt als der Rest des Arrays? (Also nicht direkt dahinter)

Nein. Das ist nicht möglich. Denn dadurch würde der Vorteil der Arrays gegenüber Listen verlorengehen, dass man in konstanter Zeit (d.h. durch Berechnung der Speicherstelle des i-ten Elements anhand der Speicherstelle des 0-ten Elements) auf ein beliebiges Element zugreifen kann.

Wenn du häufig die Länge des Arrays neu setzen willst, dann empfiehlt es sich, vorher einmal die Länge entsprechend zu setzen und nach und nach einzufügen.
Ansonsten: Nimm eine Listenstruktur. Aber nicht etwas wie TObjectlist, denn das ist auch ein Array ;-)

_________________
We are, we were and will not be.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Do 13.10.05 12:17 
user profile iconGausi hat folgendes geschrieben:
Ansonsten: Nimm eine Listenstruktur. Aber nicht etwas wie TObjectlist, denn das ist auch ein Array ;-)

TList doch auch.

IMHO ist ein dynamisches Array, das seine Größe jeweils um den Faktor 1,7 steigert, wirklich schnell genug.
Die paar Bytes, die da kopiert werden sollten auf den GHz CPU doch keine 10ms extra Overhead bedeuten. Ich würde mir darüber kein grossen Gedanken machen.

Ich habe mal Geschwindigkeitsvergleiche zwischen einer einfachen TList, einer Hash-Liste (basierend auf einem dynamischen Array), einer verketteten Liste, Skiplist, Binary-Tree usw gemacht. Und, was kommt raus?
TList ist für < 200 Elemente optimal. Danach ist die Hashliste unschlagbar. Sie vergrößert sich um den o.g. Faktor und das Einfügen/Suchen ist eben immer optimal schnell.
Skiplisten sind erstaunlich schnell, und wenn es um eine sortiere Darstellung (Enumeration) der Elemente geht, ist die Skiplist das Mass aller Dinge.

Andere Datenstrukturen braucht man eigentlich nicht, jedenfalls meiner Meinung nach.

_________________
Na denn, dann. Bis dann, denn.
retnyg
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2754

SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
BeitragVerfasst: Do 13.10.05 12:24 
user profile iconHeiko hat folgendes geschrieben:
Ist es irgendwie möglich die Zeiger eines dynamsichen Arrays zu verändern, so dass man nicht den gesamten Inhalt hin und her schieben muss im RAM?

mach dir einfach eine kopie deines pointers und erhöhe den dann je nach anforderung

_________________
es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...
Heiko Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 3169
Erhaltene Danke: 11



BeitragVerfasst: Do 13.10.05 15:51 
Naja ich glaube ich muss mal meine Frage noch ein bissl genauer erläutern. z.B. Bei einem ListView gibt es ja für Items die Möglichkeit die zw. anderen Items per Insert einzufügen, bei arrays gibt es dagegen nicht die möglichkeit, sondern man muss alle Elemente um eins nach hinten verschieben ab der Einfügeposition, damit das Element dorthin passt. Wenn man das auf diese Variante macht, muss der Rechner ja den Inhalt immer weiter von einer Speicherposition im RAM zurnächsten verschieben, da sich jedoch der inhalt der einzelnen Elemente sich nicht ändert, halte ich das für sinnlos. Des wegen kam ich auf die Idee, dass man irgendwie dem Array ja nur sagen muss, dass das 5 Elemnt nicht mehr das erste ist, sondern das 6., das 6. das 7., ... . Und an der eingefügten Stelle (bei dem Bsp. die 5. ) den Zeiger auf die letzte Stelle des arrays zeigt. Ich hoffe es ist jetzt verständlicher. (das es sich dabei um ein dynamishces Array handelt, habe ich nur deswegen erwähnt, da man ja so eins ein bissl anders anfassen muss)
retnyg
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2754

SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
BeitragVerfasst: Do 13.10.05 15:54 
guck dir mal das pointerturorial von user profile iconmotzi an, da wird genau so eine liste umgesetzt.

_________________
es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Do 13.10.05 16:03 
Heiko: Du hast schon Recht, aber das tut nicht weh, die paar MByte mal eben zu verschieben. Viel wichtiger ist i.A. das Suchen nach einem Element (wozu braucht man sonst eine Liste). Das wird dann langsamer.

_________________
Na denn, dann. Bis dann, denn.
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Do 13.10.05 16:05 
Wie ich sagte, bei Arrays ist das nicht möglich. Wenn du das beschriebene Verhalten haben willst, musst du eine Listenstruktur nehmen.
Diese hat jedoch den Nachteil, dass man nicht beliebig auf die einzelnen Elemente zugreifen kann (wie bei Arrays), sondern im schlimmsten Fall die ganze Liste durchlaufen muss, bis man das gewünschte Element gefunden hat.

Edit: Nachtrag zum Thema suchen: In einem sortierten Array kann man wesentlich schneller suchen als in einer sortierten Liste! Zum suchen in einer Liste ist es völlig egal, ob die Liste sortiert ist, oder nicht. Bei nem Array kann man z.B. Binärsuche verwenden.

_________________
We are, we were and will not be.
Heiko Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 3169
Erhaltene Danke: 11



BeitragVerfasst: Do 13.10.05 16:07 
k, ich habe jetzt das mit AFPL Ghostscript 8.14 erstellte PDF-Dokument gefunden ;).

/Edit: Oder heißt das Teil "FreePDF XP Beta 18"? :gruebel:


Zuletzt bearbeitet von Heiko am Do 13.10.05 16:09, insgesamt 1-mal bearbeitet
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Do 13.10.05 16:08 
@Gausi: Schau dir mal die Skiplists an: gelinkte Listen mit sauschnellem Suchverhalten. Also stimmt die Aussage nicht, das Listen (Du meinst ja verkettete Liste) zum Suchen nicht geeignet sind.

_________________
Na denn, dann. Bis dann, denn.
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Do 13.10.05 16:23 
Hmm. Diese Datenstruktur ist mir zugegebenerweise bisher unbekannt. Um diese Struktur aber genauso perfomant beim Suchen zu machen, benötigt man soweit ich das jetzt kurz überblicke ungefähr log(N) zusätzlichen Speicherplatz um die ganzen Adressen der Sprungstellen zu speichern - Also das, was bei der Array-Suche berechnet wird. Normale Listen oder Baumstrukturen kommen da mit weniger Speicher aus.
Dass man durch erhöhten Speicheraufwand ggf. Zeit sparen kann, ist ja auch nicht unbedingt verwunderlich.

Trotzdem bleibt die Antwort auf die Frage hier: Nein, es geht nicht, weil man dann kein Array mehr hat ;-)

_________________
We are, we were and will not be.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Do 13.10.05 16:31 
@Gausi: Wird OT, aber pro Knoten (Item) sind es 16 pointer Overhead.
hier ein link
ftp.cs.umd.edu/pub/skipLists/

_________________
Na denn, dann. Bis dann, denn.
retnyg
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2754

SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
BeitragVerfasst: Do 13.10.05 16:37 
@alzaimar, sagtest du nicht grade dass du C hasst ? ;)
www.delphi-forum.de/...p;highlight=skiplist

_________________
es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Do 13.10.05 16:43 
Aha, die also auch:
www.delphipraxis.net...p;highlight=skiplist
danke trotzdem :wink:

_________________
Na denn, dann. Bis dann, denn.