Nebo pustit Hadoop... Kam až jsme se to zase dostali :)
PM Dne 17. června 2015 12:51 Petr Viktorin <encu...@gmail.com> napsal(a): > 2015-06-16 20:34 GMT+02:00 Pavel Schön <pa...@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@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 >
_______________________________________________ Python mailing list python@py.cz http://www.py.cz/mailman/listinfo/python Visit: http://www.py.cz