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.madn...@gmail.com>
Komu: <python@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@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>
_______________________________________________
Python mailing list
python@py.cz
http://www.py.cz/mailman/listinfo/python
Visit: http://www.py.cz
