Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > cz.comp.lang.python > #3029

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

Show all headers | View raw

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

Back to cz.comp.lang.python | Next — Next in thread | Find similar

Thread

Paměťově náročné řazení Lumír Balhar <frenzy.madness@gmail.com> - 2015-06-15 13:36 -0700
  Re: Paměťově náročné řazení Pavel Schön <pavel@schon.cz> - 2015-06-16 11:34 -0700
  Re: Paměťově náročné řazení Lumír Balhar <frenzy.madness@gmail.com> - 2015-06-29 07:19 -0700

csiph-web