<p style="padding:0 0 0 0; margin:0 0 0 0;">Zdravím,</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> </p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">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 ;)</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> </p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">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.</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> </p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">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.</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> </p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">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.</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> </p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">KdyĹľ to shrnu:</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> </p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">- Nemístné šetĹ™ení prostorem vÄ›tšinou sníĹľí rychlost Ĺ™ešení.</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">- Nemístné plýtvání prostorem vÄ›tšinou dále nezvýší rychlost Ĺ™ešení.</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">- Neexistuje jediné nejlepší Ĺ™ešení pro všechny situace. VĹľdy je to kompromis.</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">- 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.</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> </p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">(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.)</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> </p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">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.</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> </p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">NechtÄ›l jsem napsat vyÄŤerpávající odpověď ;)</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> </p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">Mějte se fajn,</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> Petr</p>
<p style="padding:0 0 0 0; margin:0 0 0 0;"> </p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">______________________________________________________________<br />
> Od: "Lumír Balhar" <frenzy.madness@gmail.com><br />
> Komu: <python@py.cz><br />
> Datum: 15.06.2015 22:36<br />
> PĹ™edmÄ›t: [python] PaměťovÄ› nároÄŤné Ĺ™azení<br />
></p>
<p style="padding:0 0 0 0; margin:0 0 0 0;">Ahoj všem.<br />
<br />
Ĺ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í.<br />
<br />
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:<br />
<br />
0 ema ma maso<br />
1 ma ma masoe<br />
2 a ma masoem<br />
3 ma masoema<br />
4 ma masoema <br />
5 a masoema m<br />
6 masoema ma<br />
7 masoema ma <br />
8 asoema ma m<br />
9 soema ma ma<br />
10 oema ma mas<br />
<br />
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Ĺ.<br />
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.<br />
<br />
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.<br />
<br />
KonkrétnÄ›:<br />
<br />
class Buffer():<br />
def __init__(self, input):<br />
self.input = input<br />
self.indexes = [x for x in range(len(input))]<br />
<br />
def __getitem__(self, index):<br />
return self.input[index:] + self.input[0:index]<br />
<br />
def sort(self):<br />
self.indexes.sort(key=lambda x: self[x])<br />
<br />
<br />
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.<br />
<br />
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?<br />
<br />
PĹ™edem díky za nakopnutí tím správným smÄ›rem.<br />
Lumír<br />
_______________________________________________<br />
Python mailing list<br />
python@py.cz<br />
<a href="http://www.py.cz/mailman/listinfo/python">http://www.py.cz/mailman/listinfo/python</a><br />
<br />
Visit: <a href="http://www.py.cz">http://www.py.cz</a></p>