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
