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

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

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

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

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

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

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

全行一回なめて行頭n文字が同じだった行の位置を記録します。
んで巻き戻して読んでいって、さっき記録した疑わしい行がある場合、実際見に行って比較、表示か非表示を決めます。

60メガ100万行のファイルでメモリ30メガ、44秒くらいでした。

def fetch(fin, head)
  cur = fin.pos
  fin.pos = head
  s = fin.gets
  fin.pos = cur
  s
end

def line_with_headpos(fin)
  head = fin.pos
  while line = fin.gets
    yield(line, head)
    head = fin.pos
  end
end

def zoku(fn, n=5)
  open(fn){|fin|
    h = {}

    line_with_headpos(fin){|line, head|
      (h[line[0,n]] ||= []) << head
    }

    fin.rewind

    line_with_headpos(fin){|line, head|
      flag = h[line[0,n]].any?{|ps|
        head < ps && line == fetch(fin, ps)
      }
      print line unless flag
    }
  }
end

zoku(ARGV[0])

構想は同じですが、なんかすっきりしてないなぁ。
line_with_headposを拝借させていただきました。

def line_with_headpos(fin)
  head = fin.pos
  while line = fin.gets
    yield(line, head)
    head = fin.pos
  end
end

def deldup(file)
  require 'digest/md5'
  
  buf = Hash.new
  open(file, 'r') {|io|
    
    line_with_headpos(io){|line, head|
      (buf[Digest::MD5.digest(line)] ||= []) << head
    }
    
    buf.each_value {|val|
      0.upto(val.size-2) {|i|
        io.pos = i
        idat = io.gets
        i.upto(val.size-1) {|j|
          io.pos = j
          if idat == io.gets
            val[i] = -1
            break
          end
        }
      }
    }
    
    buf.values.flatten.select {|i|
      i != -1
    }.sort.each {|i|
      io.pos = i
      print io.gets
    }
  }
end

deldup(ARGV[0])

外部コマンドsortを使ってます。
・対象ファイルの各行のハッシュ値をテンポラリファイルに出力
・テンポラリファイルを順ソート後、読み込んで重複行数をカウント
・対象ファイルを再読込、重複行に出会うたびに重複行数カウントをデクリメント
100万行、60MBの数字のみファイルで、実行時間は50秒、メモリ35MB使用です。
マシンはCelleon2.8Ghz、メモリ1GB、Ubuntu7.04。

require 'tempfile'

def make_big_seq_file(cntmax,lthmin,eps)
  cntmax.times {
    s = ""
    (lthmin+rand(eps)).times {
      s << rand(10).to_s
    }
    puts s
  }
end

#make_big_seq_file(10**6,50,20)

def double_line_reject(f)
  h = Hash.new(0)

  temp = Tempfile::new("foobar")
  open(f) {|fin|
    while line = fin.gets
      temp.puts(line.hash)
    end
    temp.close

    f = open("|sort #{temp.path}")
    iold = ""
    f.each {|i|
      i = i.chomp.to_i
      h[i] += 1 if iold == i
      iold = i
    }
    fin.rewind
    while line = fin.gets
      puts line if h[line.hash] < 1
      h[line.hash] -= 1
    end
  }
end

double_line_reject(ARGV[0])

DouKaku?

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

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq