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

[Petr Přikryl]

Zdravím,
 
Doporučil bych ještě jeden úhel pohledu -- před rozhodnutím o způsobu implementaci. Neznám detaily řešeného problému, takže spíš obecně. Já vím, že je to jasné, ale někdy si neškodí zopaovat zásady ;)
 
U každého řešeného problému lze analyzovat složitost -- časovou a paměťovou. Nejdříve je nutné rozhodnout, jaká z nich je u řešeného problému důležitější, případně jestli někde existují limity (velikost pamět, počet procesorů, praktická doba řešení). Nakonec se to vždy plácne jen tak (pokud je to malý problém a nemá cenu se tím zabývat), nebo se hledá kompromis -- optimalizuje se. Ale před optimalizací je nutné zvolit správný přístup.
 
Mnohé implementační počiny vycházejí z naivního přístupu, který se pak těžko převrací do něčeho použitelného. Buď se každá část navrhne správně už od začátku, nebo se to musí dát snadno přepsat. Pokud něco z toho není splněno, jde to do kopru.
 
Mnohá řešení tratí na tom, že se od začátku upneme na nějaký konkrétní způsob řešení (konkrétní způsob implementace). Často používáme "Nic mi neříkejte, já na to přijdu sám!" místo toho, abychom použili prozkoumané (i když nám zatím neznámé) techniky.
 
Když to shrnu:
 
- Nemístné šetření prostorem většinou sníží rychlost řešení.
- Nemístné plýtvání prostorem většinou dále nezvýší rychlost řešení.
- Neexistuje jediné nejlepší řešení pro všechny situace. Vždy je to kompromis.
- Mohou existovat rozpoznatelné situace, kdy je výhodnější jedno z více známých řešení. Celkové řešení může být například zdvojené s tím, že se to lepší vybírá dynamicky.
 
(Vezměte si například "hloupý" SQL serve s SQL dotazovacím jazykem. Tam se napřelo už tolik úsilí, že stěží sami přijdete na něco lepšího při optimalizaci dotazu.)
 
Pokud je nutné řadit, pak nejlepší sekvenční algoritmus má teoretickou časovou složitost O(n log n). Tolikrát se budou muset transformovat data, pokud nebudou uložena. Příprava před řazením může věci urychlit.
 
Nechtěl jsem napsat vyčerpávající odpověď ;)
 
Mějte se fajn,
    Petr
 
______________________________________________________________
> Od: "Lumír Balhar" <frenzy.madness na gmail.com>
> Komu: <python na py.cz>
> Datum: 15.06.2015 22:36
> Předmět: [python] Paměťově náročné řazení
>
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 <http://www.py.cz/mailman/listinfo/python>

Visit: http://www.py.cz <http://www.py.cz>

------------- další část ---------------
HTML příloha byla odstraněna...
URL: <http://www.py.cz/pipermail/python/attachments/20150616/3249f742/attachment.html>