jakubův notes – programování a vejšplechty

Píšu o:

Trine & WINE

Trine je skákačka/plošinovka, o které jsem se dozvěděl díky článku na Jasperově zápisníku. V ukázkách se dozvíte, že na jakési království sestoupilo temno. Vžijete se do kůže zloděje, který se snaží ukrást, co se najde, z polorozbořeného hradu. Když se dostanete do sálu s pokladem, otevřete truhlu a jeden kámen, jakýsi drahokam, vás k sobě přychytí a nepustí. Teď jste kouzelník – slyšeli jste hluk (jak jste se jako zloděj vlámali do truhly s drahokamem), a tak se jdete podívat, co se děje. Drahokam vás téže polapí. Nakonec je tu ještě rytíř, který se taky zajímá, co se děje. Když se dotkne kamenu, drahokam se rozzáří a ze všech tří postav se stane jedna – za tu odteď budete hrát. Zajímavé je, že se můžete měnit vždy do jedné z původních postav.

Podle WINE AppDB by hra měla jít pod WINEm spustit. Úspěch se dostavil, a tak tu je tenhle návod. Testováno s WINE verze 1.1.29.

Nejprve ze všeho budete potřebovat winetricks. Skript si stáhněte, učiňte spustitelným a umístěte někam do PATH. Poté spusťte:

$ winetricks d3dx9

Čímž nainstalujete různé DirectX knihovny. Následně budete ještě potřebovat kodeky kvůli „videím“ ve hře. Ty můžete získat společně s Window Media Playerem:

$ winetricks wmp10

WMP trochu pozlobil – po instalaci, ale ještě před dokončením práce winetricks, se spustil a chtěl do své knihovny naimportovat veškerou hudbu v počítači. Když jsem rezolutně odmítl, urazil se a SEGFAULTnul. Při druhém spuštění winetricks již vše proběhlo v pořádku.

V případě, že se teď pokusíte Trine sputit, tak na vás vybafne chyba o nenalezení knihovny PhysXLoader.dll. Běžte tedy na stránky nVidie a stáhněte drivery. Přejděte do adresáře se staženým souborem a pomocí WINE nainstalujte:

$ wine PhysX_9.09.0814_SystemSoftware.exe

Přejděte do drive_c/Program Files/Trine, jinak dostanete akorát chybu o nenalezení dat. Trine můžete samozřejmě nainstalovat do jiného než výchozího WINEPREFIXu – aby se zbytečně nemíchal s ostatními věcmi. Já například zvolil ~/.wine.trine. Pak může posloužit jednoduchý skript, který zařídí vše potřebné:

#!/bin/sh
export WINEPREFIX="$HOME/.wine.trine"
cd "$WINEPREFIX/drive_c/Program Files/Trine"
exec wine "$WINEPREFIX/drive_c/Program Files/Trine/trine.exe"

Uložte třebas jako trine, upravte WINEPREFIX, učiňte spustitelným a přesuňte do nějakého adresáře, kam ukazuje PATH.

$ trine

A už se jede :-)

vydáno 6. 9. 2009, 20:37:28

žádný komentář

Zařazeno mezi:

B+Tree v PHP

Když jsem konečně rozchodil metatable, byl to prakticky tantrický okamžik. Och, ono to vážně funguje! A ukládá! A vybírá! Jako když malé děcko dostane lízátko. Navíc, já jsem si to lízátko sám i udělal.

Ale neusnul jsem takříkajíc na vavřínech a šel jsem ještě dál. Když si vezmete snad jakoukoli databázi, tak najdete B+Tree, další B+Tree a ještě více B+Tree. Inu, proč se neinspirovat a neudělat taky takový B+Tree? Samozřejmě zcela v PHP.

A tak vznikla třída btree, která umí spravovat B+Tree uložený v souboru. API je opět minimalistické a bude vám stačit osvojit si jen pár metod – v případě btree si vystačíte s polovinou metod než u metatable (celkem tedy se třemi). Okolo metatable jsem udělal velký humbuk, u btree se spokojím s oznámením tady na blogu.

GitHub jsem si docela oblíbil, takže opět můžete zdrojový kód získat z repozitáře právě tam:

$ git clone git://github.com/jakubkulhan/btree.git

Nejdříve ze všeho je potřeba si vytvořit instanci. Zase je tu statická metoda open():

$btree = btree::open('my.tree');

Klasicky (alias stejně jako u metatable), pokud vše proběhlo v pořádku, open() vrátí novou instanci btree, jinak FALSE. Proč všude cpeš „oupn“ metodu? Samozřejmě by šlo nechat konstruktor jako public a v případě nějaké chyby vyhodit výjimku. Avšak nemohu si pomoci – výjimky prostě nemám rád. Objekty jsou naprosto skvělé, dokonce i do Céčka (takový ten dřevní jazyk; jen pro fajnšmekry) přenáším některé své návyky z OOP. Ale výjimky? Dílo ďáblovo! Hlavně, když dělají něco, co by člověk nečekal.

Když už jeden má instanci btree, bylo by záhodno si do stromu něco uložit:

$btree->set('key', 'value');

(Opravdu jsem nepřišel na chytřejší název metody.) Narozdíl od metatable může jít jako druhý argument, jako hodnota, cokoli, co se dá serializovat, a ne jen určité typy. Ale stejně jako je tomu u metatable, vymazání určitého klíče se provádí přiřazením NULL:

$btree->set('key', NULL);

Pro získání je jako u metatable metoda get():

assert($btree->get('key') === 'value');

Tohle je všechno, co budete potřebovat, budete-li chtít použít B+Tree. Minimalistická API, to je moje.

U metatable jste se museli starat o uzavírání – buď předáním flagu AUTOCLOSE při otevírání nebo ručně. U btree tomu tak není, protože veškeré úpravy stromu probíhají append-only – tzn. že se nikdy nepřepisují již zapsaná data. Má to hodně výhod. Nemusíte se bát, že by se data nějak poškodila. Prakticky nejsou potřeba zámky (bohužel jsem nevymyslel, jak udělat set() bez zamykání; ale zatímco jedna instance zapisuje, můžete stále v klidu číst pomocí get()). A také to znamenalo velké zjednodušení kódu oproti metatable, kde k zajištění konzistence dat se všechno muselo kopírovat do *~handle souboru.

Co se tedy stane, pokud např. v prostředku zápisu nějakých dat btree vypadne elektřina? Nepůjde to vysvětlit bez toho, abych popsal formát souboru.

Jelikož strom se skládá z jednotlivých uzlů, tak i soubor se musí skládat z uzlů. Navíc se uzly do souboru musí ukládat „ploše“, jelikož soubor je jako jeden dlouhý řetězec jedniček a nul. Každý uzel v souboru je reprezentován jako 32-bitové bezznaménkové číslo (formát N pro pack()) následované počtem bytů uložených právě v tom čísle. První dva byty určují typ uzlu a pak je serializovaná podoba uzlu.

Jsou pouze dva typy uzlů – kp a kv. První typ – kp (key-pointer) – je asociativní pole obsahující dvojice (klíč, ukazatel), kde ukazatel je integer ukazující na jiný uzel (offset uzlu v souboru). Druhý – kv (key-value) – je vždy listem stromu a obsahuje již dvojice (klíč, hodnota). Nebudu nic zapírat, inspirací pro mě byla CouchDB.

CouchDB B+Tree

CouchDB B+Tree (reduce hodnot si nevšímejte, tohle má CouchDB kvůli pohledům a btree žádné pohledy nemá)

„Vždy“ na konci souboru je ukazatel na kořen stromu následovaný „hlavičkou“ sestávající z řetězce "\xffbtree" (\xff je byte plný samých jedniček).

Řekněme tedy, že ukládáme nějakou hodnotu. Jak se tomu u B+Tree dělá, traverzujeme stromem až do listu (kv uzlu), kam by hodnota měla být uložena. Udělá se vše potřebné (rozdělování/slučování uzlů) a postupně se všechny ovlivněné uzly zapisují do souboru – připojují na konec. Na závěr je připojena nová poloha kořene s novou hlavičkou a je vynucen zápis na disk. Když se kdykoli od začátku zápisu do doby, než je všechno úspěšně na disku, něco stane, btree si z toho nic nedělá: Je zapsána třeba jen polovina uzlů? Chybí hlavička? To mě nerozhází!

