<div dir="ltr">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.<div><br></div><div><div><font face="monospace, monospace"> def better_sort(self):</font></div><div><font face="monospace, monospace"> self.indexes.sort(cmp=self._sort_cmp)<br></font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace"> def _sort_cmp(self, a, b):</font></div><div><font face="monospace, monospace"> a_value = self[a]</font></div><div><font face="monospace, monospace"> b_value = self[b]</font></div></div><div><font face="monospace, monospace"> return cmp(a_value, b_value)</font></div><div><br></div><div>Jenže v Pythonu 3 už takhle jednoduše komparátor použít nekde (<font face="monospace, monospace">sort</font> prostě ani nemá parametr <font face="monospace, monospace">cmp</font>), ale dá se to obejít takto:</div><div><br></div><div><div><font face="monospace, monospace"> def better_sort(self):</font></div><div><font face="monospace, monospace"> from functools import cmp_to_key</font></div><div><font face="monospace, monospace"> self.indexes.sort(key=cmp_to_key(self._sort_cmp))</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace"> def _sort_cmp(self, a, b):</font></div><div><font face="monospace, monospace"> a_value = self[a]</font></div><div><font face="monospace, monospace"> b_value = self[b]</font></div><div><font face="monospace, monospace"> if a_value < b_value:</font></div><div><font face="monospace, monospace"> return -1</font></div><div><font face="monospace, monospace"> if a_value > b_value:</font></div><div><font face="monospace, monospace"> return 1</font></div><div><font face="monospace, monospace"> return 0</font></div></div><div><br></div><div class="gmail_extra">PM</div><div class="gmail_extra"><br><div class="gmail_quote">Dne 15. června 2015 22:36 Lumír Balhar <span dir="ltr"><<a href="mailto:frenzy.madness@gmail.com" target="_blank">frenzy.madness@gmail.com</a>></span> napsal(a):<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Ahoj všem.<br>
<br>
Ř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í.<br>
<br>
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:<br>
<br>
0 ema ma maso<br>
1 ma ma masoe<br>
2 a ma masoem<br>
3 ma masoema<br>
4 ma masoema<br>
5 a masoema m<br>
6 masoema ma<br>
7 masoema ma<br>
8 asoema ma m<br>
9 soema ma ma<br>
10 oema ma mas<br>
<br>
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ň.<br>
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.<br>
<br>
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.<br>
<br>
Konkrétně:<br>
<br>
class Buffer():<br>
def __init__(self, input):<br>
self.input = input<br>
self.indexes = [x for x in range(len(input))]<br>
<br>
def __getitem__(self, index):<br>
return self.input[index:] + self.input[0:index]<br>
<br>
def sort(self):<br>
self.indexes.sort(key=lambda x: self[x])<br>
<br>
<br>
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.<br>
<br>
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?<br>
<br>
Předem díky za nakopnutí tím správným směrem.<br>
Lumír<br>
_______________________________________________<br>
Python mailing list<br>
<a href="mailto:python@py.cz">python@py.cz</a><br>
<a href="http://www.py.cz/mailman/listinfo/python" rel="noreferrer" target="_blank">http://www.py.cz/mailman/listinfo/python</a><br>
<br>
Visit: <a href="http://www.py.cz" rel="noreferrer" target="_blank">http://www.py.cz</a><br>
</blockquote></div><br></div></div>