Entwickler-Ecke :: Thema anzeigen

FabianS - So 30.01.05 16:34
Titel: Dynamische Arrays

Hi!

Ich habe folgendes Problem. Ich habe ein dreidimensionales Array.

Delphi-Quelltext

1:
2:
3:
4:
5:

TYPE TMatrix = Array[0..100, 0..100, 0..100] of SmallInt;

...

VAR Matrix: TMatrix;

wie kann ich jetzt ein dynamisches Array erzeugen, welches mir erlaubt zur Laufzeit des Programmes die Array-Werte zu setzen.

Ich möchte nämlich ein Array erstellen, welches 1024^3 werte speichern kann.

-Geht das, was ich vorhabe gar nicht über TYPE definitions?
-Sollte ich Pointer verwenden? Wenn JA, wie macht man das? (bitte hier genauere Erklärung)

Mit freundlichen Grüßen,
FabianS

Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt.

FabianS - So 30.01.05 16:58

habe etwas noch gefunden und folgendes erarbeitet:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

//folgendes erstellt ein array mit den dimensionen 1000^3, wenn ich alles richtig verstanden habe...

TYPE TMatrix = Array of Array of Array of Integer;

VAR Matrix: TMatrix;

Anzahl := 1000;

SetLength(Matrix,Anzahl);
for counter1 := 0 to (anzahl-1) do
  begin
    SetLength(Matrix[counter1],Anzahl);
    for counter2 := 0 to (anzahl-1) do
      begin
  SetLength(Matrix[counter1,counter2], Anzahl);
      end;
  end;

wäre das dann die art, ein dreidimensionales array zu erzeugen, welches die dimensionen der grösse der variable "Anzahl" hat?

Moderiert von raziel: Code- durch Delphi-Tags ersetzt.

Johannes Maier - So 30.01.05 17:47

Ich kenne mich damit auch nicht sehr gut aus, aber der Code zur Erzeugung stimmt schon.
Ich denke nur, dass es kein Array mit 1000^3 Dimensionen ist sondern eins mit 3 Dimensionen und dem "Fassungvermögen" (wie nennt man das?) 1000000000.
Achja, wenn du weißt, dass es 1024*1024*1024 groß sein soll, wieso machst du es dann nicht mit dem Code aus dem oberen Posting, oder hab ich das was falsch verstanden?

I.MacLeod - So 30.01.05 18:03

Nja... eigentlich sollte das so funktionieren:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

var
  foo: array of array of array of TBar;

...

SetLength(foo, 1024, 1024, 1024);

Aber du solltest auch bedenken, dass du so schon 1 GB an RAM verbrauchst, wenn du nur ein byte für jede Position reservierst (zzgl. Referenz- & Längenzähler).

tommie-lie - So 30.01.05 19:38

I.MacLeod hat folgendes geschrieben:

Aber du solltest auch bedenken, dass du so schon 1 GB an RAM verbrauchst, wenn du nur ein byte für jede Position reservierst (zzgl. Referenz- & Längenzähler).

Es muss nicht 1GB RAM sein, es reicht schon, wenn soviel logischer Speicher zur Verfügung steht (über das Swapping/Paging-System). Allerdings habe ich das eben mal ausprobiert, es dauert ewig, 1GB zu allokieren, selbst wenn man 512MB RAM hat, denn der Festplattenzugriff ist schon enorm. Allerdings kann man das Array nicht auf dem Stack erzeugen, denn der kann nur 16MB groß sein.
Mit Pointern und einem einzigen Speicherblock spart man zwar ein bisschen Overhead, aber bei einem Gigabyte Daten kommt es auf 8MB auch nicht mehr an...

Du solltest dir lieber Gedanken darüber machen, ob du wirklich solche Mengen brauchst, denn irgendwie tippe ich bei sowas immer auf Design-Flaw...

FabianS - So 30.01.05 23:45