Při hledání kořene se totiž ověřuje, jestli je na konci souboru opravdu celá hlavička, a pokud ne, btree se od konce souboru dobírá k poslední úspěšně zapsané hlavičce. (Pozor tedy – uložením řetězce "\xffbtree" můžete btree pěkně pomotat hlavu!) To je celé kouzlo. Žádné opravovací algoritmy, nebo žurnály nejsou potřeba, protože i když je soubor „rozbitý“ nedokončeným zápisem, strom je v posledním konzistentním stavu. Všechna data, na která není odkazováno, jsou považována za „neexistující“.

vydáno 21. 8. 2009, 23:15:13

žádný komentář

Zařazeno mezi:

A proč vám nevyhovuje Git?

Netuším, jestli je to tím, že dříve jsem měl „práce až nad hlavu“ a teď se „flákám“, takže mám více času sledovat internetové dění; nebo se prostě teprve teď něco děje. Ale Git a vůbec opouštění SVN a přechod na nějaký DVCS je v poslední době dost žhavé téma. Už asi nezjistím, kdo s tím začal jako první. Ale nějaký počáteční impuls, a to dosti silný tu být musel.

Nejspíš to je díky tomu, že se to přivalilo z více směrů:

  1. @karmi nahlodal Davida Grudla. Takže se teď rozhoduje, jestli Nette bude používat Git, nebo Mercurial (možnost zůstat u SVN, zdá se, už nepřipadá v úvahu).

  2. @dmajda zase šťouchl do Borka Bernarda, který rozpoutal diskusi na téma GUI vs. příkazová řádka.

Nejdřív k druhému bodu. Shrnu to krátce. Byl jsem rád, že jsem mohl taky přihodit do diskuse pár postřehů. A musím souhlasit s tím, že Google Docs jsou pro kolaboraci bída s nouzí. A je vidět, jak lidé ze světa Windows a UNIXu mají neuvěřitelně rozdílný pohled na to, co je důležité (pozor, tím se nesnažím nikomu vnutit, že zrovna hodnoty UNIXu jsou ty důležité (i když podle mě samozřejmě jsou)). Hezky je to popsané v článku Joela Spolského Biculturalism.

Teď k věci první, a tedy přechodu Nette. Toto je pro mě trochu důležitější téma, než jestli se někomu líbí více GUI, nebo příkazová řádka, protože přeci jenom mám jednu aplikaci na Nette, kterou budu muset asi ještě chvilku udržovat.

Na úvod musím říct, že můj pohled může být zkreslený, protože celá „éra“ CéVéeSek a eSVéeNek se mi nějak vyhla. SVN použiji maximálně stylem checkout, make, make install, cd .. && rm -rf foo. Takže můj pohled na centralizované vs. distribuované VCS je a bude zkreslený. Stejně jako je a bude zkreslený pohled všech, kteří používají některou z centralizovaných mršek (myšleno v nejlepším slova smyslu, slovo „mrška“ využívám skoro pro všechno).

Co je tedy tím největším problémem, proč ne Git? Čeho se všichni bojí? Kvůli čemu se povedou svaté války? Čekal jsem, že by tím mohla být workflow. Pro efektivnější využívání možností DVCS se workflow bude trochu lišit. Ale tohle většina lidí přešla. Asi bez toho, že by DVCS použila v akci (alespoň pro nějaké Hello, world!). Vítězem v „nepoužitelnosti“ Gitu je:

Čísílkování revizí. Toto trápí nejvíce lidí! „V revizi FOO přibyla nějaká fičurka. Já mám BAR. Podle hashe nepoznám, jestli bude fičurka fungovat,“ je odevšad slyšet. Jak jsem psal, na SVN jsem nevyrůstal, takže nechápu, proč zrovna tuhle věc lidé shledávají tak úžasnou. Když jim člověk řekne, že pokud se nechtějí vzdát čísílek, mohou je vytvářet jako tagy, tak jenom slyší: „Proč bych tedy měl přecházet na Git, když SVN tak krásně čísluje samo od sebe?“ I když některé věci lidé shledávají na DVCS skvělé, nedokáží se odpoutat od pár generovaných čísílek.

