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

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

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

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

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

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

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

見直していて94行目がまずいことに気がつきました。
ハッシュテーブルのfdはクローズする前に
使用されていないことが確実でないといけませんね。

--- doukaku67_2.c    2007-10-27 11:40:13.265625000 +0900
+++ doukaku67.c.usethread    2007-10-27 11:54:29.687500000 +0900
@@ -91,7 +91,12 @@
     } else {
       if( (table_fd = open(table_name, O_RDWR | O_CREAT, 0600)) == -1 ){ return -1; }
     }
-    if( fd_history[hist_cursor].fd != -1 ) close( fd_history[hist_cursor].fd );
+    if( fd_history[hist_cursor].fd != -1 )
+    {
+      pthread_mutex_lock( &hash_mutex[ fd_history[hist_cursor].val ] );
+        close( fd_history[hist_cursor].fd );
+      pthread_mutex_unlock( &hash_mutex[ fd_history[hist_cursor].val ] );
+    }
     fd_history[hist_cursor].val= hash_value;
     fd_history[hist_cursor].fd = table_fd;
     hist_cursor++; hist_cursor &= 0x7f;
@@ -162,10 +167,8 @@
   /* ハッシュテーブルへ追加 */
   hash_value = calcHashValue(ins_item.text, sizeof(ins_item.text));
 
+  table_fd = history_fd_open(hash_value, 1);
   pthread_mutex_lock( &hash_mutex[hash_value] );
-    pthread_mutex_lock( &tc.mutex );
-      table_fd = history_fd_open(hash_value, 1);
-    pthread_mutex_unlock( &tc.mutex );
     lseek(table_fd, 0, SEEK_SET); seek = 0;
     while( (read_size = read( table_fd, sel_buf, sizeof(sel_buf) ) ) > 0 )
     {

L:17以降の差分は嘘です。 @@ -162,10 +167,8 @@
連続投稿申し訳ないです。

オープンはプロセス内で排他制御しないといけないので
クローズの時だけ排他制御を追加すれば
問題ないはずでした。
うーん、いろいろ歪みががが

--- doukaku67_2.c    2007-10-27 11:40:13.265625000 +0900
+++ doukaku67.c.usethread    2007-10-27 11:54:29.687500000 +0900
@@ -91,7 +91,12 @@
     } else {
       if( (table_fd = open(table_name, O_RDWR | O_CREAT, 0600)) == -1 ){ return -1; }
     }
-    if( fd_history[hist_cursor].fd != -1 ) close( fd_history[hist_cursor].fd );
+    if( fd_history[hist_cursor].fd != -1 )
+    {
+      pthread_mutex_lock( &hash_mutex[ fd_history[hist_cursor].val ] );
+        close( fd_history[hist_cursor].fd );
+      pthread_mutex_unlock( &hash_mutex[ fd_history[hist_cursor].val ] );
+    }
     fd_history[hist_cursor].val= hash_value;
     fd_history[hist_cursor].fd = table_fd;
     hist_cursor++; hist_cursor &= 0x7f;

DouKaku?

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

Posted feedbacks - diff

Index

Feed

Other

Link

Pathtraq