<div dir="ltr"><div><div>Ja nevim, skoly nemam, a nebudu se poustet do polemiky o lazy objektech, od toho jsou tu jini.<br><br></div>Jenom nahodim jednu vec. Kdysi jsem resil neco podobneho, ale misto sort() jsem pouzil sorted() a parametr "key". Ten umoznuje ohodnotit kazdou polozku nejakou hodnotou a potom setridit podle techto hodnot. <br><br></div><div>Ty jsi schopny z puvotniho radku a offsetu spocitat nejake cislo. Napr. pro "ema ma maso" spocitas "ord('e') * 10^100 + ord('m') * 10^90 + ord('a') * 10^80 + ord(' ') * 10 * 70, ...<br><br></div><div>Proste z toho stringu odvodis nejakou hodnotu, ktera umozni razeni. A sorted() ti podle ni ochodne seradi, pro kazdou polozku se ta hodnota "key" bude pocitat jenom jednou (narozdil od "cmp"). Pokud ty polozky budou lazy, jak uz psali ostatni, mas myslim problem vyreseny.<br><br></div><div>HTH<br><br></div><div>   Jirka<br><br></div><div>P.S. Takhle jsem kdysi tridil sitove rozsahy podle prvni IP adresy (first_ip() prevadi IP adresy na cisla):<br><br>def first_ip(IPy_obj):<br>    '''returns IP of the network address of an IPy object as an integer,<br>    useful for sorting (see behaviour of "key" argument for sort())/<br>    It's needed as IPy objects are sorted by length by default.<br>    '''<br>    return IPy_obj.net().int()<br><br>def sort_networks(ip_list):<br>    nets = sorted(ip_list, key=first_ip)<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-06-16 10:42 GMT+02:00 Petr PĹ™ikryl <span dir="ltr"><<a href="mailto:prikryl@atlas.cz" target="_blank">prikryl@atlas.cz</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><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" <<a href="mailto:frenzy.madness@gmail.com" target="_blank">frenzy.madness@gmail.com</a>><br>
> Komu: <<a href="mailto:python@py.cz" target="_blank">python@py.cz</a>><br>
> Datum: 15.06.2015 22:36<br>
> PĹ™edmÄ›t: [python] PaměťovÄ› nároÄŤnĂ© Ĺ™azenĂ­<br>
></p><div class="HOEnZb"><div class="h5">

<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>
<a href="mailto:python@py.cz" target="_blank">python@py.cz</a><br>
<a href="http://www.py.cz/mailman/listinfo/python" target="_blank">http://www.py.cz/mailman/listinfo/python</a><br>
<br>
Visit: <a href="http://www.py.cz" target="_blank">http://www.py.cz</a></p>

</div></div><br>_______________________________________________<br>
Python mailing list<br>
<a href="mailto:python@py.cz">python@py.cz</a><br>
<a href="http://www.py.cz/mailman/listinfo/python" rel="noreferrer" target="_blank">http://www.py.cz/mailman/listinfo/python</a><br>
<br>
Visit: <a href="http://www.py.cz" rel="noreferrer" target="_blank">http://www.py.cz</a><br></blockquote></div><br></div>