続・ファイル内の重複行削除 in Python DouKaku?

「ファイル内の重複行削除(後優先) 」の続編です。

1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。

このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。

しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。

こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。

追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。

python付属ののDBパッケージを使っています。
実際にどれだけのサイズが扱えるのか未確認なので
本当にこれでうまく行くかどうかは分かりません。

import os, sys, dumbdbm, md5

db = dumbdbm.open('tmp')
fp = file(sys.argv[1], 'r')
i = 0
for s in fp:
  k = md5.md5(s).digest()
  if db.has_key(k):
    db[db[k]] = '0'
  db[k] = str(i)
  db[str(i)] = '1'
  i += 1

fp.seek(0)
i = 0
for s in fp:
  if db[str(i)] == '1':
    sys.stdout.write(s)
  i += 1
fp.close()
db.close()

os.remove('tmp.dat')
os.remove('tmp.dir')
os.remove('tmp.bak')

と言うわけで、改訂版を投稿させていただきます。

使用メモリ量は非常に少なく、psコマンドでは9.2MBと出ます。

16MBのテストデータが問題なく完走したので、思い切って512MBのデータを
処理してみましたが、数時間たった今現在も終わる気配がありません。

残念ながらこのコードでは、大きなデータを許容できる時間内に処理することは
無理なようです。

import os, sys, bsddb

db = bsddb.hashopen('tmp.dat')
fp = file(sys.argv[1], 'r')
wfp = file(sys.argv[2], 'w')
i = 0
for s in fp:
  db[s] = str(i)
  i += 1

fp.seek(0)
i = 0
for s in fp:
  if db[s] == str(i):
    wfp.write(s)
  i += 1
fp.close()
wfp.close()
db.close()

os.remove('tmp.dat')

DouKaku?

続・ファイル内の重複行削除

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq