続・ファイル内の重複行削除
Posted feedbacks - PHP
ファイルシステムってでっかい連想記憶装置ですよね。 というわけで、ファイルを行ごとにMD5のファイル名で分割しながら重複を調べて それを統合してみました。 統合時にはファイル名を行番号に書き替えて、0から順に読んでいます。 MD5がかち合っていた場合は1行読んだら次に含まれている行の行番号にファイル名を 更に書き替えておきます。 あんまり一つのディレクトリにファイルが多くなりすぎてもまずいので 実際にはもう一段ハッシュして振り分けています。 メモリーの最大使用量は最も長い行の倍程度。 扱えるのは2G行までです。 調子に乗って331MByte190万行のログファイル(重複行なし)を突っ込んでみたら 3時間半経っても終わる気配がなくて止めてしまいました。 140万行くらいは読み込んでいたようです。 そこから後半だけ走らせているのですが、140万ファイルのリネームもやっぱり 3時間半近くかかるのかもしれません…(^_^;) もう少しバランスの良さそうな方法も考えてたのですが、こういう場なので 行くとこまで行ってみるのもいいかなと…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | <?php
$t=time();
if(!($fp=fopen($argv[1],"rt")))
exit(1);
// 行ごとにファイル"tmp1/(crc12)/(md5)"に振り分け
@mkdir("tmp1");
for($line=0;($str=fgets($fp))!==false;++$line)
{ $path=sprintf("tmp1/%x",crc32($str)&0xfff);
@mkdir($path);
$path.="/".md5($str);
$len=strlen($str);
if(($fp1=@fopen($path,"r+b"))!==false)
{ $tail=0; $p=0;
while(($str2=fread($fp1,8))!=="")
{ $a=unpack("l2",$str2);
if($a[1]>=0 && $a[2]==$len)
{ if(fread($fp1,$len)==$str)
{ fseek($fp1,$p);
fwrite($fp1,pack("l",-1));
fseek($fp1,$a[2]+4,SEEK_CUR);
$a[1]=-1;
}
}
else
fseek($fp1,$a[2],SEEK_CUR);
$p=ftell($fp1);
if($a[1]>=0)
{ echo $a[1],",";
$tail=$p;
}
}
if($tail>0)
echo "$line hash collision\n";
fseek($fp1,$tail);
ftruncate($fp1,$tail);
}
else if(($fp1=fopen($path,"wb"))===false)
exit(1);
fwrite($fp1,pack("l2",$line,$len));
fwrite($fp1,$str);
fclose($fp1);
}
fclose($fp);
// ハッシュファイルを "tmp2/(行番号/1000)/(行番号)" にリネーム
@mkdir("tmp2");
if($dh = opendir("tmp1"))
{ while(($dir = readdir($dh)) !== false)
{ if(substr($dir,0,1)!='.'&&is_dir("tmp1/$dir"))
{ if($dh1 = opendir("tmp1/$dir"))
{ while(($file = readdir($dh1)) !== false)
{ if(is_file($path="tmp1/$dir/$file"))
{ if(($fp=fopen($path,"rb"))!==false)
{ $l=-1;
while(($str=fread($fp,8))!=="")
{ $a=unpack("l2",$str);
if($a[1]>=0)
{ $l=$a[1];
break;
}
fseek($fp,$a[2],SEEK_CUR);
}
fclose($fp);
if($l>=0)
{ $path2="tmp2/".(int)($l/1000);
@mkdir($path2);
rename($path,"$path2/$l");
}
}
}
}
}
}
}
}
// 行番号順にファイルを読んで出力
if(!($fp=fopen($argv[2],"wt")))
exit(1);
for($l=0;$l<$line;++$l)
{ $path="tmp2/".(int)($l/1000)."/$l";
if(($fp1=@fopen($path,"rb"))!==false)
{ $next=-1;
while(($str=fread($fp1,8))!=="")
{ $a=unpack("l2",$str);
if($a[1]==$l)
{ fwrite($fp,fread($fp1,$a[2]));
continue;
}
if($a[1]>$l)
{ $next=$a[1];
break;
}
fseek($fp1,$a[2],SEEK_CUR);
}
fclose($fp1);
if($next<0)
unlink($path);
else
rename($path,"tmp2/".(int)($next/1000)."/$next");
}
}
fclose($fp);
echo time()-$t,"sec\n";
?>
|
各行のcrcをとり、その内の5bitで32のファイルに振り分け、 各ファイルの中では別の11bitで2048の一方向リストに振り分けることで 比較の回数を削減しつつディスクアクセスのオーバーヘッドを減らしました。 最後にマージソートしていますが、その際はリンクリストは無視して ファイル上の並び順でそのまま合ってるので簡単です。 上限は2G行または32個のハッシュファイルのどれかが2G越えるまでなので 4Gくらいなら楽勝デス。 330MByte 190万行 を(デスクトップは140万個のファイルの削除中のため) ノートPCの2.5インチ5400rpmのHDDで処理したところ 799秒でした。 webサーバのログだったのですが、分割ダウンロードしているヒトがいると 重複する行がけっこうあるんですね…。同じファイルが出来ると思っていたら ファイルサイズが小さくなっていてびっくりしました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | <?php
define("HUSHBIT1",11);
define("HUSHBIT2",5);
$t=time();
$tmpdir = tempnam(".", "tmp");
@unlink($tmpdir);
@mkdir($tmpdir);
$tmp=array();
$b=pack("l",0);
for($i=0;$i<(1<<HUSHBIT2);++$i)
{ if(!($fp = fopen("$tmpdir/$i", "w+b")))
exit(1);
for($j=0;$j<(1<<HUSHBIT1);++$j)
fwrite($fp,$b);
$tmp[]=array($fp,4<<HUSHBIT1);
}
for($line=0;($str=fgets(STDIN))!==false;++$line)
{ $crc=crc32($str);
$len=strlen($str);
$crc1=$crc&((1<<HUSHBIT1)-1);
$crc2=($crc>>HUSHBIT1)&((1<<HUSHBIT2)-1);
$fp=$tmp[$crc2][0];
fseek($fp,$crc1<<2);
list(,$p)=unpack("l",fread($fp,4));
if(!$p)
{ fseek($fp,-4,SEEK_CUR);
fwrite($fp,pack("l",$tmp[$crc2][1]));
}
else
{ do{
fseek($fp,$p);
$a=unpack("l3",fread($fp,12));
if($a[1]>=0 && $a[3]==$len)
{ $str2=fread($fp,$len);
if($str2==$str)
{ fseek($fp,$p);
fwrite($fp,pack("l",-1));
}
}
if(!$a[2])
{ fseek($fp,$p+4);
fwrite($fp,pack("l",$tmp[$crc2][1]));
break;
}
$p=$a[2];
}while(1);
}
fseek($fp,$tmp[$crc2][1]);
$l=fwrite($fp,pack("l3",$line,0,$len));
$l+=fwrite($fp,$str);
$tmp[$crc2][1]+=$l;
}
$sortbuf=array();
for($i=0;$i<(1<<HUSHBIT2);++$i)
{ $fp=$tmp[$i][0];
fseek($fp,4<<HUSHBIT1);
while(($str=fread($fp,8))!='')
{ $a=unpack("l2",$str);
if($a[1]>=0)
{ $sortbuf[$i]=$a[1];
break;
}
$a=unpack("l",fread($fp,4));
fseek($fp,$a[1],SEEK_CUR);
}
}
while(count($sortbuf))
{ asort($sortbuf);
$i=key($sortbuf);
$fp=$tmp[$i][0];
list(,$len)=unpack("l",fread($fp,4));
echo fread($fp,$len);
do{
if(($str=fread($fp,8))=='')
{ unset($sortbuf[$i]);
break;
}
list(,$sortbuf[$i])=unpack("l2",$str);
if($sortbuf[$i]>=0)
break;
$a=unpack("l",fread($fp,4));
fseek($fp,$a[1],SEEK_CUR);
}while(1);
}
for($i=0;$i<(1<<HUSHBIT2);++$i)
{ fclose($tmp[$i][0]);
unlink("$tmpdir/$i");
}
rmdir($tmpdir);
fwrite(STDERR,sprintf("%dsec\n",time()-$t));
?>
|
にしお
#3424()
Rating1/1=1.00
「 ファイル内の重複行削除(後優先) 」の続編です。
1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。
このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、 スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。
しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。
こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。
追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。
[ reply ]