Ja bych na to sel jinak:
class Rotator(object):
def __init__(self, input):
self.data = input + input
self.size = len(input)
self.indices = range(self.size)[:]
self.indices.sort(key=lambda x: self[x])
def __getitem__(self, index):
return buffer(self.data, index, self.size)
Buffer objekty jsou vicemene jen pointery takze se nemusis moc starat
kolik jich zije a sort() jim zda se rozumi (experimentalne vyzkouseno).
On 06/15/2015 10:36 PM, Lumír Balhar wrote:
> 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
> [email protected]
> http://www.py.cz/mailman/listinfo/python
>
> Visit: http://www.py.cz
>
_______________________________________________
Python mailing list
[email protected]
http://www.py.cz/mailman/listinfo/python
Visit: http://www.py.cz
