Problem: Script braucht zu viel Arbeitsspeicher. Bräuchte Tips.

[Jens Hopp]

Hallo.

Ich habe ein paar Fragen zur Optimierung des Speicherplatzbedarfs eines PHP-Scripts.
Ich wäre sehr froh, wenn mir die PHP-Spezies unter Euch ein paar Tips geben könnten.

Ich habe ein Script geschrieben, das augenscheinlich zu viel Speicherplatz verbraucht.

Jetzt würde ich es gerne optimieren, weiß aber noch nicht genau, wo ich am besten anfange.

Daher hier ein paar Details.

Ich habe eine Baumstruktur entwickelt, in der sich viele Objekte befinden, die in einer parent-child-Beziehung zueinander stehen.

Das ganze will ich mal kurz schematisch beschreiben.

Alles beginnt mit einem root-Objekt:

<?
$root = new rootobj();
?>

Darunter befinden sich in mehrdimensionalen assoziativen Arrays Objekte verschiedener Klassen nach folgendem Muster:

<?
$root->obj['xyz']['abc']['bnm'] = new Klasse_1();
$root->obj['xyz']['mno']['jkl'] = new Klasse_2();
$root->obj['asd']['qwe']['mno'] = new Klasse_3();
u.s.w.
?>

Diese Objekte haben auch wieder untergeordnete Objekte:

<?
$root->obj['xyz']['abc'][1]->obj['sdf']['yxc']['xcv'] = new Klasse_4();
$root->obj['xyz']['abc'][1]->obj['wer']['xcv']['qwe'] = new Klasse_5();
u.s.w.
?>

Das ganze kann sich auch noch tiefer verschachteln.

z.B.
<?
$root->obj['xyz']['abc'][1]->obj['wer']['xcv']['qwe']->obj['rtz']['tzu']['zui'] = new Klasse_6();
?>

Damit die untergeordneten Objekte ihr Parent-Objekt kennen, haben diese alle noch Referenzen auf das Parent-Objekt:

z.B:
<?
$root->obj['xyz']['abc'][1]->obj['sdf']['yxc']['xcv']->parent = &$root->obj['xyz']['abc'][1];
?>

Auch kann es weitere Referenzen auf Objekte in dem Baum geben, die sich in einem ganz anderen Zweig befinden:

z.B.
<?
$root->obj['xyz']['abc'][1]->obj['sdf']['yxc']['xcv']->referenzwoandershin =
&$root->obj['xyz']['abc'][1]->obj['wer']['xcv']['qwe'];
?>

Wenn nun dieser Baum so richtig dick wird, weil viele Objekte definiert sind, dann wird das ganze sehr speicherintensiv und langsam.

Jetzt meine Überlegungen, womit das zu tun haben könnte:

1. assoziative Arrays
   Könnte es sein, daß die assoziativen Arrays viel mehr Platz verbrauchen, als "normale" Arrays?
   Wäre es also günstiger, statt
   <?
   $root->obj['xyz']['abc']['bnm'] = new Klasse_1();
   ?>
   die Variante
   <?
   $root->obj[1][3][5] = new Klasse_1();
   ?
   zu wählen?
   (Und muß man dabei darauf achten, daß in jeder Dimension von 0,1,2... beginnend alle Zahlen vertreten sind, oder geht auch z.B. 5,34,623...)

2. Verschachtelung der mehrdimensionalen Arrays
   Könnte es sein, daß die verschachtelung der Arrays als solche eine Rolle spielt?
   Wäre es günstiger, statt
   <?
   $root->obj['xyz']['abc']['bnm'] = new Klasse_1();
   ?>
   die Variante
   <?
   $root->obj['xyz_abc_bnm'] = new Klasse_1();
   ?>
   zu wählen?

3. Objekte als "value" in Arrays
   Könnte es sein, daß es überhaupt ungünstig ist, Objekte in Arrays zu stecken?
   Wäre es günstiger, statt
   <?
   $root->obj['xyz']['abc']['bnm'] = new Klasse_1();
   ?>
   die Variante
   <?
   $root->obj_xyz_abc_bnm = new Klasse_1();
   ?>
   zu wählen?

4. Referenzen
   Ist die hohe Zahl von Referenzen, die z.B. durch die parent-child-Beziehung entstehen relevant?
   Wäre es günstiger statt der wirklichen Abbildung eines Objektbaumes nur die "Adressen" (Arraynamen) der Objekte zu speichern?
   Also statt
   <?
   $root->obj['xyz']['abc'][1]->obj['sdf']['yxc']['xcv'] = new Klasse_4();
   ?>
   lieber
   <?
   $root->obj['xyz']['abc'][1] = new Klasse_1();
   $root->obj['sdf']['yxc']['xcv'] = new Klasse_4();
   $root->obj['xyz']['abc'][1]->child = 'sdf_yxc_xcv';
   $root->obj['sdf']['yxc']['xcv']->parent = 'xyz_abc_1';
   (oder so ähnlich)
   ?>

