Archive for August, 2010
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.