Spíše by se ale člověk měl ptát sám sebe: „Proč Git nemá čísílka?“ Všechno je to opět v tom rozdílu centralizovaný vs. distribuovaný. Takové erekční (přívlastek přesně vystihující věc; samo se zvedá a pomáhá ho zvednout čísílkářům) čísílko v distribuovaném prostředí nemůže fungovat. Proč? Každým naklonováním repozitáře člověk získá identickou kopii toho původního (neberu teď v potaz možnost specifikovat --depth v Gitu). Člověk si vesele commituje na svém písečku, občas se koukne, jestli v nějakém jiném repozitáři nepřibyly nové věci a kdyžtak je stáhne k sobě. Ale pozor! Člověk nemusí nové věci stahovat jenom z jednoho repozitáře. Můžete si přes LANku a stahovat změny od kolegy na sousedním počítači, současně si fetchnout změny z centrálního serveru v budově a na to si ještě přibalit ty z veřejného repozitáře, nebo dalšího vývojáře od protinožců.

Kde by se pak, čísílkoví fanatici, měla skladovat ona záhadná erekční modla? Erekční číslo je globální stav. A takový stav se musí někde globálně udržovat. A aby se mohl udržovat globálně potřebujeme nějakou autoritu, která ho bude udržovat. A taková autorita, aby takový stav vyl v golbálu jenom jeden musí samozřejmě taky být jenom jedna. A to jsme zpět u centralizovaného VCS!

Ale Mercurial to umí! A v dokumentaci se dočtete, že jedno čísílko v jednom repozitáři může označovat úplně jiný commit v jiném repozitáři. Mercurial je pěkná děvka a jenom předstírá, že to s čísílky umí. Nenechte se oblbnout. Čísílka v Mercurialu jsou jen pro tuhle konkrétní kopii repozitáře a nelze se na ně spoléhat.

vydáno 14. 8. 2009, 22:11:01

8 komentářů (8 nových)

Zařazeno mezi:

Sally – holka, co natrhne prdel i starému průzkumníkovi

Všechno začalo mou leností, když jsem kódoval jedno menu. Každá položka měla jiné pozadí a položek byl stále stejný počet, tak jsem jednoduše využil CSS selektoru +:

li { background-image: url('img/menu_1.png'); }
li+li { background-image: url('img/menu_2.png'); }
li+li+li { background-image: url('img/menu_3.png'); }

Ale ejhle, selektor + přeci nepodporuje Internet Explorer 6 (a když ta mrška ne a ne odejít do horoucích pekel, kam patří…). Jelikož se v poslední době rozmnožily různé emulace různých věcí, které některé prohlížeče neumí, napsané v Javascriptu, začal jsem pátrat, jestli někdo neudělal něco podobného pro pro styly a IE šestku.

Inu, nic jsem nenašel. Tak jsem se ještě radši zeptal na tom správném místě. A zdá se, že nikdo o ničem neví. V duchu, co si neuděláš sám, to nemáš, jsem se vrhl na implementaci. A musím říct, že jsem spokojen.

Trvalo to sice hodně času a nervů, ale nakonec jsem „poskládal“ potřebné části – použil CSS selektorový engine Sizzle, uloupil detekci prohlížeče z quirksmode.org, napsal primitivní CSS parser, přihodil nějaký ten XMLHttpRequest, pak ještě smyčku, co načtená pravidla aplikuje, a tadá – zrodila se Sally, dívenka, která dá starému průzkumníkovi co proto.

Chcete-li, aby vám též pomohla, podívejte se na již odkazovaný GitHub, nebo si rovnou naklonujte repozitář:

$ git clone git://github.com/jakubkulhan/sally.git

Použití je pak jednoduché:

<script type="text/javascript" src="sally.js"></script>

Nechcete-li, aby ostatní browsery zbytečně Sally načítaly, můžete přihodit nějaký podmíněný komentář.

Sally – holka, co natrhne prdel i starému průzkumníkovi

foto od GonerDoug

vydáno 2. 8. 2009, 17:36:57

žádný komentář

Zařazeno mezi:

Zkušenosti se Zend_Search_Lucene

Jak se praví v dokumentaci, Zend_Search_Lucene je obecný textový vyhledávací engine napsaný pouze v PHP5. Praktické využití pro většinu webů – fulltextové vyhledávání. Osobně jsem si zvykl spíš používat Google a jeho site:domain.tld. Ale mít vlastní fulltextové vyhledávání je lepší, jelikož Google mě nemusí zas tak rychle zaindexovat a uživatelé jsou na zvyklí.

Zend je celkem moloch, takže nedoporučuji stahovat celý archiv, ale namísto toho využít jen SVN repozitář a provést checkout pouze potřebných adresářů a souborů:

$ mkdir -p lib/Zend
$ svn checkout \
http://framework.zend.com/svn/framework/standard/trunk/library/Zend/Search \
lib/Zend/Search
$ svn cat \
http://framework.zend.com/svn/framework/standard/trunk/library/Zend/Exception.php \
> lib/Zend/Exception.php
$ find lib/ -name ".svn" | xargs rm -rf

Zend potřebuje, aby byla správně nastavena include_path. Je-li framework umístěn v podadresáři lib/, pak je potřeba include_path nastavit nějak takto:

set_include_path(dirname(__FILE__) . DIRECTORY_SEPARATOR . 'lib' .
    PATH_SEPARATOR . get_include_path());

Ještě než se člověk pustí do práce s indexem, je potřeba nastavit locale. Tohle mě docela potrápilo. Na localhostu všechno fungovalo, jak by mělo, ale na produkčním serveru se výsledky hledání nějak podivně omezily jen na pár věcí – jako by se nezaindexovalo posledních pár slov. Zkusil jsem vše přeindexovat asi 3krát, ale pořád to samé. Kdyby mě rovnou napadlo se podívat do chybového logu, mohl jsem serveru ušetřit hodně procesorového času. Nejdříve jsem si logu vůbec nevšímal, ale jak dosáhl velikosti někde kolem 3 MiB, přilákal tím tak trochu mou pozornost. Problém byl v jiném nastavení locale u mě doma a na produkčním serveru, takže iconv() skončilo s Notice o nepovoleném znaku, čímž se zpracovala jen část řetězce. Doma jsem měl nastaveno UTF-8, na produkčním je asi ISO-8859-2, takže setlocale():

setlocale('cs_CZ.UTF-8');

Fulltext jsem potřeboval pro jednu instanci Shopaholic. Nakonec jsem se rozhodl, že indexovat se budou akorát produkty – u e-shopu lidi stejně nic jiného nezajímá (alespoň doufám). (Jelikož jsem na této instanci provedl ještě nějaké úpravy, které by nebylo dobré zahrnout do hlavní větve, bude chvilku trvat, než se fulltext dostane do repozitáře na GitHubu.)

Celé indexování se Zend_Search_Lucene probíhá ve vytváření dokumentů a jejich ukládání do indexu. Každý dokument obsahuje různá pole, pomocí kterých se dá vyhledávat. Jedno pole je pro vyhledávání výchozí, a tak se při psaní dotazu nemusí uvádět jeho jméno.

Pole jsou různých typů a mají různé vlastnosti. Pro aplikace, kde slouží jako persistentní úložiště databáze, je podle mě nejlepší zvolit pro všechna pole typ UnStored – bylo by zbytečné data z databáze ještě replikovat v indexu. Jediné, co Shopaholic ukládá do indexu, je ID produktu, podle kterého se poté při vyhledávání podnikne dotaz na databázi a vyberou skutečná data.

Když se na to podíváme z toho pohledu, že data jsou v databázi, pak možnosti indexování jednotlivých polí ztrácí význam. Řekněme, že název produktu je ukládán do pole name výrobce do manufacturer a popis produktu do description. Jako výchozí se zvolí pole description. Ale teď chce zákazník vyhledat všechny produkty od výrobce foobar. Aby tak mohl učinit, musel by do vyhledávacího políčka zadat manufacturer:foobar. Ale kdo tohle udělá? Zákazník chce prostě zadat foobar a mít výrobky od společnosti foobar.