wie könnte ich denn sonst eine solche enorme matrix realisieren?
ich meine ich könnte das array auch vom typ boolean machen. das wäre auch ok. würde das weniger speicherplatz nehmen?
oder wie gesagt: sollte/kann man da was mit pointer machen, wenn ja, wie?

mfg fabian

p.s. ich muss nur zwei verschiedene werte (0 oder 1) auf die punkte setzen können. wie würde ich denn dann das nur nehmen? also ich sehe ein, das der Integer-Typ eine schlechte wahl ist! ;)

Motzi - Mo 31.01.05 00:02

Also ein Array für 1024^3 Werte, wobei jeder Wert ein 4Byte Integer ist würde 4GB benötigen.. selbst wenn du anstatt eines Integers Booleans nehmen würdest würdest du auf 1GB kommen. Aber auch wenn der Adressraum eines Prozesses 4GB groß ist und du genügend RAM und eine ausreichend große Auslagerungsdatei hast wirst du wohl kaum einen 1GB großen Array verwenden können, da du (aufgrund der Fragmentierung) in deinem Adressraum kaum einen Platz finden wirst wo du dieses Riesen-Array in einem Stück ablegen kannst.

Wenn du nur 0 und 1 setzen können musst, warum arbeitest du dann nicht auf Bit-Ebene? Dann würde ein Integer-Array mit 32^3 Werten reichen, da du ja in jedem Integer 32-Werte speichern kannst..!

FabianS - Mo 31.01.05 00:45

mh..

@motzi
wie kann ich denn nur EIN bit reservieren? oder geht das gar net?

@BenBE
TFileStream sagt mir nix. könntest du ein beispiel machen, wie man FileStream nutzen könnte?

danke schonmal für die hilfe soweit..

na toll...

selbst wenn ich

Delphi-Quelltext

1:	array of array of array of 0..1

nutze, komme ich noch auf rund 120 MB RAM. hab aber nur 64MB ^^

mfg fabian

Moderiert von Motzi: Postings zusammengefügt.

Lossy eX - Mo 31.01.05 12:20

Das denke ich allerdings mal. Evtl wäre es gar nicht mal schlecht, wenn du uns genau erklären würdest was du damit vor hast? Vielleicht gibt es ja eine recht einfach Lösung für dein Problem. Ich denke nämlich mal nicht, dass du vor hast den gesammten Speicher zu belegen. Sondern eher nur ein Struktur zu haben in der du etwas ablegen und schnell drauf zugreifen kann, oder? Ist aber nur ne Vermutung.

tommie-lie - Mo 31.01.05 15:27

FabianS hat folgendes geschrieben:

nutze, komme ich noch auf rund 120 MB RAM. hab aber nur 64MB ^^

Das eine hat seit rund 15 Jahren mit dem anderen nichts mehr zu tun, dein Adressbereich umfasst 4GB, von dem dir unter Windows 2GB zur Verfügung stehen, egal wieviel RAM du hast. Das, was in den physischen Speicher nicht reinpasst, wird ausgelagert und landet in der pagefile.swp (unter Win98 hieß sie anders, ich meine irgendwas mit 386 im Namen, kann mich aber nicht mehr erinnern).
Wenn du Manuels Methode nachgehst, brauchst du "nur" 125MB Speicher, bei ausreichend groß konfiguriertem Pagefile klappt das wunderbar (wenn auch entsprechend langsam, weil die Festplatte nicht so schnell ist wie der RAM). Bens Methode ist faktisch Paging, nur daß du dich selbst drum kümmern musst. 4GB kriegst du unter Win98SE aber damit auch nicht hin, denn eine Datei, die 2GB groß ist, wirst du mit FAT und FAT32 vergeblich versuchen, anzulegen ;-)

Zu Manuels Methode:
Die Umsetzung kannst du mit der logischen Operation and machen. Die nimmt als Operanden zwei Masken (in Form von ordinalen Werten) an und gibt dir eine AND-Verknüpfung zurück. Wenn du nun gegen ein Muster prüfst, bei dem nur ein einziges Bit gesetzt ist, kannst du anschließend Prüfen, ob die zurückgegebene Verknüpfung 0 ist, oder nicht. In ersterem Fall ist das Bit nicht gesetzt, in letzterem Fall schon.

