[HaBo]

Sunstepper · 25.03.06, 22:04

Hi,

So, jetzt habe ich auch mal ein Problem. :)
Ist leider recht kniffelig.

Szenario:

Ich habe ein eindimensionales Array mit mehreren 100 Objekten der selben Klasse.
Diese Klasse hat ca. 10-20 Attribute vom Typ integer oder boolean. Alle Attribute aller Objekte verändern sich fortlaufend und ohne ein bestimmtes Muster.

Und jetzt möchte ich das Array, nach allen Objekten durchsuchen, bei denen bestimmte Bedingungen erfüllt sind. Z.B. wenn es die Attribute $foo und $bar gibt, suche ich alle Objekte aus dem Array, bei denen $foo == 2 und $bar == 42 ist. Übrigens existiert für jedes Objekt das konstante einzigartige Attribut $id.
Da einige 1000 diese "Queries" hintereinander gemacht werden müssen, ist performancetechnisch leider kein ständiges Durchsuchen des Arrays per Schleife (z.B. foreach) möglich.

Ich habe bis jetzt mal eine simple Spiegelung aller Werte in eine SQL-HEAP-Tabelle versucht und dann einfach mit SQL-Queries gearbeitet. Hat zwar technisch funktioniert, die Performance ist jedoch kaum bis gar nicht besser.

Gibt es eine performante Lösung, solche bestimmten Objekte in so einem Objektarray zu finden?

Vielen Dank.

CPU8080 · 25.03.06, 22:08

vll kannste dir damit was zusammen basteln:

klicken

Anzeige

- Anzeige -

Sunstepper · 25.03.06, 22:16

Wie oben geschrieben, verbraucht 10000 mal foreach() auf ein Array mit NNN Elementen zu viel Performance...

CPU8080 · 25.03.06, 22:46

und wenn du die elemente der Array zählst und dann mit einer for schleife durch läuft ist aber umständlicher.
Aber ich denke mal 10000 durchläufe brauchen immer viel Performence denk ich mal, oder.

Sunrize · 26.03.06, 00:40

Wenn Du öfters suchen musst, als dass Du was hinzufügst, könntest Du gleich beim Hinzufügen für eine Sortierung sorgen.
Dann sucht es sich schneller.

Hendrik

**Elderan** · 26.03.06, 12:31

Hallo,
also in C wäre das relativ leicht, allerdings hat PHP keine Pointer.

Aber am besten baust du die 10-20 Attribute wie einen binären Baum auf.

Ca. so:

Code:

            $foo (=15)
          /        \
       10         18
      /  \        / \
     5   14     16  19

Das gleiche mit allen anderen Eigenschaften.

Dann bei $foo == 10 (im Baum) machst du ein Array, welches alle IDs enthält, die $foo = 10 haben.

Genauso bei $bar etc.

Wenn du jetzt z.B. $foo == 5 && $bar == 8 suchst, dann gehst du in den jeweiligen binären Baum, und suchst dort das Array mit den IDs hinaus.
Dann bildest du die Schnittmenge der beiden Arrays (welche ID kommt in beiden Arrays vor) und schon hast du die IDs der Arrays, die sowohl $foo == 5 && $bar == 8 haben.

Das suchen funktioniert sehr schnell (bei 4,2 Mrd. verschiedenen Werte z.B. für $foo findet man einen Wert mit max. 32 Schritten), nur das ändern von Werten ist komplizierter, denn dann muss man in dem Baum die ID aus dem Arrays mit alten Wert löschen, und die ID in das neue Array hinzufügen.
Sollte aber auch kein Problem darstellen.

Wichtig ist, dass der Baum ausgeglichen ist, also als Wurzel nicht 1 oder den größten Wert benutzen.

**soox** · 27.03.06, 18:59

Zitat:

Original von Elderan
also in C wäre das relativ leicht, allerdings hat PHP keine Pointer.

mit referenzen sollte es jedoch auch gehen.

Sunstepper · 28.03.06, 12:42

Das mit dem Binärbaum hat mir auch jemand anderes vorgeschlagen.
Werde damit mal rumexperimentieren. Danke.

**Elderan** · 28.03.06, 18:35

Zitat:

Original von soox

Zitat:

Original von Elderan
also in C wäre das relativ leicht, allerdings hat PHP keine Pointer.

mit referenzen sollte es jedoch auch gehen.

Nicht so richtig.

Manual:

Zitat:

Referenzen sind in PHP ein Mechanismus um verschiedene Namen für den gleichen Inhalt von Variablen zu ermöglichen. Sie sind nicht mit Zeigern in C zu vergleichen, sondern Aliasdefinitionen für die Symboltabelle....

[...]

Wie bereits gesagt: Referenzen sind keine Zeiger. Das bedeutet, der folgende Code tut nicht, was zum Beispiel ein C Programmierer erwarten würde:

function foo (&$var) {
$var =& $GLOBALS["baz"];
}
foo($bar);

Folgendes wird passieren: $var in foo wird zunächst an $bar aus der aufrufenden Instanz, dann aber an $GLOBALS["baz"], gebunden. Es gibt keine Möglichkeit, $bar aus der aufrufenden Instanz mittels Referenz-Mechanismen an etwas anderes zu binden, da $bar in der Funktion foo nicht zur Verfügung steht ($bar wird durch $var repräsentiert; $var verfügt nur über Variableninhalt, besitzt aber keinen name-to-value Eintrag in der Symboltabelle der aufrufenden Instanz).
Was Referenzen nicht leisten

**soox** · 28.03.06, 22:54

Zitat:

Original von Elderan

Zitat:

Original von soox

Zitat:

Original von Elderan
also in C wäre das relativ leicht, allerdings hat PHP keine Pointer.

mit referenzen sollte es jedoch auch gehen.

Nicht so richtig.

ich sagte ja auch nicht, dass es genau geich geht...in java hat man auch keine pointer sondern arbeitet mit referenzen. dort funktionierts mit diesen wunderbar warum sollte es also in php mit dem gleichen (referenzen) nicht gehen?

Anzeige

- Anzeige -

25.03.06, 22:04	#1 (permalink)
Sunstepper Registriert seit: 25.08.04 Likes: 0	Objektarrays durchsuchen Anzeige Hi, So, jetzt habe ich auch mal ein Problem. :) Ist leider recht kniffelig. Szenario: Ich habe ein eindimensionales Array mit mehreren 100 Objekten der selben Klasse. Diese Klasse hat ca. 10-20 Attribute vom Typ integer oder boolean. Alle Attribute aller Objekte verändern sich fortlaufend und ohne ein bestimmtes Muster. Und jetzt möchte ich das Array, nach allen Objekten durchsuchen, bei denen bestimmte Bedingungen erfüllt sind. Z.B. wenn es die Attribute $foo und $bar gibt, suche ich alle Objekte aus dem Array, bei denen $foo == 2 und $bar == 42 ist. Übrigens existiert für jedes Objekt das konstante einzigartige Attribut $id. Da einige 1000 diese "Queries" hintereinander gemacht werden müssen, ist performancetechnisch leider kein ständiges Durchsuchen des Arrays per Schleife (z.B. foreach) möglich. Ich habe bis jetzt mal eine simple Spiegelung aller Werte in eine SQL-HEAP-Tabelle versucht und dann einfach mit SQL-Queries gearbeitet. Hat zwar technisch funktioniert, die Performance ist jedoch kaum bis gar nicht besser. Gibt es eine performante Lösung, solche bestimmten Objekte in so einem Objektarray zu finden? Vielen Dank.

26.03.06, 12:31	#6 (permalink)
Elderan Moderator Registriert seit: 30.03.04 Likes: 14	Hallo, also in C wäre das relativ leicht, allerdings hat PHP keine Pointer. Aber am besten baust du die 10-20 Attribute wie einen binären Baum auf. Ca. so: Code: $foo (=15) / \ 10 18 / \ / \ 5 14 16 19 Das gleiche mit allen anderen Eigenschaften. Dann bei $foo == 10 (im Baum) machst du ein Array, welches alle IDs enthält, die $foo = 10 haben. Genauso bei $bar etc. Wenn du jetzt z.B. $foo == 5 && $bar == 8 suchst, dann gehst du in den jeweiligen binären Baum, und suchst dort das Array mit den IDs hinaus. Dann bildest du die Schnittmenge der beiden Arrays (welche ID kommt in beiden Arrays vor) und schon hast du die IDs der Arrays, die sowohl $foo == 5 && $bar == 8 haben. Das suchen funktioniert sehr schnell (bei 4,2 Mrd. verschiedenen Werte z.B. für $foo findet man einen Wert mit max. 32 Schritten), nur das ändern von Werten ist komplizierter, denn dann muss man in dem Baum die ID aus dem Arrays mit alten Wert löschen, und die ID in das neue Array hinzufügen. Sollte aber auch kein Problem darstellen. Wichtig ist, dass der Baum ausgeglichen ist, also als Wurzel nicht 1 oder den größten Wert benutzen.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Durchsuchen von UDP-Paketen langsamer?	iko79	Network · LAN, WAN, Firewalls	6	05.05.08 21:35
WEB SERVER durchsuchen	FacomUnit	Webmaster-Security	7	04.07.07 19:57
Wörter Generator/Wortlisten durchsuchen	mimili	(In)security allgemein	1	30.04.05 14:09
mehrere excel-dateien durchsuchen?!	maedmexx	Applikationen	4	03.07.04 12:19
Server nach freigaben durchsuchen	scratchy	Virenschutz · Tools & Aggressive Software	2	05.08.03 12:01

25.03.06, 22:08	#2 (permalink)
CPU8080 Registriert seit: 20.07.05 Likes: 0	vll kannste dir damit was zusammen basteln: klicken

25.03.06, 22:16	#3 (permalink)
Sunstepper Themenstarter Registriert seit: 25.08.04 Likes: 0	Wie oben geschrieben, verbraucht 10000 mal foreach() auf ein Array mit NNN Elementen zu viel Performance...

25.03.06, 22:46	#4 (permalink)
CPU8080 Registriert seit: 20.07.05 Likes: 0	und wenn du die elemente der Array zählst und dann mit einer for schleife durch läuft ist aber umständlicher. Aber ich denke mal 10000 durchläufe brauchen immer viel Performence denk ich mal, oder.

26.03.06, 00:40	#5 (permalink)
Sunrize Registriert seit: 04.01.05 Likes: 0	Wenn Du öfters suchen musst, als dass Du was hinzufügst, könntest Du gleich beim Hinzufügen für eine Sortierung sorgen. Dann sucht es sich schneller. Hendrik

28.03.06, 12:42	#8 (permalink)
Sunstepper Themenstarter Registriert seit: 25.08.04 Likes: 0	Das mit dem Binärbaum hat mir auch jemand anderes vorgeschlagen. Werde damit mal rumexperimentieren. Danke.

[HaBo]

Objektarrays durchsuchen