PHP hat Ticks
Vor einigen Tagen hatte ich mit einem meiner Kollegen in der Firma ein Gespräch über Profiler (XDebug). Dabei erzählte er dass er vor einiger Zeit einen rudimentären Profiler gebastelt hat der ähnliches kann wie XDebug heute: Sein Profiler konnte die Laufzeit eines jeden Befehls in einem Script feststellen und in eine Datenbank loggen. Außerdem bekam er Informationen wie oft jede Funktion von irgendwo aufgerufen wurde, er konnte auch sehen von wo genau. Somit war es ihm möglich die langsamsten Teile seiner Software herauszufinden und diese zu beschleunigen.
XDebug und auch der Zend Debugger können genau das selbe und noch viel mehr, trotzdem wollte ich wissen wie man das macht ohne eine entsprechende Extension. Dazu hält PHP die unbekannte Funktion register_tick_function() bereit, die man mit einem Callback füttern kann. Diese Callback-Funktion wird dann bei jedem Tick aufgerufen. Ein Tick ist einfach ausgedrückt jeder low-level-Befehl in einem Script, darunter fallen Zuweisungen, Funktionsaufrufe usw. Im Prinzip fast alles außer Kontrollstrukturen (if, switch, while etc).
Hier ein kleines Script, das die Funktionsweise erklärt:
<?php
function profiler()
{
debug_print_backtrace();
}
register_tick_function('profiler');
echo "First echo\n";
declare(ticks = 1);
echo "Second echo\n";
echo "Third echo\n";
echo "Before function echo\n";
$i = md5('text');
echo "After function echo\n";
Die Ausgabe sieht wie folgt aus:
First echo #0 profiler() called at [/private/tmp/tick.php:12] #0 profiler() called at [/private/tmp/tick.php:12] Second echo #0 profiler() called at [/private/tmp/tick.php:13] Third echo #0 profiler() called at [/private/tmp/tick.php:14] Before function echo #0 profiler() called at [/private/tmp/tick.php:15] #0 profiler() called at [/private/tmp/tick.php:16] After function echo #0 profiler() called at [/private/tmp/tick.php:17]
Man sieht dass profiler() nach jedem Befehl aufgerufen wird. In Zeile 12 wird sie zweimal aufgerufen, einmal für die Zuweisung und einmal für den Funktionsaufruf. Man erkennt auch dass das echo in Zeile 10 keinen profiler() Aufruf zur Folge hat. Das liegt daran dass mit dem Aufruf von declare() erst festgelegt wird wie oft die tick-Funktion aufgerufen werden soll. Diese Zeile aktiviert also das ganze. Auf php.net findet man auch einige Beispiele von Usern zu declare() und den Möglichkeiten.
Wer also nicht zu XDebug greifen möchte (oder kann) sollte, bevor er mühsam jede Menge microtime() und debug_backtrace() Aufrufe einbaut diese Möglichkeit in Betracht ziehen.
Mein Spielplan-Algorithmus
Vor 2 Wochen hatte ich ja dazu aufgerufen ein algorithmisches Problem zur Berechnung eines Spielplan zu lösen. Es gab in den Kommentaren einige gute Ansätze und auch eine gültige Lösung wenn ich es richtig gesehen habe, und wie versprochen werde ich heute meine Lösung veröffentlichen.
Vielleicht sollten wir uns nochmal das Grundproblem ins Gedächtnis rufen:
Wir haben folgende Ausgangslage: X Spieler möchten ein Turnier veranstalten, wobei jeweils einer gegen einen spielt (Duelle, deshalb sollte X gerade sein). Dabei soll jedoch niemand mehrfach gegen den selben Spieler antreten und es soll niemand ein Spielbrett zweimal benutzen dürfen. Es gibt X/2 Spielbretter, also auch für jeden Spieler X/2 Duelle.
Meine erste Lösung war recht schnell und auf den ersten Blick coole Lösung, ABER auch dieser Code hat das Problem dass es doppelte Paarungen gibt. Dieses Problem hatten fast alle Lösungen aus den Kommentaren auch.
Grundsätzlich funktioniert der Algorithmus wie folgt (bei 10 Spielern): Ich fülle am Anfang ein 5*5 Array, worin jede Zelle alle Spielernummern (0-9) enthält. Dann ziehe ich aus dem ersten Feld 2 zufällige Spieler, lösche alle anderen Einträge aus dieser Zelle und lösche diese beiden gezogenen Spieler auch aus der restlichen Zeile und Spalte. So stelle ich sicher dass ein Spieler nur einmal pro Runde und einmal auf jedem Spielfeld spielt. Das mache ich nun so lange bis ich eine Zelle finde wo es keine 2 Spieler mehr gibt, dann resette ich zum Anfangsarray ($startGrid) und beginne von vorn.
<?php
$player = 10;
$rounds = $player/2;
$startGrid = array();
$startTime = microtime(true);
for ($i=0; $i<$rounds; $i++) {
for ($j=0; $j<$rounds; $j++) {
$startGrid[$i][$j] = range(0, $player-1);
}
}
while (true) {
$grid = $startGrid;
for ($j=0; $j<$rounds; $j++) {
for ($i=0; $i<$rounds; $i++) {
if (count($grid[$i][$j]) < 2) {
continue 3;
}
$randomEntries = array_rand($grid[$i][$j], 2);
$first = $grid[$i][$j][$randomEntries[0]];
$second = $grid[$i][$j][$randomEntries[1]];
$grid[$i][$j] = array($first => $first, $second => $second);
for ($z=0; $z<$rounds; $z++) {
if ($z != $i) {
unset($grid[$z][$j][$first]);
unset($grid[$z][$j][$second]);
}
}
for ($z=0; $z<$rounds; $z++) {
if ($z != $j) {
unset($grid[$i][$z][$first]);
unset($grid[$i][$z][$second]);
}
}
}
}
outputPlan($grid);
echo "\n".round((microtime(true)-$startTime), 2)." seconds\n";
exit;
}
function outputPlan($grid) {
global $rounds;
for ($i=0; $i<$rounds; $i++) {
for ($j=0; $j<$rounds; $j++) {
echo str_pad(join('-', $grid[$i][$j]), 25);
}
echo "\n";
}
}
Nachdem ich das Problem mit den doppelten Paarungen entdeckt hatte musste ich also nochmal überlegen und bin zu folgenden Code gekommen, der deutlich langsamer ist, aber (glaube ich) gültige Ergebnisse ausspuckt. Ich habe einen ähnlichen Ansatz wie beim ersten Versuch, speichere in jeder Zelle jedoch nicht alle Spieler, sondern alle Spielpaarungen.
<?php
$player = 10;
$rounds = $player/2;
$startTime = microtime(true);
$gameTable = array();
for ($i=0; $i<$player; $i++) {
for ($j=$i+1; $j<$player; $j++) {
$gameTable[] = array($i, $j);
}
}
$startGrid = array();
for ($i=0; $i<$rounds; $i++) {
for ($j=0; $j<$rounds; $j++) {
$startGrid[$i][$j] = range(0, count($gameTable)-1);
}
}
while (true) {
$grid = $startGrid;
for ($j=0; $j<$rounds; $j++) {
for ($i=0; $i<$rounds; $i++) {
if (count($grid[$i][$j]) == 0) {
echo "Abbruch in $i/$j\n";
continue 3;
}
// Randomly pick one game
$randomEntryIndex = array_rand($grid[$i][$j]);
// remove all others in that cell
$grid[$i][$j] = $randomEntryIndex;
// remove all games from rest of row which have players in it we picked above
for ($z=$i+1; $z<$rounds; $z++) {
foreach ($grid[$z][$j] as $game) {
if (in_array($gameTable[$randomEntryIndex][0], $gameTable[$game]) ||
in_array($gameTable[$randomEntryIndex][1], $gameTable[$game])) {
unset($grid[$z][$j][$game]);
}
}
}
for ($z=$j+1; $z<$rounds; $z++) {
foreach ($grid[$i][$z] as $game) {
if (in_array($gameTable[$randomEntryIndex][0], $gameTable[$game]) ||
in_array($gameTable[$randomEntryIndex][1], $gameTable[$game])) {
unset($grid[$i][$z][$game]);
}
}
}
// remove all occurences of that exact match
for ($k=0; $k<$rounds; $k++) {
for ($l=0; $l<$rounds; $l++) {
if (!($k==$i && $l==$j)) {
unset($grid[$k][$l][$randomEntryIndex]);
}
}
}
}
}
outputPlan($grid);
echo "\n".round((microtime(true)-$startTime), 2)." seconds\n";
exit;
}
function outputPlan($grid) {
global $rounds, $gameTable;
for ($i=0; $i<$rounds; $i++) {
for ($j=0; $j<$rounds; $j++) {
echo str_pad(join('-', $gameTable[$grid[$i][$j]]), 25);
}
echo "\n";
}
}
Ja, ich weiß, nicht schön („global“ etc.), aber funktioniert, wenn auch langsamer als Fabians Lösung aus den Kommentaren des Aufruf-Artikels. Er sagte mir dass er mehrere Abende daran gesessen hat und die Lösung sein achter oder neunter Ansatz gewesen sei. Wirklich respektabel wie er sich da reingearbeitet und diese schöne Lösung erstellt hat.
Linkpool Nummer 10
Toller neuer HTML5 Editor. Ist das Ende von TinyMCE endlich in Sicht?
http://aloha-editor.com/
10 Dinge über Software-Entwicklung, die man nicht an der Uni lernt
http://it-republik.de/jaxenter/news/10-Dinge-ueber-Software-Entwicklung-die-man-nicht-an-der-Uni-lernt-055679.html
Nette Übersicht der memcache(d) Extensions:
http://brian.moonspot.net/php-memcached-issues
XDebug 2.1 ist raus:
http://derickrethans.nl/xdebug-2.1-released.html
SSH-Server in PHP:
http://blog.magicaltux.net/2010/06/27/php-can-do-anything-what-about-some-ssh/
Falls man mal nicht weiß was man als Commit Message eingeben soll:
http://whatthecommit.com/
PDT 2.2 (Eclipse Helios 3.6)
http://www.zend.com/community/pdt
CouchDB in Version 1.0 released:
http://couchdb.apache.org/
PHP Entwicklung unter Android:
http://www.heise.de/newsticker/meldung/PHP-Entwicklung-unter-Android-1037940.html
Zum Testen von SMTP Servern und Clients nützlich: Der Python-SMTP-Sink Einzeiler:
http://www.jurecuhalev.com/blog/2009/12/03/python-smtp-sink-server/
Die grüne Suchmaschine rettet den Regenwald (Searchengines Bing/Yahoo stecken dahinter)
http://ecosia.org/
Gewinner der großen Geburtstagsverlosung
Es ist soweit, die Geburtstags-Aktion ist beendet und nun werden wir die Gewinner der Preise bestimmen. Erst einmal an dickes Dankeschön an alle, die mitgemacht haben, fleißig getwittert und gebloggt haben und somit insgesamt 155 Kommentare zusammengekommen sind. Davon sind 2 Einträge Trackbacks, 2 Einträge waren Ergänzungen um Twitter-Links, und 3 Einträge sind ungültig, mehr dazu ganz unten. Wir haben also 148 gültige Kommentare, die wir nun in den Lostopf werfen. Auch hier nochmal ein großes Dankeschön an die Verlage und Firmen, die die Preise zur Verfügung gestellt haben!
Um nun die Gewinner zu bestimmen habe ich ein kleines PHP-Script geschrieben welches uns ganz unparteiisch eine Liste von Namen ausspuckt. Das Verfahren ist von jedem von euch nachvollziehbar, es steckt kein Zufall drin, sondern nur eine besonderer Berechnung der Reihenfolge. Und zwar werden diejenigen gewinnen, bei denen der MD5 der Email-Adresse möglichst „nah“ am MD5 des Beginns der Aktion (sprich dem 1. Geburtstag) liegt.
Der Blog feiert 1. Geburtstag! Mit großer Verlosung!
Mit kleiner Verspätung können wir heute den ersten Geburtstag dieses Blogs feiern! Vor knapp mehr als einem Jahr begann ich zum ersten Mal mit WordPress einen eigenen Blog zu erstellen und mit PHP- und allerlei Webthemen zu füllen. Mittlerweile sind es 141 Artikel geworden und mit der Zeit hat sich dann auch der ein oder andere Leser hierher verirrt sodass es einer der größten deutschen PHP-Blogs ist.
Ich möchte mich natürlich bei euch, meinen Lesern, dafür bedanken, und dazu habe ich eine reiche Geschenksammlung zusammengestellt, mit freundlicher Unterstützung vieler Firmen, denen ich hier nochmals sehr danken möchte. Der Gesamtwert der zu verlosenden Gegenstände beträgt über 875 Euro!!
Folgendes gibt es zu gewinnen (wie das geht lest ihr weiter unten):
- Einen Business VServer für 12 Monate von Greatnet.de
- 5 Personal Licenses für die neue PHP-IDE PHPStorm von JetBrains
- 2 Bücher Agile Prozesse – Fallstricke erkennen und vermeiden 284 Seiten von Entwickler-Press
- 2 Bücher High Performance LAMP – Lastsituationen großer Websites planen und meistern 210 Seiten von Entwickler-Press
- 2 Bücher IT-Performance richtig testen und optimieren 250 Seiten von Entwickler-Press
- 1 Buch Fortgeschrittene CSS Techniken 436 Seiten von Galileo Press
- 1 Buch PHP 5.3 und Mysql 5.5, 1085 Seiten von Galileo Press
- 1 Buch Apache 2.2 – Das umfassende Handbuch 947 Seiten von Galileo Press
- 5 Planning Poker Sets von holisticon.de (1 Preis)
- 2 Gutscheine für das Webdeveloper Paket von demobereich.de (einmal 3 Monate und einmal 6 Monate)
- 3 Ausgaben des t3n Magazins von yeebase media
21 wertvolle Preise für 21 Gewinner, Wahnsinn.
Der Business-VServer von Greatnet.de bietet 768 MB Arbeitsspeicher, 750 GB Traffic, reichlich Rechenpower, Inklusiv-Domains und alles was ein Webmaster für mittelgroße Projekte benötigt.
Greatnet.de ist seit 1999 auf die Bereitstellung von professionellen Hosting-Lösungen spezialisiert. Neben dem reinen Hosting bietet der Haushamer ISP (Internet Service Provider) auch komplexe Infrastrukturen für Kommunikationsdienste an – für jede Zielgruppe und ihren jeweiligen Bedarf.
Die neue IDE von JetBrains namens PHPStorm will Eclipse, Netbeans und Zend Studio angreifen und dem Entwickler mit aktuellen Features unter die Arme greifen. Auch ohne PHPDoc ist eine Autovervollständigung möglich, PHPUnit ist integriert und mit einem Klick ausführbar. Seit einigen Monaten ist PHPStorm verfügbar, natürlich auch als full-featured Trial Version. Da es bereits auf der diesjährigen IPC einen Vortrag über PHPStorm gab werde ich bald einen extra Artikel veröffentlichen wo ich mir die Software im Detail anschauen werde.
Jeder von euch hat wahrscheinlich auch mindestens ein Buch des Galileo Press Verlags im Bücherschrank stehen. Besonders interessant finde ich die openbooks auf der Webseite, sprich kostenlose EBooks zu IT-Themen! Tipp: Angucken!
Galileo Press ist ein erfolgreicher, deutscher Fachbuch-Verlag, der unter seiner Marke Galileo Computing IT-Bücher und Video-Trainings publiziert. Der Verlag unterstützt mit seinem IT-Programm sowohl Experten als auch ambitionierte Einsteiger, die sich in ihrem Fachgebiet optimal und professionell weiterbilden wollen. Die Autoren und Trainer sind Experten ihres Fachs und vermitteln anschaulich und praxisnah das notwendige Know-how.
Allen Spendern ein GROSSES GROSSES DANKESCHÖN!
Doch nun genug Werbung, ihr wollt wahrscheinlich wissen wie ihr teilnehmen könnt, oder? Das ist ganz einfach: Hinterlasst einen Kommentar hier im Blog, inklusive Email-Adresse, und schon seid ihr mit einem Los im Lostopf! Einfacher gehts nicht, um diese tollen Gewinne abzustauben! Wer seine Chancen etwas erhöhen möchte bloggt/twittert über diesen tollen Tag und hinterlässt hier natürlich auch einen Kommentar mit seiner Email-Adresse, damit ich das Geschriebene auch finde. Ihr erhaltet dann dafür 3 Lose im Topf.
Am Dienstag Abend (13.07.2010) um 23:59 werde ich die Lostrommel füllen und dann wird natürlich ein PHP-Script die Gewinner ermitteln. Es wird kein einfaches Zufalls-Script sein, sondern mit Hilfe eines bekannten Algorithmus die Gewinner herausfinden, es wird für jeden nachvollziehbar sein. Ihr dürft gespannt sein!
Danke also nochmal an Euch, ohne Euch würde das Schreiben nur halb soviel Spass machen!
Michael