tommie-lie - Mo 31.01.05 19:45

Motzi hat folgendes geschrieben:

tommie-lie hat folgendes geschrieben:

Wenn du Manuels Methode nachgehst, brauchst du "nur" 125MB Speicher

Falsch... 32^3 * 4 = 131072 = 128kb - ist also sehr human vom Speicherverbrauch her! ;)

Er will 1024^3 Elemente speichern, sind also 1 Milliarde (1073741824) Werte, die alle in einem einzigen Bit dargestellt werden können. Also haben wir 1Mrd / 8 Byte = 134217728, und das sind 128 Megabyte (call it MibiByte, wenn du willst :puke:).

BenBE - Mo 31.01.05 20:24

tommie-lie hat folgendes geschrieben:

Bens Methode ist faktisch Paging, nur daß du dich selbst drum kümmern musst. 4GB kriegst du unter Win98SE aber damit auch nicht hin, denn eine Datei, die 2GB groß ist, wirst du mit FAT und FAT32 vergeblich versuchen, anzulegen ;-)

Jip. wenn man's richtig proggt, ist die Speichergröße aber praktisch nur noch vom Festplattenplatz abhängig. Dazu muss man dieses Paging aber entsprechend in mehrere Files aufteilen, wass man sowieso machen sollte. Außerdem bietet sich in dem Zusammenhang die Verwendung von MMFs an, da dann das lästige Seeken in der Datei von Windows erledigt wird.

tommie-lie - Mo 31.01.05 20:55

BenBE hat folgendes geschrieben:

Jip. wenn man's richtig proggt, ist die Speichergröße aber praktisch nur noch vom Festplattenplatz abhängig.

Ist es beim Windows-Paging auch. Nur frage ich mich gerade, was Windows macht, wenn die Paging-Datei größer als 2GB wird... logisch wäre es, eine zweite Datei zu erzeugen, aber ob Microsoft das auch als logisch empfunden hat? :gruebel:

tommie-lie - Mo 31.01.05 21:41

Motzi hat folgendes geschrieben:

tommie-lie hat folgendes geschrieben:

Nur frage ich mich gerade, was Windows macht, wenn die Paging-Datei größer als 2GB wird...

Ähm.. wie willst du denn eine 2GB große MMF erzeugen..? Die MMF wird ja schließlich in den Adressraum gemappt und da hast du bekanntlich nur Zugriff auf 2GB... :gruebel:

Ich rede nicht von MMFs, sondern vom Pagefile ;-) Es existiert ja nicht pro virtuellem Adressraum (also pro Prozess) auch ein Pagefile, es gibt vielmehr eine Zuordnung von Prozessen und deren Pages zu Pages aus dem Pagefile, und eigentlich müsste es möglich sein, mehrere Pagefiles anzulegen. Nur ob Microsoft das auch gemacht hat, weiß ich nicht, und ich habe nicht vor, es auszuprobieren *g*

FabianS - Mo 31.01.05 23:39

Nun um zu beschreiben was ich machen will mit meinem Programm.
Ich erschaffe eine Matrix, dessen größe variabel sein soll. nun verteile ich per zufall auf alle koordinaten gesehen 2%. das heißt 2% aller koordinaten haben nachher den wert 1. alle per zufall gesetzt! nebenbei wird überprüft, das jede 1 zu einer anderen einen abstand n hat.

da ich eine matrix von mind. 1000^3 koordinaten brauche, ist das leider ein enormer speicherverbrauch.

wenn euch etwas besseres einfällt, als meine bisherige methode, sagt es bitte. es ist das erste mal das ich mit array's in solcher form arbeite.

jemand sagte mal etwas von MMF's? oder so...? und TFileStream...?
wie genau wollt ihr das realisieren? da war auch ein beispiel, aber verstanden habe ich es noch nicht..

