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

Úterý Červen 16 11:03:14 CEST 2015

Ja nevim, skoly nemam, a nebudu se poustet do polemiky o lazy objektech, od
toho jsou tu jini.

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.

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, ...

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.

HTH

   Jirka

P.S. Takhle jsem kdysi tridil sitove rozsahy podle prvni IP adresy
(first_ip() prevadi IP adresy na cisla):

def first_ip(IPy_obj):
    '''returns IP of the network address of an IPy object as an integer,
    useful for sorting (see behaviour of "key" argument for sort())/
    It's needed as IPy objects are sorted by length by default.
    '''
    return IPy_obj.net().int()

def sort_networks(ip_list):
    nets = sorted(ip_list, key=first_ip)

2015-06-16 10:42 GMT+02:00 Petr Přikryl <prikryl at atlas.cz>:

> 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 at gmail.com>
> > Komu: <python at 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 at py.cz
> http://www.py.cz/mailman/listinfo/python
>
> Visit: http://www.py.cz
>
> _______________________________________________
> Python mailing list
> python at py.cz
> http://www.py.cz/mailman/listinfo/python
>
> Visit: http://www.py.cz
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.py.cz/pipermail/python/attachments/20150616/3ace5938/attachment.html>