Takže všechny informace, které by mohl chtít zákazník hledat, je nakonec potřeba dát do jednoho pole a to nastavit jako výchozí. Zvažuji, jestli do hlavní větve ponechat i další pole (kvůli pokročilejším dotazům), nebo se jich úplně zbavit a nechat jen jedno jediné? Spíš zbavit, Shopaholic má směřovat k co největší jednoduchosti – easy yet powerful, a ne powerful yet easy (protože to stejně nikdy pak easy není).

Potom tu vyvstává problém, jak aktualizovat index, když se některý z produktů změní. Jsou dvě možnosti, každá má svá pro a proti:

  1. aktualizovat index hned při jakékoli změně produktu

  2. vyčlenit změny zvlášť

První možnost přidá, a to docela dost, na čase všech operací, takže práce s produkty je pomalejší. Ale zase zachovává index neustále aktuální a zákazník vždycky najde to, co je právě teď v databázi. U druhého řešení je to naopak – práce s produkty je plynulejší, ale zákazník nemusí vždy najít to, co vlastně chtěl, protože se to mezitím mohlo změnit. A taktéž přidává nutnost do rozhraní nějak tu volbu k aktualizaci fulltextu zapracovat. Vzhledem k importu nakonec vyhrála druhá možnost.

Jak ukládat informace o tom, že produkt změnil? Databázové schéma postrádá informace o tom, kdy byl produkt vložen, či upraven (jaké to špatné mé návrhové rozhodnutí!), takže tudy cesta nevede. I když teď mě napadá, že by se to dalo sledovat pomocí změn cen – při každém ukládání produktu je zároveň zapsána cena, s kterou je v ten okamžik ukládán. Proč mě to nenapadlo dříve?

Vyřešil jsem to tedy jinak – bitmapou (a teď myslím tu bitmapu, tu strukturu, ne obrázek) ukládanou do souboru. Kód na konci článku.

Zend_Search_Lucene mě potěšilo – jak svou jednoduchostí, tak rychlostí. Originál Lucene je asi rychlejší, ale na PHP to podle mě vůbec není špatné. Taky mě to utvrdilo v tom, že Zend má své dobré části – Zend_Search_Lucene, různá API –, ale celkově je to moloch a jako základ k psaní aplikací bych ho nepoužil.

function bitmap($filename)
{
    // get all true
    if (func_num_args() === 1) {
        if (($data = file_get_contents($filename)) === FALSE) return NULL;
        $bits = array();
        for ($i = 0, $len = strlen($data); $i < $len; ++$i) {
            $byte = ord($data{$i});
            for ($j = 0; $j < 8; $j++) 
                if ($byte & (1 << (7 - $j))) $bits[] = $i * 8 + $j;
        }

        return $bits;

    // get/set bit
    } else {
        $bit = intval(func_get_arg(1));
        $set = NULL;
        if (func_num_args() > 2) $set = func_get_arg(2);
            
        // open file
        if (!($handle = @fopen($filename, 'r+b'))) return NULL;
        if (!flock($handle, $set === NULL ? LOCK_SH : LOCK_EX)) {
            fclose($handle);
            return NULL;
        }

        // read byte with needed bit
        $offset = intval(floor($bit / 8));
        $byte_offset = 7 - ($bit % 8);
        if (fseek($handle, $offset, SEEK_SET) === -1) {
            fclose($handle); 
            return NULL;
        }
        $byte = ord(fread($handle, 1));

        // get
        if ($set === NULL) {
            fclose($handle);
            return (bool) ($byte & (1 << $byte_offset));
        }

        // set
        $byte = ($a = ($byte >> ($byte_offset + 1) << ($byte_offset + 1))) |
            $byte & ~($a + (1 << $byte_offset)) |
            intval((bool) $set) << $byte_offset;

        if (fseek($handle, $offset, SEEK_SET) === -1) {
            fclose($handle);
            return NULL;
        }

        if (fwrite($handle, chr($byte), 1) !== 1) {
            fclose($handle);
            return NULL;
        }

        fflush($handle);
        fclose($handle);
        return TRUE;
    }
}

vydáno 28. 7. 2009, 15:02:51

2 komentáře (2 nové)

Zařazeno mezi: