[python] Paměťově náročné řazení

[Petr Viktorin]

2015-06-16 20:34 GMT+02:00 Pavel Schön <pavel na schon.cz>:
> https://en.wikipedia.org/wiki/External_sorting

To je dobrá poznámka. Možná bude nejlepší to strčit do souboru a
zavolat unixovou utilitku sort :)

> Dne pondělí 15. června 2015 22:36:11 UTC+2 Lumír Balhar napsal(a):
>> Ahoj všem.
>>
>> Ř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í.
>>
>> 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:
>>
>>  0 ema ma maso
>>  1 ma ma masoe
>>  2 a ma masoem
>>  3  ma masoema
>>  4 ma masoema
>>  5 a masoema m
>>  6  masoema ma
>>  7 masoema ma
>>  8 asoema ma m
>>  9 soema ma ma
>> 10 oema ma mas
>>
>> 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ň.
>> 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.
>>
>> 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.
>>
>> Konkrétně:
>>
>> class Buffer():
>>     def __init__(self, input):
>>         self.input = input
>>         self.indexes = [x for x in range(len(input))]
>>
>>     def __getitem__(self, index):
>>         return self.input[index:] + self.input[0:index]
>>
>>     def sort(self):
>>         self.indexes.sort(key=lambda x: self[x])
>>
>>
>> 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.
>>
>> 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?
>>
>> Předem díky za nakopnutí tím správným směrem.
>> Lumír
>
> _______________________________________________
> Python mailing list
> python na py.cz
> http://www.py.cz/mailman/listinfo/python
>
> Visit: http://www.py.cz