Das deutsche QBasic- und FreeBASIC-Forum

[OneCypher]

Kann man ein dynamisches Array innerhalb eines UDTs erstellen?

Mit REDIM funktioniert es ja schon mal nicht... sagt ja auch schon die Referenz.

Aber vielleicht weiss einer nen kniff wie man es doch hinbekommen kann...

[28398]

Mit nem any ptr und dann rumcasten?

[Sebastian]

Hallo,

ich würde statt eines Arrays in diesem Fall eine einfach verkettete Liste benutzen und deren Startzeiger in den UDT aufnehmen. Das ist vermutlich die einfachste Variante, wenn nicht unbedingt die Datenstruktur Array gebraucht wird.

Viele Grüße!
Sebastian
_________________

Die gefährlichsten Familienclans | Opas Leistung muss sich wieder lohnen - für 6 bis 10 Generationen!

[OneCypher]

@ Sebastian: Was meinst du mit verkettete liste?

[Sebastian]

Hallo,

auf FreeBASIC-Portal.de gibt's ein Tutorial zum Thema: http://www.freebasic-portal.de/index.php?s=tutorials&id=37&seite=1

Ansonsten: http://www.google.de/search?hl=de&q=verkettete+liste&btnG=Google-Suche&meta=

Viele Grüße!
Sebastian
_________________

Die gefährlichsten Familienclans | Opas Leistung muss sich wieder lohnen - für 6 bis 10 Generationen!

[Elektronix]

Verkettete Listen sind dynamische Datenstrukturen, die zur Laufzeit im Speicher erstellt werden. Jedes Element enthält einen Zeiger auf eine nachfolgendes Element, über spezielle Zugriffsfunktionen kann man Werte anfügen und abfragen oder löschen.

Hat den Vorteil, daß man den Listenkopf in anderen Datenstrukturen unterbringen kann und dann darüber auf alle Daten der Liste zugreifen kann, unabhängig von der Länge der Liste.
Zu beachten ist, daß die Speicherstellen für die Liste zur Laufzeig per allocate angefordert werden. Die müssen also am Ende mit Deallocate wieder freigegeben werden, sonst gibt es Speicherleaks. In dem Beispiel gibt es dafür extra Funktionen.

http://www.freebasic-portal.de/index.php?s=tutorials&id=37&seite=1
als Beispiel hier:
http://www.freebasic-portal.de/index.php?s=fbporticula&mode=show&id=482
_________________
Und die Grundgebihr is aa scho drin- DOS is jo nett.

[OneCypher]

Sehr geil! .. danke, da hab ich in dem zusammenhang noch gar nicht gedachtt!!!

*verneig*

[OneCypher]

Ok, ich weiss ich nerve.. aber in dem beispiel aus dem freebasic-portal kann ich nicht nachvollziehen wie man das ende der kette ermittelt..

Sie schreiben in etwa:

[volta]

[OneCypher]

Ah ok, das ergibt sinn

[Sebastian]

Hallo,

ich hab den Fehler korrigiert. Das php-Script muss die Ungleich-Vergleichsoperatoren verschluckt haben. Seltsam ist dabei nur, dass die übrigen spitzen Klammern <, > einzeln vorhanden waren und nur die <> gefehlt haben...

Viele Grüße!
Sebastian
_________________

Die gefährlichsten Familienclans | Opas Leistung muss sich wieder lohnen - für 6 bis 10 Generationen!

[ThePuppetMaster]

Es gibt noch einen kleinen Trick, um die zugriffszeiten auf eine verkettete Liste zu erhöhen. Auserdem kann man dadurch eine Indizierung erreichen.

Man erstellt zusätzlich zu der LinkedList einen Speicher, der ausschliesslich Integer PTRs speichert. Hat man 10 Einträge erstellt, stehen die Startadressen zu den jeweiligen Elementen nicht nur am ende eines jeden Elementes, sondern auch in der Zusätzlichen Tabelle.

Möchte man jetzt auf element 5 von 10 zugreifen, rechnet man einfach SizeOf(Integer Ptr) * 5 und erhält dadurch die Startadresse zu dem jeweiligen Element.

Zwar wird dadurch die Liste etwas aufwendiger, jedoch beschleunigt und vereinfacht sich der zugriff auf Listeneinträge durch vortlaufende Indexnummern enorm. Beim Löschen wirds dann etwas Langsamer, was man allerdigns mit MoveMem geschickt beschleunigen kann.


MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ]

[Mao]

[ThePuppetMaster]

Hä? was meinst du? Verstehe deine Aussage nicht.


MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ]

[Lutz Ifer]

Also.... ich weiß ja nicht wie's dir geht, aber ich mag meine Zugriffszeiten eher klein und möchte es vermeiden,

[MisterD]

hugh! oder du pflanzen baum! hugh!
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra

[ThePuppetMaster]

Neu erstellt werden?!? .. Was muss da grossartig neu erstellt werden?! .. das is n MoveMem und damit hat sich die "neuerstellung" schon. und die paar µs die das braucht, wirken sich negativ auf erstellen oder lsöchen von einträge aus. der zugriff auf element ebeschleunigt sich durch indexnummern gewaltig, im vergleich zu einer verketteten liste, da die Speicheradressen jedes elements im vorherigen steht .. sprich .. man muss alle elemente durchlaufen, um das zu finden,w as man sucht! ...

Mit einem 2ten array (im speicher) kann man das auffinden eines Pointers zum jeweiligen Element durch eine mathematische rechnung drastisch verkürzen. WO zum geier soll da was langsam sein?!?


MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ]

[MisterD]

es ist egal wie viele optimierungen oder pseudooptimierungen du an deiner liste machst, es bleibt ne liste, die kriegst du nich aus O(n) für wahlfreien zugriff raus, das geht nur mit hashtables oder bäumen..
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra

[Lutz Ifer]

Lieber Puppetmaster.

Stelle dir eine Verkette Liste mit sagen wir 1.000.000 Einträgen vor. Soweit so gut, so scheusslich groß.

Lösche bitte Eintrag Nummer 42, und füge einen Eintrag zwischen Nummer 5 und 6 ein.

42 löschen:
Folgepointer von 41 auf Position von 43 setzen, Element 42 löschen. Jetzt geht der Spaß mit deinem Index-Array los: von 42 bis 1.000.000 muss jeder Wert durch seinen Folgewert ersetzt werden. Meinetwegen, geht noch "relativ" schnell, mit Deinem MemMove lösbar. Wenn Du das aber sauber lösen willst, musst Du auch noch das Array verkleinern. Reallocate Preserve? Macht auch nichts anderes, als ein neues Array erstellen, dass die gewünschte Größe hat, und alle Werte kopiert, dann das alte löscht. Da wirds haarig. Meinetwegen, auch hier wieder "MemMove", geht "relativ" schnell - wir haben insgesamt knapp 2 MB im Speicher verschoben, und zwischenzeitlich (in der Übergangsphase) fast den doppelten Speicher deines Indexarrays belegt.

Nach 5 einfügen:
Neues Element erzeugen, Folgepointer auf Nummer 6 setzen, Folgepointer von Nummer 5 auf neues Element. Jetzt geht erneut der Spaß mit Deinem Index-Array los - ich spar's mir, es nochmal zu schreiben. Wieder 2 MB durch den Ram schieben, und neue Array erzeugen.

Wenn du Spaß dran hast, vergleiche mal dein mem-ge-movte array-indizierte Version mit der Normalen. Sicher mag der lesende Zugriff auf dein Konstrukt schneller sein - aber ne Linked List wird nicht nur gelesen, sonst könnte ich gleich nen Array nehmen, und eben keine LL. Also, fülle mal bitte eine "normale" LL und "deine" LL mit 1.000.000 Einträgen, und sag' mir, was dabei rauskommt.

Gruß
Lutz Ifer

ps: ich bin der Teufel, ich pflanze keine Bäume!
_________________
Wahnsinn ist nur die Antwort einer gesunden Psyche auf eine kranke Gesellschaft.

[MisterD]

du brauchst aber doch brennholz für deine höllenfeuer!
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra