Dynamische Arrays

tommie-lie · Beiträge: 4373 Ubuntu 7.10 "Gutsy Gibbon"

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*

_________________
Your computer is designed to become slower and more unreliable over time, so you have to upgrade. But if you'd like some false hope, I can tell you how to defragment your disk. - Dilbert

Motzi · Verfasst: Mo 31.01.05 21:46

Achso.. nachdem BenBE vorher was von MMFs geschrieben hat dachte ich du meinst auch MMFs.. na dann will ich nix gesagt haben..

_________________
gringo pussy cats - eef i see you i will pull your tail out by eets roots!

FabianS · Verfasst: 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 · Beiträge: 45 warmes flüssiges Blut D7 Prof, D8 Prof

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

markieren

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

_________________
FREIHEIT

UC-Chewie · Beiträge: 531 WinXP D5 Ent

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.

_________________
Egal wie dumm man selbst ist, es gibt immer andere, die noch dümmer sind

Socher · Beiträge: 45 warmes flüssiges Blut D7 Prof, D8 Prof

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

markieren

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!

_________________
FREIHEIT

reddevil · Beiträge: 23

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 · Beiträge: 23

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 · Beiträge: 1048 Erhaltene Danke: 4

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.

markieren

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.

markieren

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.

_________________
Nur die Menschheit ist arrogant genug, um zu glauben sie sei die einzige intelligente Lebensform im All. Wo nicht mal das nachhaltig bewiesen wurde.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme