Předpověď počasí pro Android 4

26.6.2014 12:04 | Přečteno: 1871× | Programování

Už je to nějaký ten pátek, co jsem napsal nějaký blog, tak jsem se při příležitosti vydání Počasí v krajích 2.0 rc2 rozhodl napsat blog shrnující novinky, co se od posledního zápisu udály.

Změny viditelné pro uživatele

• podpora více zařízení – v podstatě šlo jen o explicitní vyjádření, že není potřeba touchscreen. V praxi to znamená, že z 6389 (v době psaní zápisku) zařízení na kterých je podporován Google Play předpověď počasí nebude fungovat na čtyřech z nich.
• ikony nejsou experimentální, což znamená, že jsou zapnuté už po instalaci a při změně nastavení už není třeba potvrzovat dialog, že jsou experimentální (protože nejsou).
• odstranění otravného progress dialogu při stahování předpovědi - dříve se při stahování předpovědi zobrazil nezrušitelný dialog informující o stahování předpovědi. Což znamenalo, že když se člověk uklepnul, tak musel počkat až se předpověď stáhne než mohl změnit kraj. To bylo dáno tím, že původně šlo stahovat jen jednu předpověď, ale už během jedné z prvních verzí byla přidána podpora stahování na pozadí (když byla předpověď dostatečně nová, aplikace zkoušela novou předpověď stahovat potichu na pozadí bez informačního dialogu), takže nějakou dobu bylo limitem čistě GUI. Dialog byl nahrazen méně rušivým stavovým řádkem.
• mazání starých předpovědí – předpovědi na minulé dny se automaticky mažou. Konečně není třeba přemýšlet nad tím, co je vlastně za den, protože první v seznamu je vždy aktuální den. Z mého pohledu tohle a odstranění progress dialogu přidávají na uživatelské přívětivosti nejvíce.

Změny pod kapotou

A teď k hlavní části zápisku a tomu, co se změnilo pod kapotou. Tím je kompletní předělání parseru zpracovávajícího text předpovědi za účelem generování ikonky počasí. Je to sice jediná změna, ale ono toho tahle aplikace jinak moc nedělá . Nejprve začnu tím, jak to bylo uděláno předtím (ve zkratce: hloupě) a pak popíšu, jak je to uděláno teď s využitím jedné pěkné datové struktury.

Staré řešení

Tady není moc co rozebírat. Původní řešení nejprve vzalo String s předpovědí a pomocí split() ho rozdělilo podle mezer. Výsledné pole se poté procházelo a každý prvek (tj. slovo) byl testován vůči všem možným klíčovým slovým pomocí contains() nebo matches() (podle potřeby). Tohle sebou neslo několik problémů. Z praktického hlediska bylo největším problémem to, že parser zpracovával vždy jen jedno slovo a řešení spojení jako „skoro jasno“ vyžadovalo zavedení flagů, které informovaly o předchozím slově). Dalším problémem byla samozřejmě neefektivita zpracování. A to nejen z hlediska výpočetní náročnosti, ale také z hlediska paměti. Od jisté doby totiž Java pro podřetězce alokuje novou paměť (předtím se jen ukládal index začátku a konce). Nevím, jestli tomu tak je v Androidu, protože jsem nestudoval příslušné zdrojáky, ale vzhledem k tomu, že došlo ke znatelnému snížení spotřeby paměti, tak hádám, že dělá to samé co nová Java.

Nové řešení

Oproti tomu nové řešení je strašně super. Celé je postavené na upravené datové struktuře Trie přidávající hashování. O tom, jak funguje trie psát nebudu, kdo to neví, ať to přečte. Standardní trii jsem se ale rozhodl trošičku optimalizovat, a to použitím hash tabulky pro první rozdílné písmeno za prefixem. V praxi rozdíl nebude, protože se zpracovává málo dat, ale chtěl jsem si to vyzkoušet . Hlavně pokud by to mělo k něčemu být při zpracování většího množství dat, tak by se hash tabulka musela používat pro větší část prefixu (třeba tři písmena), protože projít abecedu je mžik. Každopádně už to tak je a funguje to.

