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

[Petr Viktorin]

2015-06-15 22:36 GMT+02:00 Lumír Balhar <frenzy.madness na gmail.com>:
> 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.


Ahoj,
sort() používá jen operátor "<", takže stačí naimplementovat ten (i
když s functools.total_ordering [0] není problém naimplementovat ty
ostatní).
Jen je potřeba mít objekt pro každý řádek. Když takový objekt obsahuje
jen odkaz na původní řetězec, a číslo řádku, tak se ti snad všechny do
paměti vejdou.
Přikládám nástin toho, jak bych to řešil já (v py3).
(Jestli se vyplatí při porovnávání generovat oba řádky a porovnat ty,
nebo jako já porovnávat jednotlivé znaky v Pythonu, záleží na tom jak
často ty řetězce mají dlouhé shodné prefixy.)

[0] https://docs.python.org/3/library/functools.html#functools.total_ordering
------------- další část ---------------
A non-text attachment was scrubbed...
Name: rad.py
Type: text/x-python
Size: 871 bytes
Desc: [žádný popis není k dispozici]
URL: <http://www.py.cz/pipermail/python/attachments/20150616/ac5e5f0c/attachment.py>