5. Verschachtelung von Objekten
   Durch die Nutzung von $root und Unterordnung aller Objekte unter dieses Rootobjekt kann ich durch
   <?
   global $root;
   ?>
   in allen Funktionen auf alle vorhandenen Objekte zugreifen. Das ist recht günstig.
   Ist es aber vielleicht trotzdem besser, auf $root zu verzichten und Objekte im allgemeinen Namensraum zu definieren?
   Es könnte ja z.B. sein, daß mit jedem
   <?
   global $root;
   ?>
   der ganze Baum wieder innerhalb der Funktion noch einmal erzeugt wird.
   Wäre es also günstiger, statt
   <?
   $root->obj['xyz']['abc']['bnm'] = new Klasse_1();
   $root->obj['xyz']['mno']['jkl'] = new Klasse_2();
   $root->obj['asd']['qwe']['mno'] = new Klasse_3();
   ?>
   lieber die Variante
   <?
   $obj['xyz']['abc']['bnm'] = new Klasse_1();
   $obj['xyz']['mno']['jkl'] = new Klasse_2();
   $obj['asd']['qwe']['mno'] = new Klasse_3();
   ?>
   zu wählen und dann innerhalb einer Funktion z.B. mit
   <?
   global $obj['xyz']['abc']['bnm'];
   global $obj['xyz']['mno']['jkl'];
   ?>
   die benötigten Objekte direkt anzusteuern?

gibt es vielleicht noch mehr Fallen?
<? ???? ?>

Wer bis hierhin durchgehalten hat: DANKE DANKE DANKE!

Wenn ich jetzt wissen würde, ob ich auf dem richtigen Weg bin - und wo ich anfange...
Wenn jemand Erfahrung mit solchen Problemen hat, wären ein paar Hinweise und Ergänzungen super.

Vielen Dank und viele Grüße
Jens Hopp

[Sven Rautenberg]

Moin!

Ich habe ein Script geschrieben, das augenscheinlich zu viel Speicherplatz verbraucht.

Hast du mal überschlagsmäßig nachgedacht, wieviel Speicher deine Objekte im Speicher belegen?

Nur so als Beispiel nehmen wir mal ein Integer-Array:
Jeder Wert belegt 4 Byte.

Ein Array 1..100 belegt also 400 Byte. Billig.
Ein Array 1..100,1..100 belegt schon 100x100x4 Byte, also 40000 Byte.
Ein Array 1..100,1..100,1..100 belegt 4.000.000 Byte, ungefähr 4 Megabyte.

Du hast eine Struktur gewählt, die:

• drei Dimensionen in der ersten Ebene hat:

$root->obj['xyz']['abc']['bnm'] = new Klasse_1();

• drei Dimensionen in der zweiten Ebene hat:

$root->obj['xyz']['abc'][1]->obj['sdf']['yxc']['xcv'] = new Klasse_4();

• und drei Dimensionen un der dritten Ebene hat:

$root->obj['xyz']['abc'][1]->obj['wer']['xcv']['qwe']->obj['rtz']['tzu']['zui'] = new Klasse_6();

Wenn du ein symmetrisches Array aufbauen würdest, nur mit Integer-Zahlen zu je 4 Byte, dann würde die erste Ebene aus einer Million Elementen bestehen. Jedes hätte wiederum eine Million Unterelemente in der zweiten Ebene, und das wiederum eine Million Unterelemente in der dritten Ebene. Mal 4 Byte (ein Zeiger hat z.B. diese Größe)!

1 Mio x 1 Mio x 1 Mio x 4 Byte sind nach Adam Riese die schlappe Größe von
4.000.000.000.000.000.000 Byte. Oder auch 4 Trillionen Byte. Oder (ungefähr gerundet) 4 Millionen Terabyte!

Natürlich nur, wenn du wirklich für jeden Index echt einhundert Werte hast.

Wie gesagt: Eine Überschlagsrechnung. Macht aber deutlich, daß du durch dein Verschachteln bis in die dritte Ebene von jeweils dreidimensionalen Arrays oder Hashes ziemlich schnell in Probleme geraten wirst, weil zumindest die Verwaltungsinformationen für die Hashes sich mit x^9 explosionsartig im Speicher breitmachen.

Mir scheint, du solltest dein Konzept grundlegend ändern. :)

Dazu solltest du vielleicht erstmal erklären, wozu du diese Unmenge an Daten überhaupt benötigst, sprich: Was willst du überhaupt machen?

- Sven Rautenberg

[Jens Hopp]

Hi!

Danke für die schnelle Antwort.

Ich will natürlich nicht alle drei Ebenen mit Werten wie z.B. 1..100 auffüllen. Es geht mir nur darum, die Objekte, die entstehen, gut adressieren zu können (Die drei Ebenen waren nur ein Beispiel, es könnten weniger  [aber auch mal mehr] sein).

Ich will letztlich eine in einer relationalen Datenbank abgebildete Baumstruktur auch so im PHP abbilden, um einzelne Datensätze aus der Datenbank öffnen zu können und die Relationen direkt mit dabei zu haben. Es geht gar nicht unbedingt um eine große Menge an Daten sondern eher um ihre Organisation im Script.

Denkbar wäre z.B. dann etwas wie
$root->obj['Datenbank_1']['Tabelle_1']['Record'][23]->(Objekt mit Felddaten);
$root->obj['Datenbank_1']['Tabelle_2']['Record'][243]->(Objekt mit Felddaten);
D.h. die Namen in den Arrays haben schon etwas mit dem Objekttyp zu tun. Ich denke, man kann sie so ganz gut ansprechen.

Der Unterschied zu etwas wie
$root->Datenbank1_Tabelle1_Record_23->(Objekt mit Felddaten);
$root->Datenbank1_Tabelle2_Record_243->(Objekt mit Felddaten);
-also ohne Array-
kann doch so groß nicht sein oder?

Mit den Arrays kann ich z.B. dann auch wunderbar alle geöffneten Datensätze einer Tabelle mir foreach... abklappern und ausgeben oder sortierungen Vornehmen oder sowas.

Ist das so falsch gedacht?

Viele Grüße
Jens

[Sven Rautenberg]

Moin nochmal!

