Speicherzugriffsproblem

[Callisto]

Ich habe ein Problem das ich in Delphi für einen Array Speicher zuweise (Globalalloc, Virtualallic, getmem) und nach der Benutzung auch wieder frei gebe. Einmal wird der Array mit Daten befüllt und ein zweites Mal ausgelesen. Das Problem ist nun dass das Programm dauernd mit Speicherzugriffsfehern abstürzt. Einmal geht er komplett durch die Routine und hängt sich beim zweiten Mal auf, einmal gleich am Anfang etc. Es ist also nicht vorhersehbar wann.
Ich denke das auf einmal der zugewiesene Speicher "weg" ist, aber wie kann ich das beheben?
Ich habe keine Ahnung. Kann man den Speicherbereich irgendwie schützen?

[Whiz-zarD]

Delphi besitzt doch dynamische Arrays, wieso benutzt du diese nicht?

Code (Delphi):

 
procedure SetLength ( var ArrayToChange : ArrayType; NewLength : Integer ) ;
 

Damit kann man die Größe eines Arrays bestimmten.
Also setLength(meinArray, 10); vergrößert/verkleinert das Array auf 10 Elemente.

Um den reservierten Speicher wieder freizugeben, muss man die Größe auf 0 setzen. Also setLength(meinArray, 0);.

[Callisto]

Wollt nur sagen das es mit den dynamischen Arrays erstmal geklappt hat. Danke!
Scheinen die anderen Varianten wohl für 60k++ Arrays nicht ausgelegt zu sein.

[Whiz-zarD]

Naja, bei solchen großen Datenmengen ist ein Array auch sehr ineffizient.
Da würde ich dir mal vorschlagen, dass du dich mit Hashtabellen oder balancierte Bäume auseinandersetzt und diese implementierst, sofern Delphi dafür keine eigene Klasse parat hat.

[Mog]

Naja, bei solchen großen Datenmengen ist ein Array auch sehr ineffizient.
Da würde ich dir mal vorschlagen, dass du dich mit Hashtabellen oder balancierte Bäume auseinandersetzt und diese implementierst, sofern Delphi dafür keine eigene Klasse parat hat.

...

Du weißt, wie die gängigen HashMaps implementiert werden, oder?^^

[Callisto]

Schon klar, aber das Programm (DLL) habe ich nicht selbst geschrieben. Hab mir nur den Quellcode besorgt um paar Bugs zu beseitigen, da der richtige Autor keine Zeit dafür hat.
Und soviel will ich da auch nicht umschreiben.

[Mog]

Naja, bei solchen großen Datenmengen ist ein Array auch sehr ineffizient.
Da würde ich dir mal vorschlagen, dass du dich mit Hashtabellen oder balancierte Bäume auseinandersetzt und diese implementierst, sofern Delphi dafür keine eigene Klasse parat hat.

...

Du weißt, wie die gängigen HashMaps implementiert werden, oder?^^

...

Meh, das kann ich so wirklich nicht stehen lassen. :/ http://imgs.xkcd.com/comics/duty_calls.png greift gerade komplett bei mir.


Was ist die Idee einer Hashmap?

Wir greifen auf unsere Daten zu, in dem wir den Key hashen. Durch den Hash-Wert des Keys, können wir sagen, wo die Daten in unserem Speicherbereich liegen müssen. Auf diesen Speicherbereich müssen wir nun in konstanter Zeit zugreifen können.
Da nur die wenigsten Hashes (und die, die wir in einer Hashmap verwenden ohnehin nie) perfekt sind, können Daten natürlich unter Umständen auf der selben Position liegen müssen. Hier muss man dann mit diversen Verfahren die Kollision umgehen. (Buckets, etc.)

Insofern wir hier nicht in konstanter Zeit auf die Daten selber zugreifen könnten, hätte es keinen Sinn überhaupt eine HashMap zu implementieren: WIr wollen schließlich viele Vergleiche ersparen, und ganze Teile unserer Daten beim Suchen überspringen können, während wir nach einen Key suchen. Wenn wir beispielsweise nur seriell zugreifen könnten, hätten wir hier nur eine idiotische Liste, bei der wir uns evtl. ein paar Schlüsselvergleiche sparen. Trotzdem müssten wir die Liste idiotisch durchgehen, bis wir den passenden Eintrag gefunden haben.

Kurzum: Die einzigen sinnvollen Datenstrukturen, die hinter der HashMap liegen, sind Arrays, oder Files.

Das Array muss noch dazu mindestens genau so lang sein, wie es Keys gibt, oder eben länger. Wohl gemerkt ist die Wahrscheinlichkeit, dass das unterliegende Array länger ist, sogar recht hoch.

Auch, wenn Arrays nicht gerade so groß werden sollten, wenn es sich vermeiden lässt, sind deine Gegenvorschläge schlichtweg nicht die richtigen Mittel. Vorallem wissen wir nicht einmal die notwenidgen Informationen bekommen, anhand denen wir beurteilen können, was hier evtl. besser wäre, als ein Array.

Kurzum: Insofern er nicht in seinen Daten gerade in erster Linie suchen sollte, ist ein simples Array sicher die bessere Datenstruktur, als eine HashMap.

[Whiz-zarD]

Ok, es fehlt ein "z.B.".
Hashtabellen und balancierte Bäume sollten nur Beispiele sein, um eine effizientere Datenstruktur zu basteln. Delphi hat seine dynamischen Arrays auch nur als eine einfach verkettete Liste implementiert, die ebenfalls ständig durchgegangen werden muss. Sie werden halt nur als normale Arrays behandelt, weil der Compiler automatisch an den Stellen, zur Benutzung der Liste, Code einfügt.

[Ineluki]

Wo steht bitte, dass Delphi Dynamische Arrays als Listen implementiert ?
Soweit ich weiss, sind das effektiv Pointer auf zusammenhaengende Datenbereiche mit ein paar Zusatzinformationen. Und wenn man das Array vergroessern/verkleinern muss, wird halt ein entsprechend groesserer/kleinerer Datenblock alloziiert, die Daten kopiert und der alte Datenblock freigegeben oder, falls das effizienter ist, ein neuer Datenblock hinzugefuegt, und die Pointer der Datenbloecke in einer Liste verwaltet, bis sie bei einer spaeteren Operation zusammengefuehrt werden. Trotzdem hast du zu jeder Zeit einen Zugriff auf ein beliebiges Element in const time. *schulterzuck*