0

約 (15000-25000) 行 (固定サイズ) の csv ファイルがあり、c 言語を使用して重複行を検出する方法を知りたいです。

出力の例は次のとおりです。

0123456789;CUST098WZAX;35

メモリや時間の制約がないため、最も簡単なソリューションが必要です。

ご協力いただきありがとうございます。

4

3 に答える 3

4 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct somehash {
        struct somehash *next;
        unsigned hash;
        char *mem;
        };

#define THE_SIZE 100000
struct somehash *table[THE_SIZE] = { NULL,};

struct somehash **some_find(char *str, unsigned len);
static unsigned some_hash(char *str, unsigned len);

int main (void)
{
char buffer[100];
struct somehash **pp;
size_t len;

while (fgets(buffer, sizeof buffer, stdin)) {
        len = strlen(buffer);
        pp = some_find(buffer, len);
        if (*pp) { /* found */
                fprintf(stderr, "Duplicate:%s\n", buffer);
                }
        else    {       /* not found: create one */
                fprintf(stdout, "%s", buffer);
                *pp = malloc(sizeof **pp);
                (*pp)->next = NULL;
                (*pp)->hash = some_hash(buffer,len);
                (*pp)->mem = malloc(1+len);
                memcpy((*pp)->mem , buffer,  1+len);
                }
        }
return 0;
}
struct somehash **some_find(char *str, unsigned len)
{
unsigned hash;
unsigned slot;
struct somehash **hnd;

hash = some_hash(str,len);
slot = hash % THE_SIZE;
for (hnd = &table[slot]; *hnd ; hnd = &(*hnd)->next ) {
        if ( (*hnd)->hash != hash) continue;
        if ( strcmp((*hnd)->mem , str) ) continue;
        break;
        }
return hnd;
}

static unsigned some_hash(char *str, unsigned len)
{
unsigned val;
unsigned idx;

if (!len) len = strlen(str);

val = 0;
for(idx=0; idx < len; idx++ )   {
        val ^= (val >> 2) ^ (val << 5) ^ (val << 13) ^ str[idx] ^ 0x80001801;
        }
return val;
}
于 2012-04-17T11:58:39.333 に答える
0

最も単純なアルゴリズム：

  1. 元のファイルを行の配列Aとしてメモリにロードします。
  2. 同じサイズの別の配列Bを作成します。
  3. Aを繰り返します。Bの現在の行を線形検索します。そこにない場合は、Bと出力ファイルに追加します。

これは非常に単純で、残忍で非効率的なO（n ^ 2）ソリューションです。基本的なCスキルがあることを前提とすると、実装は非常に簡単です。

ちなみに、順序が重要でない場合は、ファイルを並べ替えると、タスクはさらに簡単になります。最初にファイルを並べ替えてから、最後の行の変数を取得します。これに対して現在の変数を確認し、最後の行と等しい場合は現在の変数をスキップします。

于 2012-04-17T12:35:12.307 に答える
0

これが最も簡単な解決策かどうかはわかりませんが...

すべてのエントリが次のようになっている場合:

0123456789;CUST098WZAX;35

... 最後の 2 文字は常に00-の値99です。この値を使用してバケットのインデックスを作成できます。このバケットは、100 の配列 (つまり、値のように 0 から 99) の 1 つの項目であり、それぞれがそのバケットに属する文字列を格納する構造のリンクされたリストを指します。

文字列がバケットにソートされると、重複を識別するために必要な完全な文字列の比較の数が (うまくいけば) 大幅に削減されます。同じバケットにある文字列を比較するだけです。

すべてのエントリが同じ値を持つ場合、これはすべてのエントリを同じバケットに入れ、このメソッドを比較ステップだけで O(n^2) に低下させます。しかし、値のさまざまな分布を想定すると、この方法は実際には高速になります。

（もちろん、ハッシュテーブルについて説明しましたが、通常使用されるよりも単純なハッシュ関数を使用しています。）

于 2012-04-17T11:21:06.307 に答える