Ich will letztlich eine in einer relationalen Datenbank abgebildete Baumstruktur auch so im PHP abbilden, um einzelne Datensätze aus der Datenbank öffnen zu können und die Relationen direkt mit dabei zu haben. Es geht gar nicht unbedingt um eine große Menge an Daten sondern eher um ihre Organisation im Script.

Von wievielen Datensätzen reden wir? Zehn? Zwanzig? Einige hundert? Wieviele können es maximal sein? Ist die Maximalzahl vielleicht nicht genau bestimmt? Und wie groß sind diese Datensätze dann?

Kardinalfrage: Bist du sicher, daß du ein Speicherplatzproblem hast, oder könnte es auch an deinem Skript (Programmierfehler) liegen?

Wenn du sicher ein Speicherplatzproblem hast, dann ist dein Ansatz irgendwie falsch.

Mit den Arrays kann ich z.B. dann auch wunderbar alle geöffneten Datensätze einer Tabelle mir foreach... abklappern und ausgeben oder sortierungen Vornehmen oder sowas.

Ich dachte bislang eigentlich immer, für die Datenverwaltung, -sortierung und -bearbeitung wäre die Datenbank zuständig, und nur die Ausgabe in irgendeine HTML-Datei übernimmt das PHP-Skript.

Wie schon gesagt: Wenn du nicht etwas ausführlicher erzählst, was du eigentlich willst, kann man dir kaum helfen, außer zu sagen, daß du dein Speicherplatzproblem (von dem immer noch die Frage ist, ob es das wirklich ist) durch ein anderes Datenhaltungskonzept lösen mußt, sofern es überhaupt lösbar ist, weil die Daten wirklich relativ klein sind.

- Sven Rautenberg

[Jens Hopp]

Moin Sven.

Von wievielen Datensätzen reden wir? Zehn? Zwanzig? Einige hundert? Wieviele können es maximal sein? Ist die Maximalzahl vielleicht nicht genau bestimmt? Und wie groß sind diese Datensätze dann?

Die Zahl der Datensätze ist nicht genau bestimmt, auch deren Größe nicht. Es sind aber auf der anderen Seite nicht soo riesige Mengen (keine langen Texte, keine Blobs u.s.w.). Einige Hundert ist schon zu viel.

Kardinalfrage: Bist du sicher, daß du ein Speicherplatzproblem hast, oder könnte es auch an deinem Skript (Programmierfehler) liegen?

Ja, weil es falsch geschrieben ist, braucht es zu viel Arbeitsspeicher. Es geht in den 2-stelligen MB-Bereich (15MB und mehr). Und das ist schon viel oder? (zumindest für manche Provider) Außerdem läuft es auch langsam, braucht also auch zuviel Rechenzeit.

Ich dachte bislang eigentlich immer, für die Datenverwaltung, -sortierung und -bearbeitung wäre die Datenbank zuständig, und nur die Ausgabe in irgendeine HTML-Datei übernimmt das PHP-Skript.
Wie schon gesagt: Wenn du nicht etwas ausführlicher erzählst, was du eigentlich willst, kann man dir kaum helfen, außer zu sagen, daß du dein Speicherplatzproblem (von dem immer noch die Frage ist, ob es das wirklich ist) durch ein anderes Datenhaltungskonzept lösen mußt, sofern es überhaupt lösbar ist, weil die Daten wirklich relativ klein sind.

Ich will die in der relationalen Datenbank vorhandenen Daten in einer Baumstruktur darstellen, so daß ich
wie (wie beim Win-Explorer) durch das Auf- und Zuklappen von Zweigen an die entsprechenden Datensätze komme. Dazu hole ich nur einige Kopfdaten für die benötigten Datensätze (ID, Name) aus der Datenbank. Das ist also nicht so viel. Ich brauche aber die Baumstruktur für die Darstellung. Und ich brauche auch die relationalen Verknüpfungen irgendwie im Script abgebildet.

Beispiel CD-Datenbank:
+Björk
+U2
+Saga
+Abba

Wenn ich jetzt auf "Björk" klicke:
-Björk
  +Debut
  +Homogenic
  +Selma Songs
+U2
+Saga
+Abba

Wenn ich jetzt auf "Homogenic" klicke:
-Björk
  +Debut
  -Homogenic
    +Titel sososo
    +Titel lalala
  +Selma Songs
+U2
+Saga
+Abba

so in diesem Sinne....

viele Grüße
Jens

[Henryk Plötz]

Moin

Ich will die in der relationalen Datenbank vorhandenen Daten in einer Baumstruktur darstellen, so daß ich
wie (wie beim Win-Explorer) durch das Auf- und Zuklappen von Zweigen an die entsprechenden Datensätze komme. Dazu hole ich nur einige Kopfdaten für die benötigten Datensätze (ID, Name) aus der Datenbank. Das ist also nicht so viel. Ich brauche aber die Baumstruktur für die Darstellung. Und ich brauche auch die relationalen Verknüpfungen irgendwie im Script abgebildet.

Beispiel CD-Datenbank:
[snip]

Du willst also nur einen klitzekleinen Bruchteil der Daten die du aus der Datenbank liest tatsächlich darstellen. Da bietet es sich doch an, nur die Daten die du wirklich brauchst zu lesen und im Speicher zu halten, und schwups sollte das Skript laufen wie geschmiert.

Das ist _natürlich_ einfacher gesagt als getan :)  Denn da muss man dann wohl doch sehr stark am Algorithmus rumfummeln.

Das kommt jetzt darauf an, wie du die Daten vom Client kriegst, aber generell würde ich das so machen:

Alle Datensätze die direkt unter der Wurzel liegen auslesen

für jeden davon:
  rekursiv aufrufen:
    bestimmen, ob er kinddatensätze hat (damit ein + dargestellt werden kann)
    wenn er kinddatensätze hat, schauen ob er ausgeklappt werden soll
       wenn er ausgeklappt werden soll, ein Minuszeichen darstellen, alle kinddatensätze lesen und zum rekursiven Aufruf gehen
       wenn er nicht ausgeklappt werden soll, ein Pluszeichen darstellen

So oder so ähnlich sollte das zu machen sein. Das sendet zwar viele Anfragen an die Datenbank, hält aber nur die wirklich wichtigen Informationen im Speicher.

--
Henryk Plötz
Grüße aus Berlin

[Michael Schröpl]

Hi Henryk,

So oder so ähnlich sollte das zu machen sein.
Das sendet zwar viele Anfragen an die Datenbank, hält aber nur
die wirklich wichtigen Informationen im Speicher.

das paßt gut zu meinen Ausführungen in </?m=18608&t=3166>:
Wieder ein solcher CPU/RAM - TradeOff.

Viele Grüße
      Michael

[Henryk Plötz]

Moin

das paßt gut zu meinen Ausführungen in </?m=18608&t=3166>:
Wieder ein solcher CPU/RAM - TradeOff.

Ja, aber unter den gegebenen Bedingungen, glaube ich doch dass das die beste Lösung ist. Nichts gegen eine schöne Hashtabelle, aber wenn man das selbst in PHP implementiert ist es höchstwahrscheinlich beträchtlich langsamer als die in PHP bereits eingebauten Funktionen, die wahrscheinlich exakt den selben Algorithmus benutzen, aber dafür schön kompiliert vorliegen. (Man kann jetzt natürlich zig Variationen machen. Zum Beispiel statt der Liste hinter jedem Hash-Index die Hash-Tabelle mit offener Verkettung benutzen - so wie wir es grade im Studium lernen - erkauft sich dabei etwas Geschwindigkeit, allerdings mit den Kosten dass die Hashtabelle voll ist, wenn sie voll ist, man vorher also genau wissen muss, wieviel Platz man braucht. Oder man nimmt B*-Bäume. Oder ... usw.)

Hier geht es aber kaum darum möglichst viele Daten möglichst gut im Speicher abzulegen, sondern es dürfte reichen wenn man nur die Daten die man wirklich braucht im Speicher hat. Geht man davon aus, dass die Datenbank alle ihre Daten bereits im Cache hat und die Zugriffe nur über indizierte Felder erfolgen (an dieser Stelle sollten drei Ausrufezeichen stehen, bitte bitte lege auch einen Index auf das Feld mit dem du die Datenbank abfragst, also hier wahrscheinlich die Nummer des Elternknotens) sollte die Datenbankabfrage kaum Rechenzeit verbrauchen und nur noch die Entfernung zur Datenbank einen beschränkenden Faktor darstellen. Da die Datenbank wahrscheinlich auf dem selben Host läuft, geht es hier also fast nur noch um das durch die Gegend kopieren im Hauptspeicher (ja, mit Zugriffen auf den Datenbankindex) was ungefähr - pi mal daumen - genauso schnell oder etwas langsamer abläuft wie die in PHP selbst programmierten Hashfunktionen. Mit dem eminenten Unterschied das vorher kein SELECT * FROM Tabelle nötig ist, sondern nur die Daten die der User braucht, ihren Weg in den Speicherbereich von PHP finden. Der User sollte natürlich nicht alle Bäume gleichzeitig ausklappen :)

Einen kleinen Haken hat die Sache noch: Wenn jemand den Baum mit dem sich dein Skript gerade beschäftig löscht, während es noch beim Datenzusammenkratzen ist, könnten sich Probleme ergeben. Hier ist dann eine etwas intelligentere Fehlerbehandlung gefragt (Im Zweifelsfall einfach nochmal von vorne anfangen) oder du musst die Tabelle für Schreibzugriffe sperren bevor du dich ans Werk machst.
Andere Fehler können natürlich auch mittendrin auftreten (etwa dass die Datenbank plötzlich keine Lust mehr hat) und dann ist es etwas unschön wenn dein Skript schon den halben Baum ausgegeben hat. Deswegen habe ich immer ganz gerne alle Datenbankabfragen am Anfang des Skriptes bevor jeglicher HTML-Code ausgegeben wird. Es sollte hier aber reichen wenn du deine Ausgabe erstmal in einen String schreibst und den nur ausgibst, wenn alles geklappt hat. Oder du aktivierst output_buffering (http://www.php.net/ob_start) und schmeisst den Buffer weg, wenn was schiefgeht.

so long...

--
Henryk Plötz
Grüße aus Berlin

[Michael Schröpl]

Hi Sven,

Nur so als Beispiel nehmen wir mal ein Integer-Array:
Jeder Wert belegt 4 Byte.
Ein Array 1..100 belegt also 400 Byte. Billig.
Ein Array 1..100,1..100 belegt schon 100x100x4 Byte, also 40000 Byte.
Ein Array 1..100,1..100,1..100 belegt 4.000.000 Byte, ungefähr 4 Megabyte.

Wie sicher bist Du Dir, daß PHP intern genau so arbeitet?
Ich kenne einige Sprachen, die das tun würden.
Perl gehört meines Wissens allerdings nicht dazu - soweit ich gehört habe,
werden dort auch Arrays zunächst einmal dynamisch angelegt.

Der tatsächliche Platzbedarf hängt möglicherweise in hohem Maße davon ab,
wieviele verschiedene Elemente tatsächlich benötigt werden.
Wenn der Array beispielsweise nur jedes 3. Element pro Dimension wirklich
umfassen soll, dann sinkt der Speicherbedarf möglicherweise um Faktor
3^(Anzahl Dimensionen) - nämlich dann, wenn der Array als Liste mit
zusätzlicher Adressierungs-Infrastruktur realisiert ist.
Man kann einen Array durchaus auch als Baum realisieren, wenn man bereit
ist, den gesparten Platz mit etwas langsameren Zugriffen zu bezahlen.

1 Mio x 1 Mio x 1 Mio x 4 Byte sind nach Adam Riese die schlappe Größe von
4.000.000.000.000.000.000 Byte. Oder auch 4 Trillionen Byte. Oder (ungefähr
gerundet) 4 Millionen Terabyte!
Natürlich nur, wenn du wirklich für jeden Index echt einhundert Werte hast.

Oder wenn das Laufzeitsystem den Platz dafür bereit stellt. Dies hängt
aber sehr stark von der Arbeitsweise des entsprechenden Interpreters ab.

Macht aber deutlich, daß du durch dein Verschachteln bis in die dritte
Ebene von jeweils dreidimensionalen Arrays oder Hashes ziemlich schnell
in Probleme geraten wirst, weil zumindest die Verwaltungsinformationen
für die Hashes sich mit x^9 explosionsartig im Speicher breitmachen.

Den grundsätzlichen Ausführungen schließe ich mich natürlich vollumfänglich
an. ;-)

Mir scheint, du solltest dein Konzept grundlegend ändern. :)

Wobei die Idee, Dimensionen zusammenzufalten, mir spontan am erfolgverspre-
chendsten erscheint.

Dabei ist das Konkatenieren der Teil-Indizes zu einem komplexen Gesamt-Index
pro Objekt-Ebene durchaus ein gangbarer Weg.

Eine andere Idee wäre die Verwendung einer Hash-Funktion, um diese komplexen
Indexe auf etwas vergleichsweise Triviales (etwa integer) abzubilden, wobei
dann mit diesen Integern ein Array adressiert werden kann, der Platz in der
Größenordnung des tatsächlichen Netto-Bedarfs zur Verfügung stellt.
Perl (und wohl auch PHP?) stellen dies dann sogar direkt als Sprachelement
zur Verfügung (wobei dessen Verwendung dann Vertrauen in die entsprechende
Implementierung bedeutet ;-), in C müßte man es selbst programmieren.

Viele Grüße
      Michael

[Jens Hopp]

Hi Michael

Eine andere Idee wäre die Verwendung einer Hash-Funktion, um diese komplexen
Indexe auf etwas vergleichsweise Triviales (etwa integer) abzubilden, wobei
dann mit diesen Integern ein Array adressiert werden kann, der Platz in der
Größenordnung des tatsächlichen Netto-Bedarfs zur Verfügung stellt.
Perl (und wohl auch PHP?) stellen dies dann sogar direkt als Sprachelement
zur Verfügung (wobei dessen Verwendung dann Vertrauen in die entsprechende
Implementierung bedeutet ;-), in C müßte man es selbst programmieren.

Heißt das, die Arrays nach meinem Beispiel gehend mit Integern zu adressieren
$root->obj[3][54][132]->...
diese Integers aber wiederum in einem Hash zu haben?
So nach dem Motto
$hash['asd'] = 3;
$hash['qwe'] = 54;
$hash['yxc'] = 132;     ?

Bei Bedarf kann man das verschachtelte Array dann mit den Hash-Werten adressieren.

Das hatte ich auch schon überlegt, die Frage ist nur, ob Du das meinst.
Mein Problem ist hier jetzt auch die Informatiker-Begrifflichkeit, die ich erst mal in mein Learning-by-doing-Programmierer-Deutsch übersetzen muß ... ;-)

Viele Grüße
      Michael

Jo, ebenso viele Grüße
Jens

[Michael Schröpl]

Hi,

Heißt das, die Arrays nach meinem Beispiel gehend mit Integern
zu adressieren
$root->obj[3][54][132]->...
diese Integers aber wiederum in einem Hash zu haben?
So nach dem Motto
$hash['asd'] = 3;
$hash['qwe'] = 54;
$hash['yxc'] = 132;     ?

Die Idee ist, daß Du die Menge der angebotenen Indexwerte der Menge
der benötigten Index-Werte anpaßt.
_Wie_ Du das machst, das hängt von Deinem konkreten Einsatzfall ab.

Ich nehme mal Deine drei Zahlenwerte 3, 54 und 132 als Eingabe.
Wenn Du davon ausgehst, daß Du tatsächlich ungefähr drei Werte haben
wirst, aber nicht genau weißt, wieviele (tendentiell eher etwas mehr),
dann könnte Deine Hash-Funktion einfach den Zahlenwert modulo 10
zurückliefern, also 3 -> 3, 54 -> 4 und 132 -> 2.
Du hältst einen Array mit 10 Elemente vor, kontrollierst also die
erforderliche Speicher-Menge; gleichzeitig erfordert der Zugriff auf
den passenden Speicherort genau einen mathematische Transformation.
Du "kaufst" also sehr viel Speicher durch etwas zusätzliche CPU-
Leistung - ein klassischer Trade-Off der Datenverarbeitung. (Der
Einsatz von mod_gzip für den Apache-Server des Self-Portals ist
letzten Endes dasselbe - der 'kauft' Bandbreite mit CPU-Leistung.)

