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.k...@gmail.com Phone: +420 606 678585 2015-06-15 22:36 GMT+02:00 Lumír Balhar <frenzy.madn...@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@py.cz > http://www.py.cz/mailman/listinfo/python > > Visit: http://www.py.cz _______________________________________________ Python mailing list python@py.cz http://www.py.cz/mailman/listinfo/python Visit: http://www.py.cz
