Vypadá to, že si sort hodnoty vrácené z key funkce ukládá. To se dá obejít tak, že si sám naimplementuješ komparátor, který bude řetězce vytvářet až podle potřeby.
def better_sort(self): self.indexes.sort(cmp=self._sort_cmp) def _sort_cmp(self, a, b): a_value = self[a] b_value = self[b] return cmp(a_value, b_value) Jenže v Pythonu 3 už takhle jednoduše komparátor použít nekde (sort prostě ani nemá parametr cmp), ale dá se to obejít takto: def better_sort(self): from functools import cmp_to_key self.indexes.sort(key=cmp_to_key(self._sort_cmp)) def _sort_cmp(self, a, b): a_value = self[a] b_value = self[b] if a_value < b_value: return -1 if a_value > b_value: return 1 return 0 PM Dne 15. června 2015 22:36 Lumír Balhar <frenzy.madn...@gmail.com> 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