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

[Honza Král]

Ahoj,

ja bych to delal lazy, a tedy nikdy nevytvarel instance tech listu
(coz ty delas v __getitem__) a misto toho by proste byl kazdy radek
reprezentovany jen tim offsetem ale existovalo by jen jedno globalni
pole s tim vstupem:

# lze rovnez resit lazy, ale asi nestoji za to, pro pripadnou usporu
pameti u hodne velkych vstupu pouzij __slots__
self.lines = [Line(input, offset) for offset in range(len(input))]

kde Line ma naimplementovano __getitem__ (self.input[(self.offset +
key) % len(self.input)]) a hlavne __iter__

pak je jen potreba vymyslet sort, ale tady bych proste jen resilt
rucne lexikograficky sort - tedy napred pole prvniho pismene, pak
podle druheho atp - aby ses vyhnul materializovani kazde radky (coz
bude fungovat jelikoz sort je stable). Pripadne pomoci komparatoru
(https://docs.python.org/2/howto/sorting.html#the-old-way-using-the-cmp-parameter)
coz bude fungovat i na tech lazy objektech.

Je docela dobre mozne, ze pandas bude mit neco co se bude hodit na
problem lepe, ale o tom ja nic nevim
Honza Král
E-Mail: honza.kral na gmail.com
Phone:  +420 606 678585


2015-06-15 22:36 GMT+02:00 Lumír Balhar <frenzy.madness na gmail.com>:
> 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