Zákeřné pole
Školení, která pořádám 
PHP pro uložení polí používá hashovací tabulky. Ty fungují tak, že při uložení každého prvku spočítají hash jeho klíče a prvek uloží do tabulky na základě této hodnoty (kromě toho se udržuje ještě spojový seznam prvků, aby se prvky daly procházet v tom pořadí, v jakém byly vloženy). Hashovací tabulky mají řadu užitečných vlastností, především dokážou prvek uložit a vyhledat v průměrném případě v konstantním čase (při přepočtu na jeden prvek). To znamená, že ať je pole jak chce veliké, tak základní operace s ním budou vždy rychlé.
<?php /** Vytvoření zákeřného pole * @param int hloubka zanoření ovlivňující počet vytvořených prvků * @param string předpona klíčů * @return array pole s prvky se stejným hašem klíčů */ function zakerne_pole($depth, $prefix = "", $i = 7) { if (!$depth) { return array($prefix => true); } $return = array(); for ($j=0; $j <= 7; $j++) { $b = 33 * (7 - $i) + $j; $return += zakerne_pole($depth - 1, $prefix . chr($b), $j); } return $return; } ?>
Jak je tedy možné, že je tato funkce tak příšerně pomalá a přitom se při změně konstanty 33 zázračně zrychlí? Důvodem je, že hash všech vytvořených klíčů je stejný – PHP pro výpočet hashe používá jednoduchou funkci Times 33, která pracuje tak, že hash nejprve nastaví na 5381 a pak postupuje po bajtech klíče, starý hash vždy vynásobí číslem 33 a přičte hodnotu bajtu. Možná si říkáte, proč není použitá nějaká osvědčená hashovací funkce jako třeba md5, u které by se pro nalezení kolize hodilo mít ve jméně W a G? Důvodem je rychlost – ostatně podívejte se do funkce zend_inline_hash_func, jak se jednoduchý algoritmus dá kvůli optimalizaci popsat složitě.
Diskuse
David Grudl:
Jakube, nechtěl bys to W a G rozvést? Slyším o tom poprvé a docela by mě to zajímalo.
David Grudl: 
Jakub Vrána 
:
To byl jen takový vtípek: http://en.wikipedia.org/wiki/Xiaoyun_Wang
Jakub Vrána : david@grudl.com:
Taktos mě dostal ;)
Ale ať taky přispěju s troškou do mlýna zákeřních polí. Zkuste si v libovolné verzi PHP od 5.0.0 do 5.1.2 spustit tento kód:
<?php
$arr = array();
$arr['XB@'] = 'La';
$arr[2089710047] = 'Trine';
unset($arr['XB@']);
?>
Unset překvapivě odstraní prvek arr[2089710047]. Také to souvisí s hashovací funkcí.
david@grudl.com: 
v6ak:
Nějak jim chybí použití kolizní funkce...
v6ak: Karel:
Znamená to, že PHP je v případě polí nespolehlivé?(A btw. existuje k tomuhle nějaký white-paper nebo bug report?)
spaze:
Není, bylo. A to ve verzích 5.0.0 do 5.1.2, jak je psáno. Ale v těch verzích toho bylo špatně asi více ;)
spaze: Miloslav Ponkrác:
Já, když jsem psal svůj padesátidílný seriál o PHP na zive.cz, kde jsem tehdejší tuším ještě 5.0.2 po testech doporučil nepoužívat jako nespolehlivé a zatím zůstat u PHP 4. A jak se do mě pan Vrána pustil, co si to dovoluji tvrdit. Jakub Vrána :
Napsal jsem „autor … by to měl podložit nějakými argumenty“. To se mi nezdá úplně jako „puštění se“. Já PHP 5 používám od celkem raných verzí a problémy s ním jsem nikdy neměl větší než s PHP 4. http://www.zive.cz/Clanky/PHP--50-dil--budoucnost-…#ITEM_366001
Navíc konkrétně tato chyba se projevovala i do PHP 4.4.2: http://latrine.dgx.cz/php-surprise, takže to není příliš pádný argument o kvalitě PHP 4 ve srovnání PHP 5…
Jakub Vrána : PHX:
Nejak mi nejde do hlavy, proc dane funkci vadi stejne hase. Spise bych cekal, ze to nebude fungovat, kdyz si to prepisuje prvky pole.Dale mi prijde ze hash funcek Times33 musi dle tveho popisu vracet s rostoucim klicem roustouci cislo. Pri dlouhem klici se cislo hase bude blizit "nekonecnu". Osobne mam o hash predstavu, ze vraci vzdy konstantni delku vyledku.
Jakub Vrána :
Protože dva prvky se stejným hashem se zapíšou do tabulky na stejné místo. Toto místo je pak potřeba prohledat ručně, takže složitost přidání prvku není konstantní, ale lineární.
Ano, číslo se neustále zvětšuje, ale pracuje se jen s posledními 32 bity.
Jakub Vrána : Jakub Vrána :
Jak objevil David Grudl, funkce správně funguje jen v PHP 5, protože PHP 4 používá jinou hashovací funkci (místo plus provádí xor).
Jakub Vrána : pmg:
Děkuji za pěkný článek. Podle jakého vzorce stanoví PHP velikost hašovací tabulky, aby to bylo tak akorát? Jakub Vrána :
Při inicializaci se velikost tabulky nastaví na nejbližší ne-menší mocninu dvojky vzhledem k počtu prvků v poli. Když počet prvků v poli přesáhne velikost tabulky, tak se tabulka zdvojnásobí. Tabulka se nikdy nezmenšuje.
Jakub Vrána : Bohdan:
Tomuto problému lze předejít tak, že se funkce vybere náhodně z nějaké 2-universální množiny (to jsou takové množiny hashovacích funkcí, že při náhodném výběru funkce z té množiny je pro každé dvě různé položky, které chceme zahashovat, pravděpodobnost kolize menší než 1/(velikost hashovací tabulky) – což zaručuje průměrné konstantní časy základních operací).Vlastní hashovací funkce jsou potom pořád velmi rychlé a náhodný výběr funkce (v praxi většinou vygenerování dvou celých čísel) se nemusí provádět pro každé pole, stačilo by jednou pro skript nebo dokonce spuštění php.
Docela by mě zajímalo, proč to dělají takhle...
Jakub Vrána :
Řekl bych, že PHP jde cestou nejmenšího odporu. Na reálných datech ke kolizím prakticky nedochází, takže nikdo neměl potřebu se tím zabývat. A nakonec může být výhodou i rychlejší průměrný případ (byť jen konstanta-krát) proti pomalejšímu nejhoršímu (přestože řádově).
Jakub Vrána : kuba:
prosim vas...jak mam udelat v php text ze ktereho se vykresly tabulka??Diskuse je zrušena z důvodu spamu.
© 2005-2024 