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

[Petr Viktorin]

2015-06-15 22:36 GMT+02:00 Lumír Balhar :
> 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.


Ahoj,
sort() používá jen operátor "<", takže stačí naimplementovat ten (i
když s functools.total_ordering [0] není problém naimplementovat ty
ostatní).
Jen je potřeba mít objekt pro každý řádek. Když takový objekt obsahuje
jen odkaz na původní řetězec, a číslo řádku, tak se ti snad všechny do
paměti vejdou.
Přikládám nástin toho, jak bych to řešil já (v py3).
(Jestli se vyplatí při porovnávání generovat oba řádky a porovnat ty,
nebo jako já porovnávat jednotlivé znaky v Pythonu, záleží na tom jak
často ty řetězce mají dlouhé shodné prefixy.)

[0] https://docs.python.org/3/library/functools.html#functools.total_ordering

class RotatedString:
__slots__ = ['orig_string', 'n']

def __init__(self, orig_string, n):
self.orig_string = orig_string
self.n = n

def __len__(self):
return len(self.orig_string)

def __str__(self):
return self.orig_string[self.n:] + self.orig_string[:self.n]

def __iter__(self):
yield from self.orig_string[self.n:]
yield from self.orig_string[:self.n]

def __getitem__(self, i):
return self.orig_string[(self.n + i) % len(self.orig_string)]

def __lt__(self, other):
if self.orig_string != other.orig_string:
return self.orig_string < other.orig_string
for c1, c2 in zip(self, other):
if c1 != c2:
return c1 < c2


base = 'ema má maso'

for rs in sorted([RotatedString(base, i) for i, c in enumerate(base)]):
print(rs)
___
Python mailing list
python@py.cz
http://www.py.cz/mailman/listinfo/python

Visit: http://www.py.cz

Re: [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" 
Komu: 
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 


Visit: http://www.py.cz 

___
Python mailing list
python@py.cz
http://www.py.cz/mailman/listinfo/python

Visit: http://www.py.cz

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

[Jirka Vejrazka]

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 :

> 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" 
> > Komu: 
> > 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

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

[Petr Messner]

Dne 16. června 2015 11:03 Jirka Vejrazka 
napsal(a):

>
> 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").
>

No a to je právě ten problém - sort zavolá key jenom jednou a výsledek si
zapamatuje, jenže je toho tolik, že to zabere spoustu paměti. Proto je tady
ten cmp styl lepší, nebo ty objekty, co to vypočívávají "lazy".

PM
___
Python mailing list
python@py.cz
http://www.py.cz/mailman/listinfo/python

Visit: http://www.py.cz

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

[Jirka Vejrazka]

>
> 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").
>

> No a to je právě ten problém - sort zavolá key jenom jednou a výsledek si
zapamatuje, jenže je toho tolik, že to zabere > spoustu paměti. Proto je
tady ten cmp styl lepší, nebo ty objekty, co to vypočívávají "lazy".

To ja beru, ale pro kazdy vstupni radek si zapamatuje jen jedno cislo (i
kdyz velke). Pokud by i tohle byl problem, tak uz zbyva snad jenom nejaka
forma externiho trideni na disku.

   Jirka

2015-06-16 11:10 GMT+02:00 Petr Messner :

> Dne 16. června 2015 11:03 Jirka Vejrazka 
> napsal(a):
>
>>
>> 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").
>>
>
> No a to je právě ten problém - sort zavolá key jenom jednou a výsledek si
> zapamatuje, jenže je toho tolik, že to zabere spoustu paměti. Proto je tady
> ten cmp styl lepší, nebo ty objekty, co to vypočívávají "lazy".
>
> PM
>
>
> ___
> Python mailing list
> python@py.cz
> http://www.py.cz/mailman/listinfo/python
>
> Visit: http://www.py.cz
>
___
Python mailing list
python@py.cz
http://www.py.cz/mailman/listinfo/python

Visit: http://www.py.cz

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

[Hynek Fabian]

Ja bych na to sel jinak:

class Rotator(object):
  def __init__(self, input):
self.data = input + input
self.size = len(input)
self.indices = range(self.size)[:]
self.indices.sort(key=lambda x: self[x])

  def __getitem__(self, index):
return buffer(self.data, index, self.size)

Buffer objekty jsou vicemene jen pointery takze se nemusis moc starat
kolik jich zije a sort() jim zda se rozumi (experimentalne vyzkouseno).

On 06/15/2015 10:36 PM, Lumír Balhar wrote:
> 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
> 
> Visit: http://www.py.cz
> 
___
Python mailing list
python@py.cz
http://www.py.cz/mailman/listinfo/python

Visit: http://www.py.cz