Natürlich mußt Du damit leben können, daß Deine Hash-Funktion auch
mal "Pech" hat. Sie wird Dir nicht mit Sicherheit lauter disjunkte
Indizes liefern.
Du mußt also unter jeder Deiner Speicheradressen möglicherweise eine
komplexere Struktur (z. B. eine lineare Liste) anlegen, nicht nur
eine atomare Speicherzelle. Und Du mußt Verwaltungsinformationen mit-
führen, um die Einträge der Liste voneinander unterscheiden zu können.
Letzten Endes würde sich Deine Implementierung dem, was Perl oder PHP
für deren interne Realisierung eines Hashes verwenden, stark annähern.

Der Trick besteht darin, daß es sehr unwahrscheinlich ist, daß diese
Liste tatsächlich viele Elemente enthält (dann wäre Deine Hash-Funktion
schlecht); in den allermeisten Fällen wird ein direkter Zugriff sofort
zum Erfolg führen.
Deshalb habe ich die Tabelle auch größer gewählt als nötig. Im Beispiel
mit Deinen drei Zahlen wäre schon "modulo 4" eine optimale Hash-Funktion
gewesen, aber bereits für die 4. Zahl würde die Wahrscheinlichkeit, die
verbliebene Speicherzelle zu treffen, auf nur noch 25% absinken, und bei
der 5. Zahl ist die erste Kollision sicher.

Von den Integer-Zahlen als Eingabewerte in die Hash-Funktion bin ich nur
ausgegangen, um die Sache anschaulicher zu machen.
Du kannst genauso gut den ersten Buchstaben Deiner Adreß-Strings verwen-
den. Das Prinzip gilt für Bitmuster - egal, was sie bedeuten.

Insbesondere kann Deine Hash-Funktion beliebig viele Dimensionen als
Eingabe haben, also beliebig komplexe "Adressen" übersetzen - so wie
die skalare Nummer eines Personalausweises eine beliebig komplexe Person
adressieren kann.
Du kannst also sämtliche Deiner Objekte über einen einzigen linearen
Array speichern, wenn Deine Hash-Funktion die Dimensionen entsprechend
zusammenfalten kann. Damit weißt Du sehr genau, wieviel Arbeitsspeicher
Du Deinem Problem zuordnest - wenn es nicht reicht, dann wird halt die
Kollisionsrate höher und die Verarbeitung langsamer.
(Die Kollisionsrate kannst Du dabei selbst mitschreiben und beim Über-
schreiten eines kritischen Wertes eine Meldung ausgeben, daß Dein Spei-
cher offenbar zu dürftig ausgestattet ist - im Prinzip macht ein Be-
triebssystem etwas Ähnliches, wenn es die Swapping-Rate berechnet.)
Auf diese Weise würde Deine ursprüngliche Idee direkt mit einfließen -
und ein einziger Aufruf einer effizient implementierten Hash-Funktion
ist wömöglich sogar schneller als wiederholtes Deferenzieren Deiner
Objekt-Verkettungen.

Mein Problem ist hier jetzt auch die Informatiker-Begrifflichkeit,
die ich erst mal in mein Learning-by-doing-Programmierer-Deutsch
übersetzen muß ... ;-)

Nur zu - dafür ist das Forum prima geeignet.

Viele Grüße
      Michael

[Sven Rautenberg]

Hi Sven,

Moin!

Ein Array 1..100,1..100,1..100 belegt 4.000.000 Byte, ungefähr 4 Megabyte.

Wie sicher bist Du Dir, daß PHP intern genau so arbeitet?

Garnicht sicher. Sicher ist nur, daß ein voll genutztes 100x100x100-Array eine Million Einträge enthält, und mindestens soviel Platz erfordert, wie die Daten, die dort abgelegt sind. Als Beispiel, wie schnell ein Array unerwartet groß werden kann, war es doch eindrucksvoll genug, oder?

Ich kenne einige Sprachen, die das tun würden.

Turbo Pascal arbeitet so. Allerdings gibts (zumindest in den DOS-Varianten) das Problem mit den 4 Megabyte nicht, weil das Datensegment höchstens 64 KB groß sein durfte. Alles andere mußte mit Pointern, Listen und Bäumen gelöst werden. Wer dann aber eine Million Einträge im RAM halten will, braucht bei Listen allein deshalb schon mal 4 Megabyte an Pointern (die ja auch 32 Bit=4 Byte groß sind), plus die Datenmenge. Bei Bäumen sind mindestens zwei Pointer pro Datensatz zu erwarten, also 8 MB Verwaltungsinformationen, plus Daten.

Ich schweife ab...

Perl gehört meines Wissens allerdings nicht dazu - soweit ich gehört habe, werden dort auch Arrays zunächst einmal dynamisch angelegt.

Was ja auch Sinn macht, denn unbenutzter Platz muß ja nicht verbraucht werden.

- Sven Rautenberg

[Christian Kruse]

Hoi,

Ein Array 1..100,1..100,1..100 belegt 4.000.000 Byte, ungefähr 4 Megabyte.

Wie sicher bist Du Dir, daß PHP intern genau so arbeitet?

Garnicht sicher.

Gut :-) Das tut es naemlich nicht. In PHP sind Arrays intern
Hashtables.

Sicher ist nur, daß ein voll genutztes 100x100x100-Array eine
Million Einträge enthält, und mindestens soviel Platz erfordert,
wie die Daten, die dort abgelegt sind.

Wenn alle 1.000.000 Eintraege gefuellt sind, ja.

Ich kenne einige Sprachen, die das tun würden.

Turbo Pascal arbeitet so. Allerdings gibts (zumindest in den
DOS-Varianten) das Problem mit den 4 Megabyte nicht, weil das
Datensegment höchstens 64 KB groß sein durfte.

In der DOS-Variante, die ich hatte, durfte ich den Untereren
Speicherbereich (konventionellen Speicherbereich) nur nutzen. Da
musste man noch richtig sparsam mit dem Speicher umgehen ;-)

Gruesse,
 CK

[Christian Kruse]

Hoi,

Ich wäre sehr froh, wenn mir die PHP-Spezies unter Euch ein paar
Tips geben könnten.

Spezie bin ich nicht, aber ich versuchs trotzdem.

Ich habe ein Script geschrieben, das augenscheinlich zu viel
Speicherplatz verbraucht.

Das heisst?

1. assoziative Arrays
   Könnte es sein, daß die assoziativen Arrays viel mehr Platz
   verbrauchen, als "normale" Arrays?
   Wäre es also günstiger, statt
   <?
   $root->obj['xyz']['abc']['bnm'] = new Klasse_1();
   ?>
   die Variante
   <?
   $root->obj[1][3][5] = new Klasse_1();
   ?
   zu wählen?

Nein. Das sind pro Key lediglich (Anzahl der Zeichen des Keys - 1)
Byte mehr. Und ansonsten sind Arrays in PHP *immer* assoziativ (als
eine Key-Value-Liste implementiert, AFAIK).

(Und muß man dabei darauf achten, daß in jeder Dimension von
0,1,2... beginnend alle Zahlen vertreten sind, oder geht auch
z.B. 5,34,623...)

Es geht auch die zweite Variante. Ist sogar sinnvoller.

2. Verschachtelung der mehrdimensionalen Arrays
   Könnte es sein, daß die verschachtelung der Arrays als solche
   eine Rolle spielt?
   Wäre es günstiger, statt
   <?
   $root->obj['xyz']['abc']['bnm'] = new Klasse_1();
   ?>
   die Variante
   <?
   $root->obj['xyz_abc_bnm'] = new Klasse_1();
   ?>
   zu wählen?

Das duerfte hoechstens Geschwindigkeits-Vorteile bringen -- PHP muss
jetzt nicht mehr n Lookups machen, sondern nur noch einen.
Aber das ist so eine Sache, dafuer ist die Liste dann wieder ein
ganzes Stueckchen groesser. Das musst du mal ausrechnen: es sollte
generell so sein, dass bei wenigen Elementen ein Lookup schneller
ist als n Lookups, bei grossen Arrays allerdings sollte eine
verschachtelte Struktur schneller sein.

3. Objekte als "value" in Arrays
   Könnte es sein, daß es überhaupt ungünstig ist, Objekte in Arrays
   zu stecken?
   Wäre es günstiger, statt
   <?
   $root->obj['xyz']['abc']['bnm'] = new Klasse_1();
   ?>
   die Variante
   <?
   $root->obj_xyz_abc_bnm = new Klasse_1();
   ?>
   zu wählen?

Nein.

4. Referenzen
   Ist die hohe Zahl von Referenzen, die z.B. durch die
   parent-child-Beziehung entstehen relevant?

Durchaus. Referenzen sind anscheinend sehr langsam in PHP.

Wäre es günstiger statt der wirklichen Abbildung eines
Objektbaumes nur die "Adressen" (Arraynamen) der Objekte zu
speichern?
Also statt
<?
$root->obj['xyz']['abc'][1]->obj['sdf']['yxc']['xcv'] = new Klasse_4();
?>
lieber
<?
$root->obj['xyz']['abc'][1] = new Klasse_1();
$root->obj['sdf']['yxc']['xcv'] = new Klasse_4();
$root->obj['xyz']['abc'][1]->child = 'sdf_yxc_xcv';
$root->obj['sdf']['yxc']['xcv']->parent = 'xyz_abc_1';
(oder so ähnlich)
?>

Ja. Wenn die Wiederaufbereitung der Daten nicht zu viel Zeit kostet.

5. Verschachtelung von Objekten
   Durch die Nutzung von $root und Unterordnung aller Objekte unter
   dieses Rootobjekt kann ich durch
   <?
   global $root;
   ?>
   in allen Funktionen auf alle vorhandenen Objekte zugreifen. Das
   ist recht günstig.
   Ist es aber vielleicht trotzdem besser, auf $root zu verzichten
   und Objekte im allgemeinen Namensraum zu definieren?

Nein.

Es könnte ja z.B. sein, daß mit jedem
<?
global $root;
?>
der ganze Baum wieder innerhalb der Funktion noch einmal erzeugt
wird.
Wäre es also günstiger, statt
<?
$root->obj['xyz']['abc']['bnm'] = new Klasse_1();
$root->obj['xyz']['mno']['jkl'] = new Klasse_2();
$root->obj['asd']['qwe']['mno'] = new Klasse_3();
?>
lieber die Variante
<?
$obj['xyz']['abc']['bnm'] = new Klasse_1();
$obj['xyz']['mno']['jkl'] = new Klasse_2();
$obj['asd']['qwe']['mno'] = new Klasse_3();
?>
zu wählen und dann innerhalb einer Funktion z.B. mit
<?
global $obj['xyz']['abc']['bnm'];
global $obj['xyz']['mno']['jkl'];
?>
die benötigten Objekte direkt anzusteuern?

Nein.

Wenn ich jetzt wissen würde, ob ich auf dem richtigen Weg bin -
und wo ich anfange...

Ich wuerde an deiner Stelle nicht bei der Datenstruktur suchen,
sondern den Algorithmus checken.

Gruesse,
 CK

[Jens Hopp]

Hi Christian

Ich habe ein Script geschrieben, das augenscheinlich zu viel
Speicherplatz verbraucht.

Das heisst?

15MB und mehr. Das mag nicht jeder Provider.
Auch läuft es zu langsam (einige Sekunden) - ist also sicher auch ein Rechenleistungsproblem.

