PHP in_array() die Performance-Bremse
Dies ist ein Gastartikel von Dominik Siebel.
Dominik ist 25 Jahre alt und arbeitet als Webentwickler und Consultant bei TWT Business Solutions GmbH in Düsseldorf. Sein Hauptaufgabenbereich ist die Entwicklung von Inter- und Intranetapplikation im Zusammenspiel mit Google Enterprise Produkten (GSA) auf Basis gängiger Technologien: MySQL, PHP, Java, jQuery, etc.
Einleitung
Ich bin kürzlich erst wieder über dieses Problem gestolpert und dachte mir ich bringe es für die Nachwelt zu Papier 😉
PHPs in_array() Funktion ist ziemlich praktisch um auf die Schnelle zu überprüfen ob ein Eintrag bereits in einem Array enthalten ist und so z.B. doppelte Einträge zu vermeiden. So handlich diese Funktion auch ist, so offenbart sie jedoch erhebliche Schwächen, wenn wir erstmal ein paar mehr als die üblichen 500 – 1000 Datensätzen verarbeiten wollen.
Ausgangssituation
Im Zuge einer etwas komplexeren Search-as-you-type Implementierung werden in einem Ajax-Request über zwei verschiedene Mechanismen Vorschläge in einem Array vorgehalten, bevor sie per JSON an den Client zurück geliefert werden, wobei der zweite Mechanismus vor jedem Hinzufügen eines Vorschlags prüft ob dieser eventuell bereits vorhanden ist.
Der Vorzug einer solchen Search-as-you-type Geschichte ist, dass man Begriffe und Suchergebnisse vorgeschlagen bekommt, noch bevor man den kompletten Suchbegriff eingetippt hat. Was wir also brauchen ist Geschwindigkeit. Über die Laufzeit des Projektes wurden es aber irgendwann so viele Daten, dass die Suche immer langsamer wurde. Bis zur völligen Nutzlosigkeit. Wo lag das Problem?
Folgendes Beispiel zeigt in vereinfachter Form die bestehende Implementierung:
Beispiel
<?php
$result = range(1, 50000);
$iStartTime = time();
echo 'START - count: ' . count($result) . PHP_EOL;
for ($i = 0; $i < 50000; $i++) {
$random = mt_rand(1,100000);
if (!in_array($random, $result)) {
$result[] = $random;
}
}
echo 'END - count: ' . count($result) . ' duration: ' . (time() - $iStartTime) . PHP_EOL;
Auf eine bereits bestehende Menge Daten von (in diesem Beispiel) 50000 Einträgen werden über einen zweiten Mechanismus (hier durch die Generierung von weiteren 50000 Zufallswerten dargestellt) weitere Datensätze hinzugefügt ohne dabei Duplikate zu erzeugen. Dabei stellte sich nach einiger Zeit der Fehlersuche heraus, dass genau dieser Codeschnipsel bis zu 1 Minute oder länger lief. Nicht gerade die gewünschte Antwortzeit für ein schnelles “look-up”:
Ergebnis
dsiebel@note:~/public_html/test$ php in_array.php START - count: 50000 END - count: 69625 duration: 109
Also ich weiß nicht, wie es euch geht, aber wenn ich knapp 110 Sekunden auf meine Suchvorschläge müsste… So ist dieses Stück Programm also nicht mehr wirklich nutzbar.
Lösungsansätze
Wie sollte ich dieses Problem beheben? Ich habe verschiedene Ansätze ausprobiert und konnte mich letztendlich auf die folgende Implementierung einigen:
Beispiel
<?php
$result = array();
for ($i = 0; $i < 50000; $i++) {
$result[md5($i)] = $i;
}
$iStartTime = time();
echo 'START - count: ' . count($result) . PHP_EOL;
for ($i = 0; $i < 50000; $i++) {
$random = mt_rand(1, 100000);
$index = md5($random);
if (!isset($result[$index])) {
$result[$index] = $random;
}
}
echo 'END - count: ' . count($result) . ' duration: ' . (time() - $iStartTime) . PHP_EOL;
Auch hier wird wieder mit einem Grundstock von 5000 Datensätzen begonnen. Unterschied ist die Art und Weise, wie die Daten im Array abgelegt werden: Im ersten Skript wurde ein “normales” Array mit numerischen Indizes verwendet. In der neuen Implementierung wird als Index die MD5-Summe des Wertes verwendet. Warum die MD5-Summe? Da es sich im realen Skript teilweise um ganze Sätze oder Beschreibungen handelt war MD5 die nächste Wahl die Strings in gleich große und einzigartige Schlüssel umzuwandeln. Außerdem besteht ein Vorschlag nicht nur aus dem eigentlichen Vorschlag sondern auch zusätzlichen Metadaten für eine Sortierung beispielsweise, die in einem späteren Schritt erfolgen könnte.
Zurück zu dem neuen Script:
Ergebnis
dsiebel@note:~/public_html/test$ php isset.php START - count: 50000 END - count: 69719 duration: 0
Dieses Ergebnis kann sich doch schon eher sehen lassen (< 1s).
Da wir die Werte in Form der MD5-Summen als Indizes verwenden können wir das Array schnell und einfach mittels isset() überprüfen – welches um ein vielfaches performanter arbeitet als in_array() – bevor wir den neuen Vorschlag hinzufuegen und somit Duplikate vermeiden.
Ich hoffe mein kleiner Gastbeitrag hilft vielleicht dem ein oder anderen von Euch dieses Problem frühzeitig zu erkennen und zu verhindern.
Alternativ kann man auch statt in_array zu benutzen einfach alles in den Array tun und am ende ein array_unique nutzen um alle Einträge nur einmal zu haben.
Gruß
René
René
26 Jan 11 at 09:54
Cooler Ansatz. Aber gibts da nicht ne Möglichkeit, über ein statisches Objekt eine Menge zu definieren? Und laut mathematischer Definition einer Menge darf ein Element ja nur ein einziges Mal vorhanden sein.
Ob das nun performanter ist, weiß ich nicht, aber da kann man auch mal drüber nachdenken.
rene
26 Jan 11 at 10:33
Sicher gibt es auch andere Lösungen. Ich hatte, wie gesagt, auch noch 2-3 weitere Implementierungen angetestet. Diese war die Implementierung, die in dem Moment am sinnvollsten erschien, bei allen anderen gab es Seiteneffekte mit dem Rest der Applikation.
Array_unique war dabei noch die performanteste Lösung.
Der „statisches Objekt“ Ansatz von rene ist mir schleierhaft.
Ich hatte es über ein selbst implementiertes Collection Objekt versucht zu lösen, das nur Objekte eines bestimmten Interfaces aggregiert und kam auf Rechenzeiten von 2-3 Sekunden, daher wurde dies fallen gelassen.
Dominik Siebel
26 Jan 11 at 10:45
Da PHP-Arrays, soweit ich weiß, intern als Hashmaps umgesetzt sind, wundert mich nicht, dass isset() die schnellste Variante darstellt, da ein Lookup im besten Fall O(1) benötigt. Zwar sind es im Worst-Case O(n), aber ich vermute, dass die PHP-Implementierung bei diesen Größenordnungen ausreichend optimiert ist.
Eine Frage noch: Warum werden als Indizes MD5-Hashwerte verwendet? Nach meinem Verständnis dürften Strings ebenso gut funktionieren, da der Zeitaufwand hauptsächlich vom Hashwert des Index abhängt.
Solltest du diese Variante ausprobieren, würden mich die Ergebnisse interessieren.
@rene: Die Frage ist, wie man eine Menge am effizientesten implementiert. Ich denke, dass der Ansatz von Dominik über eine Hashmap bereits eine gute Wahl ist. Falls du eine gute Mengen-Implementierung findest, sag mir Bescheid. 🙂
Andre
26 Jan 11 at 11:11
Du solltest vielleicht noch beachten, dass dein count() auch einiges an Zeit schlucken dürfte, was du zwei mal innerhalb der Zeitmessung aufrufst.
Und sha1 ist, obwohl es komplexer ist, trotzdem schneller als md5 hab ich gehört.
Ansonsten sieht die Lösung für mich nach einer Liste mit Hashmap auf den Value aus. Das gleiche Prinzip was in PHP bei associativen Arrays genutzt wird, um doppelte Keys zu verhindern.
Das ursprüngliche performenceproblem wird damit allerdings nicht gelöst, nur gemildert.
Du solltest die Erzeugung dieser Suggests auslagern(zb. per cronjob erledigen lassen), so dass du dann beim vervollständigen nur noch das fertige Ergebnis aufrufen musst und es nicht bei jedem mal neu erzeugen musst.
Flyingmana
26 Jan 11 at 11:15
Guter Hinweis das mit dem coutn(), wobei der im Produktiv-Skript natürlich nicht drin ist 😉
Was den Index mit MD5 angeht habe ich mir keine großen Gedanken gemacht, es schien mir in dem Moment logisch, werde da aber ggf. nochmal ein wenig rumexperimentieren, danke.
Das Auslagern der Suggests per Cron macht keinen Sinn, da wir hier von einer direkten Suchanfrage sprechen. Das Skript wird per Ajax vom Suchfrontend angesprochen und soll Ergebnisse liefern. Das Befüllen der Datenbank dahinter ist natürlich ein Cronjob 😉
Dominik Siebel
26 Jan 11 at 11:41
Die in_array() Variante is klar langsam, in_array() muss für jeden insert das komplette array durchsuchen, dasist aufwändig (O(n^2)), der einzelne hah lookup is aber nahezu konstant schnell (O(1))wodurch die zweite Variante sich linear verhält – er muss einmal durhcgehen und es erzeugen (O(n)). Das md5 ist aber überflüssig. PHP arrays sind hashtabllen, d.h. der key wird als Hash gespeihert, dies und warum die Kompläxität ur nahezu O(1) ist gibt es in meinem Blog http://schlueters.de/blog/archives/142-HashTables.html
Johannes
26 Jan 11 at 11:48
Schei* Tastatur 🙂
„…der key wird als Hash gespeichert, dies und warum die Komplexität nur nahezu O(1) ist…“
Johannes
26 Jan 11 at 11:49
array_unique() skaliert zwar besser als in_array(), muss aber trotzdem 2x durch alle Elemente durch. Im Prinzip macht array_unique() nichts anderes als 2x array_flip() aufzurufen. Wenn man also vorher sowieso schon in einer Schleife die Elemente durcharbeitet, spart man sich rund 60% Zeit, wenn man gleich assoziative Arrays verwendet (unbewiesene Behauptung, wenn jemand Lust hat, das nachzuprüfen, freue ich mich über eine Korrektur 😉 )
Es ist IMMER sinnvoll, mit assoziativen Arrays (aka Hashtabellen) zu arbeiten, wenn man viele Elemente handhabt nach deren Wert man suchen muss.
David
26 Jan 11 at 12:43
Vorsicht bei NULL-Einträgen: isset() liefert bei Array-Einträgen, die zwar existieren, allerdings einen Wert NULL haben, false zurück. Könnte man zwar so verwenden, dass Solche Einträge automatisch befüllt werden, wenn man die NULL-Einträge allerdings trotzdem behalten möchte (aus welchem Grund auch immer) liegt array_key_exists() näher.
http://php.net/manual/de/function.array-key-exists.php
Selber Code wie oben (isset() ersetzt mit array_key_exists()) liefert folgende Ergebnisse:
START – count: 50000
END – count: 69666 duration: 0
Ergo kein Performanceverlust.
DukeNightcrawler
26 Jan 11 at 14:28
Guter Hinweis!
Sollte aber in diesem speziellen Fall kein Problem sein, da der Eintrag dann einfach mit einem überschreiben wird, der im Zweifelsfall NICHT mit NULL gefüllt ist.
Nichtsdestotrotz: Die Codeschnipsel sind natürlich nur schnell zusammengeschraubte Beispiele die der Verdeutlichung des in_array()-Problems dienen sollten. Nichts was ohne nähere Beleuchtung in Produktion gehen sollte. 😉
Dominik Siebel
26 Jan 11 at 14:54
Ist es dann nicht schneller auf die if abfrage ganz zu verzichten, wenn jeder Wert eh ein uniq key hat?
Wenn der Wert schon da ist wird er überschrieben mit den gleichen Daten und wenn nicht hinzugefügt.
Nur eine Vermutung.
Tobias
26 Jan 11 at 15:14
Hmm.. Tatsächlich würde das in diesem Fall funktionieren. 🙂
Dominik Siebel
26 Jan 11 at 15:18
Wie siehts bei der Nutzung der SPL aus wie SplFixedArray und SplDoublyLinkedList?
Sven Drieling
26 Jan 11 at 18:24
[…] Here is a german blog post about it (maybe Google translator does a good job?): https://www.phpgangsta.de/php-in_array-die-performance-bremse […]
in_array()’s lame! | patrickburke.de
26 Jan 11 at 20:46
Wir setzen zur Zeit leider noch PHP v5.2 ein.
Beide gibt es erst ab v >= 5.3.
Aber die Performance würde mich schon interessieren. Jemand Erfahrungen damit?
Dominik Siebel
27 Jan 11 at 09:26
SplFixedArray ist ein Array fester Größe, das nur natürliche Zahlen als Indizes erlaubt. Wenn man die Suchanfragen wieder als Schlüssel verwenden möchte, müsste man eine Hashfunktion verwenden, um Schlüssel auf natürliche Zahlen abzubilden. Wenn man dann die gesamten Sonderfälle (z.B. Anzahl der Suchanfragen übersteigt die Array-Größe) miteinbezieht, hat man wahrscheinlich PHP-Arrays in PHP nachimplementiert. Selbst wenn man die Struktur der Suchanfragen in seine Datenstruktur ausnutzen kann, bezweifle ich, dass es sich lohnt, zumal PHP langsamer als C ist. 😉
Aber falls jemand eine Möglichkeit findet, würde es mich sehr interessieren. 🙂
Bei einer doppelt verketteten Liste kann ich mir nur Bäume als effiziente Datenstruktur vorstellen. Da die Suchkomplexität allerdings in O(log n) liegt, bezweifle ich sehr stark, dass sich damit der bisherige Ansatz übertreffen lässt.
Andre
27 Jan 11 at 12:14
Ich hoffe doch, dass Dominik für diesen Beitrag einen elePHPant bekommen hat?
Verdient hat er sich den auf jeden Fall 😉
Karsten
29 Jan 11 at 18:55
[…] PHP in_array() – die Performance-Bremse. […]
Linkhub – Woche 04-2011 | PehBehBeh
31 Jan 11 at 00:40
Und noch ein paar Anmerkungen falls es noch enger wird.
SHA1 ist im Gegensatz zu MD5 kollisionsfrei.
Und wenn du die Werte unter dem Hash speicherst, dann kannst du gleich $result[$random] = 0. Das spart Platz (damit auch Zeit). Dieser Performancegwinn wird ggf. schnell wieder aufgezehrt, wenn mann die Daten für den gebrauch mit array_keys($result) widergewinnen muss.
array_key_exists($key,$result) sollte noch etwas schneller sein, als isset($result[$key]), da der Wert nicht zurückgegeben werden muss.
cxc
14 Sep 11 at 13:42
Ein kleiner – wenn auch etwas später – Hinweis sollte zu „cxc“ Erwähnung finden:
SHA1 ist selbstverständlich nicht völlig „kollisionsfrei“, das kann eine allgemeine Streuwertfunktion (ohne Beschränkung der Definitionsmenge) auch gar nicht sein, da die Zielmenge endlich ist. Eine Kollisionsresistenz ist natürlich gegeben.
cSharp
4 Jan 12 at 10:41
Hey! Wer hätte gedacht, dass lineares Suchen O(n) langsamer ist als eine direkte Adressierung O(1). Jeder der Suchalgos in der Schule hatte sollte sich da nochmal frisch machen 🙂
Mehr dazu:
http://www.tu-ilmenau.de/iti/lehre/ -> Lehre -> EA (Effiziente Algorithmen)
Viel Spaß xDDD
Ortreum
30 Jul 12 at 10:28
Excellent post. I used to be checking constantly this weblog and I’m impressed! Very useful info specifically the final phase 🙂 I maintain such info a lot. I used to be seeking this certain information for a very long time. Thanks and best of luck.
Roger
29 Jan 13 at 17:58
Danke für den Artikel! Hatte in vor 2 Jahren kurz nach erscheinen gelesen. Heute habe ich in gebraucht, um unique Gutscheincodes zu generieren. Vorher hatte ich bei 50000 Codes 964 Sekunden jetzt nur 510 Sekunden! Das ist schon ein stattlicher Unterschied!
Grüße aus Hürth bei Köln
Steffen
14 Mai 13 at 18:35