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

[Petr Messner]

Nebo pustit Hadoop...

Kam až jsme se to zase dostali :)

PM

Dne 17. června 2015 12:51 Petr Viktorin <encukou na gmail.com> napsal(a):

> 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
> _______________________________________________
> Python mailing list
> python na py.cz
> http://www.py.cz/mailman/listinfo/python
>
> Visit: http://www.py.cz
>
------------- další část ---------------
HTML příloha byla odstraněna...
URL: <http://www.py.cz/pipermail/python/attachments/20150617/5684d785/attachment.html>