4) Referenzen

Ist die hohe Zahl von Referenzen, die z.B. durch die
parent-child-Beziehung entstehen relevant?

Durchaus. Referenzen sind anscheinend sehr langsam in PHP.

Ja, das ist beruhigend, denn das könnte ich am schnellsten beheben... ;-)

Wäre es günstiger statt der wirklichen Abbildung eines
Objektbaumes nur die "Adressen" (Arraynamen) der Objekte zu
speichern?

Ja. Wenn die Wiederaufbereitung der Daten nicht zu viel Zeit kostet.

Die Daten sind ja da, wenn ein Objekt einmal definiert ist oder?
Wenn ich dann (statt Referenz) irgendwo den Namen (also die Array-Keys) des Objektes speichere, müßte ich doch auch direkt rankommen.

Wenn ich jetzt wissen würde, ob ich auf dem richtigen Weg bin -
und wo ich anfange...

Ich wuerde an deiner Stelle nicht bei der Datenstruktur suchen,
sondern den Algorithmus checken.

Ja, das kann man sicherlich auch noch das ein oder andere optimieren...

Danke für die vielen Tips!

Viele Grüße
Jens

[Christian Kruse]

Hoi,

Ich habe ein Script geschrieben, das augenscheinlich zu viel
Speicherplatz verbraucht.

Das heisst?
15MB und mehr. Das mag nicht jeder Provider.

Das hoert sich nach einer rekursiven Loesung an?

Auch läuft es zu langsam (einige Sekunden) - ist also sicher auch
ein Rechenleistungsproblem.

Oder benutzt du eine iterative?

Die Daten sind ja da, wenn ein Objekt einmal definiert ist oder?
Wenn ich dann (statt Referenz) irgendwo den Namen (also die
Array-Keys) des Objektes speichere, müßte ich doch auch direkt
rankommen.

Mit 'Aufbereitung der Daten' meine ich, dass du die Keys ja auch
wieder auseinander nehmen musst. Das darf nicht zu viel Zeit in
Anspruch nehmen.

Ja, das kann man sicherlich auch noch das ein oder andere
optimieren...

Poste doch einfach mal eine URL, wo man den Source sich anschauen
kann.

Danke für die vielen Tips!

Gern.

Gruesse,
 CK

[Carsten]

Hallo Jens!

Da sich bislang ja noch keiner gefunden hat der so richtig Bescheid weiß hier mal ein paar Ideen von mir dazu:

1. assoziative Arrays
   Könnte es sein, daß die assoziativen Arrays viel mehr Platz verbrauchen, als "normale" Arrays?

In PHP sind AFAIK alle Arrays assoziativ, es ist also egal ob sie fortlaufend numerisch, numerisch oder alphanumerisch abgelegt werden.  Der unterschied besteht dann nur im Speicherbedarf für den Schlüssel selbst.

2. Verschachtelung der mehrdimensionalen Arrays
   Könnte es sein, daß die verschachtelung der Arrays als solche eine Rolle spielt?

Für jedes 'neue' Array ist eine neue Verwaltungsinformation zum Array selbst nötig. Wenn die Arrays nicht nicht nur ein paar Elemente haben  sollte das keine Rolle spielen.
Ganz viele Arrays mit jeweils ganz wenig Elementen kann ein Problem sein, pro Array ist ja die Hashtabelle, eine Schlüsseltabelle und eine Tabelle für die Inhalte nötig. Da dürfte einiges zusammenkommen.

3. Objekte als "value" in Arrays
   Könnte es sein, daß es überhaupt ungünstig ist, Objekte in Arrays zu stecken?

Da besteht eigentlich kein Grund zu.

4. Referenzen
   Ist die hohe Zahl von Referenzen, die z.B. durch die parent-child-Beziehung entstehen relevant?
   Wäre es günstiger statt der wirklichen Abbildung eines Objektbaumes nur die "Adressen" (Arraynamen) der Objekte zu speichern?

Die Referenz sollte eigentlich die kürzeste und günstigste Form sein.

gibt es vielleicht noch mehr Fallen?
<? ???? ?>

Tja, das weiss ich auch nicht....

Eigentlich sieht das was du gemacht hast so aus, als ob es im Rahmen von PHP eine effiziente Lösung ist. Es werden immer nur alle benötigten Objekte angelegt.
Der Speicherverbrauch vom 'Baum' selber ist ebenfalls ok. Jeder Ast hat nur einen Array-Eintrag.

Bleibt also die Menge der Array Einträge gesammt, die Menge der Objekte gesammt, die Menge der Arrays und die Grösse der Hashes.
In welcher Grössenordnung liegt denn das so?

Den fettesten Speicher-Verbrauch dürften viele fast leere Arrays haben, da würde etwas ähnliches wie deine Variante 3 Abhilfe schaffen: $root->obj[xyz_abc_bnm] = new Klasse_1();
Jetzt hast du nur noch ein Array, d.h. der 'pro Array' Aufwand fällt nur einmal an.

Gruss,
 Carsten

[Jens Hopp]

Hallo, all Ihr freundlichen Helfer und Tipsgeber.

VIELEN DANK!!!

Auch, wenn ich wohl doch erst mal Informatik studieren sollte, um wirklich alles zu verstehen ~:-|

Wäre vielleicht besser. Learning-by-doing geht zwar auch, die Umwege sind halt nur länger...

Ein bißchen weiter bin ich aber gekommen. Und ein paar grundsätzliche Sachen über PHP zu erfahren konnte auch nicht schaden.

Also, vielen Dank nochmal und viele Grüße
Jens-Holger Hopp