außerdem.. ein weiteres problem, ich will nachher alle koordinaten in dieser matrix in eine MySql-DB packen. Also alle koordinaten, wo der wert auf 1 gesetzt wurde....

hoffe das war verständlich, sonst fragt bitte nochmal nach!

mfg fabian

Socher - Di 01.02.05 00:09

Eine einfache Lösung wäre vieleicht eine typeisierte Datei:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

type
    D3Rec = record
    x,y,z:real;
    end;
..
..
var D3:file of D3rec;

..
..
procedure TForm2.Label1Click(Sender: TObject);
begin
assignfile(D3File,'c:\zip\ZKoordinaten.dat');
rewrite(D3File);
for i:=1 to 3000 do
    begin
    D3.x:=random(1000)/pi;
    D3.y:=random(1000)/pi;
    D3.z:=random(1000)/pi;
    write(D3File,D3);
    end;
end;

Moderiert von raziel: Delphi-Tags hinzugefügt

UC-Chewie - Di 01.02.05 00:36

OK, 2% aller Felder sind belegt?
Das hieße, von 1 Mrd Felder sind es 20 Millionen.
Sind diese über das ganze Gitter verteilt oder gibt es Häufungspunkte?
Falls letzteres zutrifft, könntest du deine Datenstrukturen so aufbauen, dass du zunächst mal eine Blöckgüße von z.B. 100 festlegst, d.h. du hast erstmal 10x10x10 Felder. Diese sind Referenzen auf eine weitere Datenstruktur, die dann genauer ist usw. Befindet sich kein Element in dem Block, wird ein nil-Zeiger gespeichert.

Durch eine geeignete Wahl der Blockgrößen und Anzahl der Verschachtelungsebenen kann man so Speicher sparen, vorausgesetzt, wie gesagt, man hat Häufungen. Sonst braucht man u.U. noch mehr Speicher....

Oder du indizierst nur zwei Dimensionen und speicherst dann eine dynamisch große Liste, je nachdem wie viele Punkte in der Reihe liegen. Dann musst du nur noch 1000x1000xn (wobei n die Anzahl der Elemente in der Zeile ist) Elemente speichern.

Oder denk dir irgendeine verkettete Struktur mit Speichern der Position aus....

Es gibt sehr viele verschiedene Möglichkeiten, zu beachten ist aber, dass in dem meisten Fällen eine Verringerung des Speicheraufkommens mit eine rErhöhung der Komplexität einhergeht.

Socher - Di 01.02.05 00:50

Das wären dann mit dieser Datei Rund 350 MB auf deiner Festplatte

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

for i:=1 to 20000000 do
    begin
    D3.x:=random(1000)/pi;
     D3.y:=random(1000)/pi;
      D3.z:=random(1000)/pi;
    write(D3File,D3);
    end;

D3 entspricht bei Real 18 Bytes pro Datensatz (Koordinate)

Alle Daten 1000^3 würden ungefär so aussehen.
1000^3 * 3 * 6 Bytes = ca. 17000 MB = 17 GB - ein Haufen Holz

Hoffentlich habe ich jetzt keinen Blödsinn gerechnet?

Moderiert von raziel: Delphi-Tags hinzugefügt. Nächstes Mal bitte selbst dran denken :mahn: Danke!

reddevil - Di 01.02.05 01:18
Titel: öhm..

