<div dir="ltr"><div><div>Nebo pustit Hadoop...<br><br></div>Kam až jsme se to zase dostali :)<br><br></div>PM<br></div><div class="gmail_extra"><br><div class="gmail_quote">Dne 17. června 2015 12:51 Petr Viktorin <span dir="ltr"><<a href="mailto:encukou@gmail.com" target="_blank">encukou@gmail.com</a>></span> napsal(a):<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">2015-06-16 20:34 GMT+02:00 Pavel Schön <<a href="mailto:pavel@schon.cz">pavel@schon.cz</a>>:<br>
> <a href="https://en.wikipedia.org/wiki/External_sorting" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/External_sorting</a><br>
<br>
To je dobrá poznámka. Možná bude nejlepší to strčit do souboru a<br>
zavolat unixovou utilitku sort :)<br>
<div class="HOEnZb"><div class="h5"><br>
> Dne pondělí 15. června 2015 22:36:11 UTC+2 Lumír Balhar napsal(a):<br>
>> Ahoj všem.<br>
>><br>
>> Řeším s kamarádem jeden jeho projekt, jehož součástí je i Burrows-Wheelerova transformace, která se používá před kompresí dat společně s Move to Front transformací pro snížení entropie vstupních dat a tím zvýšení efektivity kompresního algoritmu, kterému tyto dvě transformace předcházejí.<br>
>><br>
>> Pochopení transformací není potřeba. U BWT se využívá tzv, buffer, který obsahuje všechny možné rotace vstupních dat, takže například pro "ema má maso" vypadá takto:<br>
>><br>
>>  0 ema ma maso<br>
>>  1 ma ma masoe<br>
>>  2 a ma masoem<br>
>>  3  ma masoema<br>
>>  4 ma masoema<br>
>>  5 a masoema m<br>
>>  6  masoema ma<br>
>>  7 masoema ma<br>
>>  8 asoema ma m<br>
>>  9 soema ma ma<br>
>> 10 oema ma mas<br>
>><br>
>> Pro malá data je to dobré, ale pro velká nelze mít celý buffer v paměti, protože se pro každý vstupní znak navíc rozšíří o řádek i sloupec zároveň.<br>
>> Napsal jsem tedy pro Buffer samostatnou třídu, kde pomocí __getitem__ vygeneruji potřebný řádek posunem až ve chvíli, kdy je jeho obsah potřeba.<br>
>><br>
>> Základní buffer jsem tím vyřešil a ušetřil hromadu paměti. Problém ale je, že v dalším kroku potřebuji tento buffer lexikograficky seřadit. Abych jej opět nemusel cpát do paměti, vytvořil jsem pole indexů, kde každý index reprezentuje jeden řádek bufferu a řadím jen toto pole (čímž získám přeskládané pořadí řádků původního bufferu), ale jako klíč používám právě obsah řádku pro daný index.<br>
>><br>
>> Konkrétně:<br>
>><br>
>> class Buffer():<br>
>>     def __init__(self, input):<br>
>>         self.input = input<br>
>>         self.indexes = [x for x in range(len(input))]<br>
>><br>
>>     def __getitem__(self, index):<br>
>>         return self.input[index:] + self.input[0:index]<br>
>><br>
>>     def sort(self):<br>
>>         self.indexes.sort(key=lambda x: self[x])<br>
>><br>
>><br>
>> A teď jsme se dostali k jádru problému. I když se obsah jednotlivých řádků generuje až ve chvíli, kdy jsou potřeba, a řadit by se mělo jen relativně malé pole indexů, při volání funkce .sort() se jakoby stejně celé to pole nejdříve vytvoří v paměti, seřadí a pak se seřadí to cílové pole s indexy na základě obsahu bufferu.<br>
>><br>
>> Existuje způsob, jak implementovat takovýto řadící algoritmus pro velký objem dat, aniž bych je měl v jednu chvíli všechny v paměti?<br>
>><br>
>> Předem díky za nakopnutí tím správným směrem.<br>
>> Lumír<br>
><br>
> _______________________________________________<br>
> Python mailing list<br>
> <a href="mailto:python@py.cz">python@py.cz</a><br>
> <a href="http://www.py.cz/mailman/listinfo/python" rel="noreferrer" target="_blank">http://www.py.cz/mailman/listinfo/python</a><br>
><br>
> Visit: <a href="http://www.py.cz" rel="noreferrer" target="_blank">http://www.py.cz</a><br>
_______________________________________________<br>
Python mailing list<br>
<a href="mailto:python@py.cz">python@py.cz</a><br>
<a href="http://www.py.cz/mailman/listinfo/python" rel="noreferrer" target="_blank">http://www.py.cz/mailman/listinfo/python</a><br>
<br>
Visit: <a href="http://www.py.cz" rel="noreferrer" target="_blank">http://www.py.cz</a><br>
</div></div></blockquote></div><br></div>