1

ハードディスクに保存されている約 12*10^6 行のテキスト ファイルを使用しています。ファイルの構造は次のとおりです。

data|data|data|...|data\n
data|data|data|...|data\n
data|data|data|...|data\n
...
data|data|data|...|data\n

ヘッダーはなく、行を一意に識別する ID もありません。

機械学習の目的で使用したいので、確率学習に影響を与える可能性のあるテキスト ファイルに順序がないことを確認する必要があります。

通常、私はそのような種類のファイルをメモリにアップロードし、それらをシャッフルしてからディスクに再書き込みします。残念ながら、今回はファイルのサイズが原因で不可能なので、ディスク上で直接シャッフルを管理する必要があります (ディスク容量に問題はないと仮定します)。Pythonでそのようなタスクを効果的に（つまり、ディスクへの書き込みなど）効果的に管理する方法についてのアイデアはありますか?

4

4 に答える 4

6

これらのアイデアは 1 つを除いてすべて O(N) メモリを使用しますが、array.arrayまたはnumpy.ndarrayを使用する場合は、ファイル全体よりもかなり小さい N*4 バイトについて話していることになります。(簡単にするために単純なリストを使用します。よりコンパクトな型に変換するのに助けが必要な場合は、それも示します。)

一時データベースとインデックス リストの使用:

with contextlib.closing(dbm.open('temp.db', 'n')) as db:
    with open(path) as f:
        for i, line in enumerate(f):
            db[str(i)] = line
    linecount = i
    shuffled = random.shuffle(range(linecount))
    with open(path + '.shuffled', 'w') as f:
        for i in shuffled:
            f.write(db[str(i)])
os.remove('temp.db')

これは、2N の単一行ディスク操作と 2N の単一 dbm キー ディスク操作であり、2NlogN の単一ディスク ディスク操作と同等の操作であるため、合計の複雑さは O(NlogN) です。

dbm の代わりにリレーショナル データベースを使用する場合は、次のようsqlite3にするだけでよいため、インデックス リストも必要ありません。

SELECT * FROM Lines ORDER BY RANDOM()

これは上記と同じ時間の複雑さを持ち、理論上、空間の複雑さは O(N) ではなく O(1) です。実際には、1 億行セットから一度に 1 行ずつフィードできる RDBMS が必要です。

一時データベースを使用しない別のオプション — 理論的には O(N**2) ですが、実際には、ライン キャッシュが役立つ十分なメモリがあればより高速になる可能性があります。

with open(path) as f:
    linecount = sum(1 for _ in f)
shuffled = random.shuffle(range(linecount))
with open(path + '.shuffled', 'w') as f:
    for i in shuffled:
        f.write(linecache.getline(path, i))

最後に、インデックス リストのサイズを 2 倍にすることで、一時的なディスク ストレージをなくすことができます。しかし、実際には、これはかなり遅くなる可能性があります。これは、ドライブがそれほど得意ではない、より多くのランダムアクセス読み取りを行っているためです。

with open(path) as f:
    linestarts = [f.tell() for line in f]
    lineranges = zip(linestarts, linestarts[1:] + [f.tell()])
    shuffled = random.shuffle(lineranges)
    with open(path + '.shuffled', 'w') as f1:
        for start, stop in shuffled:
            f.seek(start)
            f1.write(f.read(stop-start))
于 2013-10-10T19:38:48.093 に答える
2

これは、上記の私のコメントに基づく提案です。圧縮された行がまだメモリに収まることに依存しています。そうでない場合は、他のソリューションが必要になります。

import zlib
from random import shuffle

def heavy_shuffle(filename_in, filename_out):
    with open(filename_in, 'r') as f:
        zlines = [zlib.compress(line, 9) for line in f]
    shuffle(zlines)
    with open(filename_out, 'w') as f:
        for zline in zlines:
            f.write(zlib.decompress(zline) + '\n')

私の経験では、zlib は高速ですが、bz2 の方が圧縮率が高いため、比較することをお勧めします。

また、たとえば n 行をまとめてチャンク化することができれば、そうすることで圧縮率が上がる可能性があります。

有用な圧縮の可能性について疑問に思っていたので、ここに IPython の実験があります。あなたのデータがどのように見えるかわからないので、フロート (文字列として) を 3 桁に丸め、パイプでつなぎました:

最良のシナリオ (たとえば、多くの行がすべて同じ数字を持つ):

In [38]: data = '0.000|'*200

In [39]: len(data)
Out[39]: 1200

In [40]: zdata = zlib.compress(data, 9)

In [41]: print 'zlib compression ratio: ',1.-1.*len(zdata)/len(data)
zlib compression ratio:  0.98

In [42]: bz2data = bz2.compress(data, 9)

In [43]: print 'bz2 compression ratio: ',1.-1.*len(bz2data)/len(data)
bz2 compression ratio:  0.959166666667

予想どおり、最良のケースは非常に良好で、圧縮率は 95% を超えています。

最悪のシナリオ (ランダム化されたデータ):

In [44]: randdata = '|'.join(['{:.3f}'.format(x) for x in np.random.randn(200)])

In [45]: zdata = zlib.compress(randdata, 9)

In [46]: print 'zlib compression ratio: ',1.-1.*len(zdata)/len(data)
zlib compression ratio:  0.5525

In [47]: bz2data = bz2.compress(randdata, 9)

In [48]: print 'bz2 compression ratio: ',1.-1.*len(bz2data)/len(data)
bz2 compression ratio:  0.5975

驚くべきことに、圧縮率が 60% までの最悪の場合でもそれほど悪くはありませんが、メモリが 8 GB しかない場合 (15 GB の 60% は 9 GB) は問題になる可能性があります。

于 2013-10-11T04:21:17.167 に答える
0

この問題は、スワップ ファイル I/O を削減するための効率的なメモリ ページ管理の問題と考えることができます。バッファbufを、出力ファイルに保存したいファイルの連続したチャンクのリストにします。ファイルの連続したチャンクを、一定量の行全体のリストとします。

次に、ランダムなシーケンスを生成し、返された値を再マッピングして、そのチャンク内のチャンク番号と行オフセットを適切に割り当てます。

この操作により[1..num of chunks]、[1..num of chunks]. オンライン バリアント (実際の OS など) の場合、この問題に対する最適な戦略はありませんが、ページの参照の実際の順序がわかっているため、ここで見つけることができる最適な解決策があります。

このアプローチのメリットは何ですか? 最も頻繁に使用されるページは、HDD からの再読み取りが最も少なく、データを読み取るための I/O 操作が少なくなります。また、チャンク サイズがメモリ フットプリントと比較してページ スワップを最小限に抑えるのに十分な大きさであることを考慮すると、多くの場合、出力ファイルの次の行は、メモリに格納されている同じチャンク (または、まだスワップされていない他のチャンク) から取得されます。ドライブから再読み取りするのではなく、ドライブ)。

おそらく、これは最も簡単な解決策ではないかもしれませんが (最適なページ スワッピング アルゴリズムは簡単に記述できます)、それは楽しい練習になるのではないでしょうか?

于 2013-10-10T19:55:06.990 に答える
0

ディスク容量に問題がないと仮定して、データを保持するために複数のファイルを作成しています。

import random
import os

PMSize = 100 #Lesser value means using more primary memory
shuffler = lambda x: open(x, 'w')
shufflers = [shuffler('file'+str(x)) for x in range(PMSize)]

with open('filename') as file:
    for line in file:
        i = random.randint(0, len(shufflers)-1)
        shufflers[i].write(line)

with open('filename', 'w') as file:
    for file in shufflers:
        newfile.write(file.read())

for file in shufflers:
    os.remove(file)

メモリの複雑さは PMSize によって制御されます。時間の計算量は O(N + PMSize) 程度になります。

于 2013-10-10T19:55:28.540 に答える