vielleicht solltest du nur speichern wo eine "1" steht (da nur 2% Einsen drin sind)
und wie meine Vorgänger rechne auch ich mal ein bischen rum:
1024^3 * 2% = 21 Mio = Anzahl der Einsen die zu speichern wären
zu jeder Eins müsstest du speichern wo die Eins in deiner Matrix steht dazu nehmen
wir erstmal 3 integers (für jede Richtung/Dimension einer) und wir kommen auf
21 Mio * 3 * 4Byte = 252MB
Das ganz noch geeignet sortieren damit du auch realtiv schnell rausfinden kannst
ob ein Eintrag gesetzt ist oder nicht
In dem obigen Fall würde wohl Delphi für dich "alles" übernehmen (z.b. wenn du einen datentyp der aus 3 integers besteht definierst und den in ein array mit 21Mio einträgen packst (wobei..wenn ich so drüber nachdenke ist das für delphi wohl ein zu großes array)

Wenn die 252MB zuviel sind sehe ich noch die Möglichkeit anstelle von 3 integers pro Eins nur einen zu verwenden (vorrausgestezt du brauchst maximal 1024 "Einträge pro Dimension" bzw "10bits pro Dimension"). Du müsstest dann die erste Dimension in die ersten 10bits des Integers packen (die zweite Dim. in die nächsten 10 und die dritte Dim. analog in die nächsten 10). Das ganz wäre sehr programmieraufwendig (zumindest für mich) und recht langsam aber du bräuchtest "nur" 21Mio * 4 Byte = 84MB Speicher

red

reddevil - Di 01.02.05 10:04

achja vielleicht noch ne idee
du legst ein zweidimensionales array mit 1024 Pointer-einträgen pro Dimension
Das ergibt schonmal 4Byte*1024^2 = 4MB
Der Pointer an Position (x,y) im array zeigt dann auf ein dynamisch erzeugtes Array in welchem vom Punkt (x,y,z) nur die z-koordinate gespeichert wird (die x,y-koordinate ergibt sich ja aus der Position des Pointers im array) und das entsprechend für alles Punkte die in der ersten und zweiten Koordinate (x,y) haben und wo eine Eins stehen soll..
damit kommt man dann auf 21Mio*4Byte+4MB = 88MB
wobei hier der Programmieraufwand im Vergleich zu den anderen eher gering ist...

(ähnlich wie oben kannst du in einem 4Byte Integer auch wieder bis zu 3 z-koordinaten speichern..dann würden 30MB reichen aber der Aufwand wäre wieder groß)

red

Lossy eX - Di 01.02.05 10:47

Ich persönlich würde so auch sagen, dass du die Daten am Besten in einem 2 Dimensionalem Array ablegst und dann entsprechend in der dritten Dimension dann lediglich eine Liste der Elemente für diese Stelle beinhält.

Eine alternative zu einem 4Byte Integer wäre zum Beispiel ein 2 Byte Integer (ja auch so etwas gibt es). ;-) Also entweder ein DWord oder Smallint. Dann hätte man keinen so großen Verwaltungsaufwand. Keinen so großen Speicherverschmiss und man könnte die Dimensionen auf 64000^3 erweitern. Für den Fall, dass aber 1024 das absolute Maximum für die Matrixgröße wäre würde ich auch vorschlagen, dass du nur ein 4Byte integer benutzt. Das extrahieren ist zwar ein wenig Komplizierter als ein Integer abfragen aber noch keines Wegs so kompliziert.

Das kann man mit den Operatoren and und shr sehr einfach und schnell lösen. Shr rotiert eine Zahl um die angegebene anzahl an Bits. Und and lässt nur ein bestimmtes Bitmuster durch. $3FF = 1023. Also die ersten 10 Bits.

Delphi-Quelltext

1:
2:
3:

X := Wert and $3FF;
Y := Wert shr 10 and $3FF;
Z := Wert shr 20 and $3FF;

Zusammenbauen würde so gehen. shl rotiert auch aber nach links.

Delphi-Quelltext

1:	Wert := (Z shl 20) or (Y shl 10) or X;

PS: Bei solchen Datenmengen wäre es vielleicht sogar eine Überlegung wert ob es nicht sinnvoller ist die Daten gleich in die Datenbank zu schreiben? Eine Datenbank kann durch diverse Indizes schon einiges optimieren. Aber die Daten wären halt komplett auf der Festeplatte gespeichert. Das würde allerdings nur funktionieren, wenn du nicht so häufig auf die Daten zugreifen musst. Sonst schlägt sich das negativ in der Geschwindigkeit nieder.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!