Pro lepší ilustraci obrázek, co vznikne vložením „sníh“, „skoro jasno“, „skoro zataženo“, „déšť“ a „přeháňky“ do této datové struktury. První je na řadě hash tabulka pro počáteční písmena prefixů „s“, „d“, „p“. Protože déšť a přeháňky nemají společný prefix, jsou uloženy (kromě prvního písmena) do samostatných uzlů do kterých ukazuje záznam pro „d“, resp. „p“ z hash tabulky. Zajímavé jsou ale „skoro jasno“ a „skoro zataženo“. Protože se liší prvním písmenem za „skoro “, tak se vytvoří nová hash tabulka, která ukazuje na další část slova.

Co se týče použití v praxi, tak došlo k následujícím změnám – veškerý starý kód parseru jsem vyhodil, a:

1. Během statické inicializace se trie naplní daty, přičemž každý list stromu ukládá referenci na objekt, který zapracovává jemu odpovídající klíčové slovo.
2. Místo vytváření podřetězců se ukládá jen aktuální pozice v textu předpovědi.
3. Program se vždy pokusí z textu na dané pozici získat klíčové slovo. Pokud něco takového v trie je, trie vrátí objekt pro zpracování slova. Pak už se jen posune ukazatel na další slovo.

Díky těmto změnám je teď snadné podporovat víceslovná spojení a navíc došlo k výraznému zrychlení. IIRC parser zabral ca dvě třetiny času zpracování předpovědi, teď to je tuším někde kolem 2%.

Odkazy

Počasí v krajích na Google Play
Stažení pro lidi, co neradi Google Play        

Obrázky

Komentáře

[Jacob]

Super, něco takového jsem zrovna hledal, tohle budu používat. A velice oceňuji, že je možné stáhnout i samotné apk. Díky.

[kotrcka]

no, uz je to snad pomaly rok.. niekedy v lete 2013 som si to dal na tabletik..

stale dobra praca, palec hore.

[DW]

Šlo by to přidat i na F-Droid prosím?

[Rezza]

A na BBW. Uz tomu delam reklamu v kanalu :).

[mich]

Co je BBW prosím? Google hází jen samé porno...

[chrono]

BlackBerry App World

[Rezza]

BlackBerry World. A od 10.3 bude stacit i Amazon AppStore.

[stativ]

Jak tak na to koukám, tak je evidentně potřeba aplikaci „přebalit“. Zítra na to mrknu a uvidím, kolik by to dalo práce. Odkazují na plugin do Android Studia, které sice používám, ale nedělám v něm release buildy, protože to nějakou dobu nešlo a i předtím se muselo proklikávat otravným GUI. Teď to mám hezky naskriptováno, takže se mi APK sestaví, podepíše, vygeneruje mapovací soubor pro proguard a to všechno hezky nakopíruje do WebDAV adresáře s verzí, odkud to pak před vydáním stahuji do mobilu na testování.

[Rezza]

Jsou na to i CLI tooly, je to celkem jednoduche, muzu pomoct pripadne. Vcetne testovani (ala APK bez prebaleni jede perfektne).

[Rezza]

Nebo je to open source a muzu to udelat ja a delat ti distributora bez opruzu dalsich klicu, registrace atd. a jeste to pokazde zkusit na realnem HW.

[stativ]

Tomu se samozřejmě nebráním. Naopak pomoc od někoho, kdo tomu rozumí a má možnost to otestovat na realném HW jedině uvítám. Zdrojáky jsou pod GPL v3.

Pokud by ses na to vrhl, tak pokud je to možné, bylo by lepší používat verzi pro API12 a vyšší (je v branchi default, tagy jsou příslušně označené jako -API12). Na rozdíl od verze pro API 7 je totiž líp testovaná a neobsahuje různé obezličky. Kdyžtak během dneška přidám návod, jak na kompilaci.

[Rezza]

Ono ani neni potreba nic moc prekladat, staci to APK. API12 je samozrejmost. Jen jsem si to nedavno u sebe nedavno rozbil cele :(.

[stativ]

Tak to je super. Každopádně návod na kompilaci jsem do repozitáře přidal, může se hodit.

[Rezza]

Dobros, poslal jsem to na review, uvidime. Jeste jsem tam nikdy nic z Androidu nedaval. Uz me to stihli i vratiti kvuli popisu :).

[Josef Kufner]

Tak tam ještě přidej skript na update f-droid repositáře a dej URL k němu. Je to jen o vygenerování nějakého indexu.

[stativ]

