Funkce window.setTimeout v PHP
Školení, která pořádám 
Jeden můj kamarád dostal při pohovoru (nikoliv do Facebooku) zajímavou otázku: „Naprogramuj JavaScriptovou funkci setTimeout v PHP.“ Jak jsem to slyšel, začala mi hlava šrotovat, vymýšlet řešení a narážet na první komplikace ještě dřív, než jsem vzal do ruky tužku nebo klávesnici. A i když jsem si nejdřív říkal, že je to úloha zaměřená hlavně na technické detaily implementace místo na algoritmizaci (o což by mělo jít víc), tak se v ní algoritmus přeci jen použije. Tím pádem se dá rozebrat jeho časová složitost, která je při přímočaré implementaci špatná, ale dá se vylepšit. Prostě mi z toho nakonec vychází perfektní úloha k pohovoru.
Pokud vás úloha taky zaujala, zkuste si ji nejprve vyřešit sami:
Nevíte si s něčím rady? Nejste si jisti, jestli jste na něco nezapomněli? Podívejte se na nápovědu. Časem se dostaneme i k mému řešení.
- Než člověk začne, je dobré si uvědomit, že JavaScript běží v jednom vláknu. To znamená, že i když zavoláme
setTimeout(f, 0), tak se funkce nespustí hned, ale teprve až když doběhne všechno ostatní. Není tedy potřeba lámat si hlavu s nějakým asynchronním plánováním a stačí všechno dávat do fronty a tu na konci spustit. - Zavolali jste na konci skriptu jakousi vaši funkci
processSetTimeout? Srabi! register_shutdown_function neznáte?
Pokud jste nápovědu zohlednili, podívejte se na příklad, který by váš skript měl umět zpracovat.
Příklad použití
<?php Window::setTimeout(function () { echo "Wo"; Window::setTimeout(function () { echo "d!\n"; }, 1000); }, 1000); Window::setTimeout(function () { echo "rl"; }, 1500); echo "Hello "; ?>
Příklad by měl pochopitelně vypsat Hello World!. Mazali jste se místo statických metod s normálními? A není náhodou čas tak trochu globální veličina?
Pokud vám všechno funguje, podívejte se na mé první řešení a porovnejte ho se svým.
Řešení
<?php class Window { static private $timeouts; static function setTimeout(callable $function, $ms) { if (self::$timeouts === null) { register_shutdown_function('Window::shutdown'); } self::$timeouts[] = [ microtime(true) + $ms / 1e3, $function ]; } /** @internal */ static function shutdown() { while (self::$timeouts) { $val = min(self::$timeouts); $key = array_search($val, self::$timeouts); unset(self::$timeouts[$key]); list($time, $function) = $val; $now = microtime(true); if ($time > $now) { usleep(($time - $now) * 1e6); } $function(); } } } ?>
V řešení jsou použity dvě frajeřinky z PHP 5.4 – typehint callable a zkrácená syntaxe polí. Samozřejmě by to fungovalo i bez nich, ale měl jsem nutkavou potřebu ukázat, že jsem in.
Na řešení je zajímavá jiná věc: Samozřejmě mě nejprve napadlo v metodě shutdown prvky setřídit podle cílového času a projít je cyklem foreach. To by ale narazilo v momentě, když by někdo v jednom timeoutu zaregistroval druhý. Takže se timeout vybírá funkcí min. Ta funguje stejně jako porovnávací operátory i s poli podle dokumentovaného algoritmu.
Taky mě nejprve napadlo čas ukládat do klíče ($timeouts[$time][] = $function), ale to narazí na to, že PHP v klíčích pole dovoluje používat pouze celá čísla nebo řetězce. A vynásobení 1e6 by zase přesáhlo maximální velikost celého čísla.
Jaká je časová složitost algoritmu? Nejprve si ji sami odvoďte. Rozmyslete si, jestli by se nedala vylepšit. Pak porovnejte.
Složitost
Funkce min musí prohlédnout všechny prvky pole, takže stojí O(N). Zavolá se O(N)–krát, celkem tedy algoritmus běží v čase O(N²). Zlepšit by se to dalo tak, že bychom prvky do pole průběžně zatřiďovali v čase O(log N) a vždy jen vybrali ten nejmenší. Celkem by se čas tedy zkrátil na O(N * log N). V PHP ale nevím o funkci, která by nám v setříděném poli rychle našla nejbližší prvek a vložila vedle něj další. A pokud bychom si to psali sami, tak je otázka, co by se složitostí udělalo volání funkce array_splice, kterou bychom nejspíš použili.
Teď taková objektová odbočka: Jak se zbavit příznaku @internal a udělat metodu shutdown zvenčí neviditelnou? Máte? Já taky.
Jak se zbavit @internal
Metodu shutdown úplně zrušíme a při registraci zavoláme:
<?php register_shutdown_function(function ($timeouts) { // ... původní obsah metody shutdown }, self::$timeouts); ?>
To ale nestačí – pole se v PHP předávají kopií, takže by se ztratila vazba na vlastnost třídy. A funkce register_shutdown_function nepodporuje předávání parametrů referencí. Vyřešit by se to dalo tím, že bychom ze self::$timeouts udělali objekt. Psát se mi to nechce. Alternativou je nastavit $timeouts = &self::$timeouts a poslat to callbacku přes use (&$timeouts).
Přerušení
Teď je čas to „mírně“ upravit: Co kdybychom se nespokojili s tím, že další funkci stačí zavolat, až když doběhne předchozí kód a místo toho bychom ji chtěli spustit co nejdřív, jakmile bude její čas? Prostě takové přerušení. Následující kód by tedy měl opět vypsat Hello World!:
<?php Window::setTimeout(function () { echo " World"; }, 550); foreach (preg_split('~~', "Hello!\n") as $ch) { echo $ch; usleep(100000); } ?>
Troufnete si? Nejspíš to nebude jen drobná změna, ale fundamentálně odlišné řešení. Zkuste si ho napsat:
Možná si říkáte, že něco takového v PHP nejde. Ale jde.
Použití declare
Řešení spočívá v použití neobvyklé konstrukce declare(ticks = 1). Kamarád mi ani nevěřil, že v PHP něco takového existuje. Ani já jsem to nikdy smysluplně nepoužil, ale tohle je ideální příležitost:
<?php declare(ticks = 1); class Window { static private $timeouts; static function setTimeout(callable $function, $ms) { if (self::$timeouts === null) { register_tick_function('Window::tick'); } self::$timeouts[] = [ microtime(true) + $ms / 1e3, $function ]; } static function tick() { if (!self::$timeouts) { return; } $val = min(self::$timeouts); $key = array_search($val, self::$timeouts); list($time, $function) = $val; if (microtime(true) > $time) { unset(self::$timeouts[$key]); $function(); } } } ?>
Normální program by se tím příšerně zpomalil, protože volání microtime je dost drahé. Celkové řešení bychom navíc museli sestavit kombinací prvního a druhého, já jsem v ukázce záměrně nechal jen to zajímavé. Ale jako řešení u pohovoru by to myslím stačilo.
Závěr
Příklad se mi natolik líbil, že ho asi začnu o pohovorů dávat sám.
Diskuse
mp:
zaujimave je ze v google reader je cely clanok :)mp:
joj slepy som... je aj tu :)
David Grudl 
:
Použil bych na to jednu funkci a speciální konstrukci, která tam existuje od doby, co PHP znám, ale nikdy jsem ji nepoužil. Ona konstrukce je mimochodem zmíněná ve všech knihách o PHP 6 :-)
David Grudl : 
Jakub Vrána :
U pohovoru by mi to asi vadilo. Jednak považuji za zásadní vlastnost setTimeout(), že čeká na doběhnutí spuštěného kódu, což způsob jeho využití zásadně ovlivňuje (zjednodušuje). A jednak by tohle řešení (na rozdíl od toho druhého) bylo nepoužitelně pomalé.
Jakub Vrána : David Grudl :
ad předávání referencí: mělo by jít register_shutdown_function(function () use (& $timeouts) {});
David Grudl : Jakub Vrána :
Fakt to jde, díky. Doplnil jsem to do článku.
Jakub Vrána : David Grudl :
a do třetice: to rozbalování je vážně cool!
David Grudl : Jakub Vrána :
Hlavně když ho musíš dělat po odeslání každého příspěvku do diskuse znovu, co?
Jakub Vrána : paranoiq:
příklad s `declare(ticks = 1)` nebude fungovat. důvodem je to, že ticky nejsou vykonávány v runtimu. namísto toho je volání ticků vloženo kompilátorem přímo do kódu nad kterým jsou deklarovány. opustí-li tedy běh kódu oblast pro kterou jsou ticky deklarovány, přestanou se ticky provádět Jakub Vrána :
Zajímavé, to mě nenapadlo. Takže bychom museli declare(ticks = 1) napsat do všech vložených souborů.
Jakub Vrána : Ugo:
hezký, na tom bych solidně pohořel (co kamarád?). Ale i když jsem to nezkoušel, tak mě napadá, že dávat timeout až na konec nemusí být vždy funkční ne? Když mi script běží 10 vteřin a na začátku dám aby se něco zavolalo po 5 vteřinách, tak předpokládám, že mám asi smůlu, ale jak to vyřešit, když zavolám jiný script nebo přímo php v konzoli, tak zrovna tak se bude čekat na dokončení. btw. co je konstrukce zmiňovaná v knihách o PHP 6? jestli někdo zná opravdu funkční řešení, tak já bych se na něj ze zvědavosti rád podíval.Ugo:
omlouvám se, toho rozbalování je tolik že jsem to nerozbalil celé :-P jdu si hrát s tikánimHonza Prachař:
Mně funguje tohle (ale je tam ten problém, co zmiňuje paranoiq).function setTimeout($c,$d){$t=microtime(1);register_tick_function(function()use(&$c,$d,$t){!$c||1e3*(microtime(1)-$t)>$d?:$c()&$c=0;});}
Jakub Vrána :
Parádní Twitterové řešení. Ale třeba následující kód mi vypíše „ab“, i když by měl vypsat „ba“.
<?php
setTimeout(function () {
echo "a\n";
}, 500);
setTimeout(function () {
echo "b\n";
}, 100);
sleep(1);
;
?>
Navíc to bude ještě pomalejší, protože microtime() se volá pro každou zaregistrovanou funkci zvlášť. Ale o to v tomhle případě zase tolik nejde.
Jakub Vrána : Honza Prachař:
Jasně to bude tím, že "tick" se uděje až po uběhnutí té 1 s, a ty funkce se tím pádem zavolají v tom pořadí, v jakém byly zaregistrovány.Richard Hutta:
Možná by stálo za to,<?php
echo "You have to wait 10 seconds to see this.";
register_shutdown_function('shutdown');
exit;
function shutdown(){
sleep(10);
echo "anything";
}
Richard Hutta:
Ou, sorry nevšiml jsem si té nápovědy :XStanda:
K té složitosti - udržovat setříděné pole je zbytečné. Stačí halda, která se dá na začátku elegantně vybudovat v O(N). REMOVE_MIN a INSERT je pak stejně O(log N), ale aspoň je lepší konstanta.
Stejně si neumím představit udržování setříděného pole v O(log N). To spíš nějaký vyvážený strom, ale jak říkám, setříděnou posloupnost nepotřebujeme.
Jakub Vrána :
Díky, kolego!
Jakub Vrána : 
Michal Gebauer:
Fce. usleep narozdíl od sleep nemůže být přerušena před zadaným časem?
Pokud může být přerušena myslím, že continue po usleep by ošetřilo tento případ.
Michal Gebauer: Franta:
A využití v praxi?
Jakub Vrána :
Já bych si ho docela dovedl představit u nějakého démona – normálně dělá, co potřebuje, a jednou za čas se podívá, jestli není na serveru něco nového.
Jakub Vrána : Franta:
A bude schopný po provedení té akce „jednou za čas“ pokračovat zase v tom, co „normálně dělá“?
Tony:
Mně to přijde jako dost nevhodný příklad na pohovor, právě proto, že k vyřešení je zapotřebí znát funkce, které se,jak jsi sám řekl, vůbec nepoužívají (declare ticks = 1), nebo zneužívat věci, které jsou k úplně jiným účelům (register_shutdown_function).Přijde mi to jako úkol typu "GOTCHA" nebo "AHA, NO JO" - tj. úkol, jehož řešení už znám a pak vypadám jako borec, ale když ho neznám, tak se to bez nápovědy vyřešit nedá. Nepřijde mi to, jako úloha k pohovoru, kde by člověk měl prozkoumat kandidátovo logické myšlení, namísto znalosti obskurních detailů.
Franta:
+1, navíc docela pochybuji o tom praktickém využití (viz výše)
Jakub Vrána :
„Úkol, jehož řešení neznám, se bez nápovědy vyřešit nedá.“
To je nesmysl. Já řešení neznal a úkol jsem bez nápovědy vyřešil.
Jinak register_shutdown_function() a především způsob odloženého provádění kódu v JS považuji za obvyklou znalost „seniornějších“ vývojářů.
Jakub Vrána : Tomáš Ludvik:
v PHP 5.3 jsou ticky deprecated a v PHP 6 budou odebrány, viz. http://www.tuxradar.com/practicalphp/4/21/0Diskuse je zrušena z důvodu spamu.
© 2005-2024 