[python] Paměťově náročné řazení

[Petr Messner]

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.madness na 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 na py.cz
> http://www.py.cz/mailman/listinfo/python
>
> Visit: http://www.py.cz
>
------------- další část ---------------
HTML příloha byla odstraněna...
URL: <http://www.py.cz/pipermail/python/attachments/20150615/61d78553/attachment.html>