No, asi bych to už opravdu měl udělat, protože je to už několikátý dotaz. Dokonce jsem zjistil, že už jsem tam registrovaný. Už dřív jsem pokukoval po tom, že bych balíček vytvořil, ale scházelo mi nějaké pěkné how-to. Evidentně ale stačí jen zažádat o zařazení do F-droidu na fóru, takže to udělám hned.

[stativ]

Tak jsem to zadal na fóru. Uvidíme, jestli, a případně kdy, to přidají.

[Myriam]

Diky!

[stativ]

Dobrá zpráva, už by to mělo v f-droidu být.

[Filip Jirsák]

Jaký význam má přidání toho hashe do trie? Pro vyhledávání textových řetězců je trie velmi efektivní struktura, zvlášť když ji (jako ve vašem případě) jednou postavíte a pak už jen čtete. Na první pohled mi připadá, že jste tím přidáním hashe dost zkomplikoval kód a výrazně zneefektivnil vyhledávání, ale třeba mi něco uniká a měl bych se na to podívat lépe...

[stativ]

V tomhle případě byl význam si vyzkoušet, jestli to jde.

Teď k mojí teorii, která tedy má smysl až když se udělá hash na delší část textu. Předpokládám, že hashováním na několika písmenech se hledání rychle posune do nižší úrovně bez nutnosti přímo porovnávat různé prefixy. Důsledkem by vlastně bylo i snížení hloubky stromu. Př.: když by se vkládalo „něco“, „někdo“ a „foo“ a hash se dělal ze tří písmen, tak by si člověk odpustil porovnávání s „ně“ a s „foo“ ale v tomhle případě by se rovnou skočilo na výsledek. Podle mého názoru (nemám to nijak matematicky podložené*) by to tedy mělo výhodu v podstatě O(1) vyhledávání jako v hash tabulce, ale s tím, že by bylo menší množství kolizí při potřebě několika krátkých tabulek.

Tady asi čtenáře napadne, proč jsem vlastně nepoužil rovnou hash tabulku. Důvod je takový, že by musela být poměrně rozsáhlá aby zachytila všechny možné tvary slov. Tak, jak to mám implementováno teď, se do trie často vkládá jen část slova (třeba „sněh“) přičemž se vrací výsledek už když ten začátek pasuje (tedy pokud nepasuje nějaký delší prefix), tj. postihne to slova jako „sněhem“, „sněhové“ atd. což už by se s hash tabulkou dělalo asi docela špatně.

PS: nevykat

* píšu si do TODO, protože by mě to samotného zajímalo

[Filip Jirsák]

V tomhle případě nemá smysl porovnávat třídy složitosti, protože vstupy jsou tak malé, že nesrovnatelně větší vliv má to, jaké konkrétní operace se se vstupem dělají. Už jenom to, že musíte vytvořit nový objekt s prefixem, spočítat jeho hash, a to, že hashovací tabulka bude v paměti mnohem větší, než trie, by mělo být varováním, že ta implementace s hashem bude pravděpodobně mnohem méně efektivní. Dokonce bych si tipnul, že u takhle malého množství slov bude rozhodující, kolikrát se budou muset do procesorové cache tahat data z hlavní paměti, a že to trie díky své kompaktnosti vyhraje s velkým náskokem.

[stativ]

Však jsem na to upozorňoval už v blogu, že při tomhle použití to vlastně poznat nebude. Ale chtěl jsem si zkusit, jestli to vůbec může fungovat (což funguje). Měnit to moc smysl nemá, času z běhu aplikace to zabere minimum (jednou při stažení, a i při tom většinu času aplikace stráví samotným stahováním a vykreslováním textu, přístup do trie zabere jednotky procent).

[stativ]

Tak jsem ze zvědavosti zkusil porovnat verzi s hashem a bez hashe a výsledek je překvapivý i pro mě. I použití hashování pro jeden znak výrazně urychlilo vyhledávání. Konkrétně to bylo o 10% při měření v emulátoru pro x86 a až o 40% na Huawei Y300.

[backinabag]

Nestacilo by u stareho reseni hledat jednotliva slova v celem textu predpovedi, bez deleni na slova? Jedno contains() odhaduju tak na 0.01ms.

[stativ]

Ono to závisí mimo jiné na pořadí, rozdělení na věty a tak. Navíc samotné contains() nemůže být efektivnější než současné řešení (viz zdrojáky Javy) a není to taková sranda.