2

私は SO や他の場所でさまざまな同様の質問を見てきましたが、新しい質問を正当化する特別な状況があると感じました。

これは質問です：

最大 10 億の整数を格納できる整数の配列があります。これらの数値は 10 億から 10 億の間ですが、値が欠落している可能性があります。したがって、値ごとに 32 ビットで十分です。私がやりたいことは、重複がないことを確認することだけです。重複の最初の発生を見つけた瞬間、大騒ぎして終了します。これは多数のファイルに対して行う必要があり、ファイルに重複があることはめったにないと予想されます。そのため、平均的なケースが最悪のケースになることもよくあります。

シェルでこれを非常に簡単に行う方法を知っています（テキストファイルで、次の整数を読み取ります：sort | uniqなど）。約13秒かかります。したがって、うまくいけば、純粋な C スマート アルゴリズムの方がうまくいくでしょう。私の考えは、配列で高速な (できればすぐに利用できる) 並べ替えを使用し、連続する各ペアの違いを繰り返し計算するというものです。ゼロを見つけた瞬間、立ち止まって終了します。

おもちゃの例を次に示します。

1001
1002
1003
1004
1005
1003
...

最初に配列をソートして取得します: 1001 1002 1003 1003 1004 1005 ...

次に、line3 - line4 == 0 と表示された 4 行目で停止します。

すべてが順調であれば、終了コード 0 で黙って終了します。

これらは私の要件/制約です: 1) 私は C の初心者です (私のベルトの下には数百行のコードしかありません)。2) 私は純粋な C ソリューションを学ぶことを強く好みます。標準ライブラリは問題ありません。3) C++ ソリューションがプログラミング時間の短縮に関して非常に優れている場合は、それも提案してください。

どうもありがとう。

4

3 に答える 3

2

ハッシュ ソリューションの簡単な疑似コードを次に示します。これにより、その背後にある「概念」がわかります。C にしようと思いますが、コンパイルとテストが完了しているとは限りません。しかし、それは近いでしょう。

#include <iostream>
using namespace std;

const int NUM_BITS = 32;

bool noDuplicates(const int INPUT[], const int SIZE, const int MIN_VALUE, const int MAX_VALUE) {

    const unsigned int RANGE = (MAX_VALUE - MIN_VALUE) / NUM_BITS;  //Use unsigned int, can support wider ranges this way.

    int isPresent[RANGE];// Might need dynamic allocation here, don't know if C supports this type of array initialization

    for(int i = 0; i < RANGE; i++) isPresent[i] = 0;//Probably don't need this loop on most systems.  Aslo, there are faster ways to zero memory.

    for(int i = 0; i < SIZE; i++) {

        const int ADJUST_TO_ZERO = INPUT[i] - MIN_VALUE; //adjust our min value to zero index now every possible value should map to an indice in our "isPresent" array
        const int INT_IN_ARRAY = ADJUST_TO_ZERO / NUM_BITS; // Each int represents 32 values, or our bit is hiding in the (VALUE/32)th slot
        const unsigned int BIT_VALUE = 1 << (ADJUST_TO_ZERO % NUM_BITS); // This is identical to 2 ^ (ADJUST_TO_ZERO % NUM_BITS)

        cout << "CHECKING: " << ADJUST_TO_ZERO << " ARRAY INDEX: " << INT_IN_ARRAY << " BIT:" << (ADJUST_TO_ZERO % NUM_BITS) << " INT REPRESENTATION: " << BIT_VALUE << endl;

        if(isPresent[INT_IN_ARRAY] & BIT_VALUE) { //bitwise &, with a value 2 ^ BIT, isolates this "BIT"
            return false;
        }

        isPresent[ADJUST_TO_ZERO / NUM_BITS] += BIT_VALUE; //If we add 2^BIT to an int, we are only adding the value to this to set this "BIT"
    }
    return true; //If we escape the loop above there are no duplicates
}


int main() {
    const int SIZE = 65;
    int array[SIZE];

    for(int i = 0; i < SIZE; i++) {
        array[i] = i;
    }

    array[SIZE - 1] = 30;

    cout << "RESULT: " << noDuplicates(array, SIZE, 0, 100) << endl;
}
于 2013-06-04T13:25:01.327 に答える
1

値の範囲が何であるかはわかりませんが、それが 32 ビット整数の範囲であると仮定すると、ビットマップ配列は 512MB になり、ほとんどの最新のマシンに問題なく収まります。次のようなことを試してください：

/* Assumes 32-bit ints */
int verify_unique( <data source> ) {
    unsigned int *bitmap = calloc(128 * 1024 * 1024, 4);
    if (!bitmap) { <error> }

    while ( <more input> ) {
        unsigned int value = <next value>;
        unsigned int index = value >> 5;
        unsigned int mask = 1 << (value & 0x1f);

        if (bitmap[index] & mask) {
            <found duplicate>
            break;
        }
        bitmap[index] |= mask;
    }
    free(bitmap);
}
于 2013-06-04T15:39:40.513 に答える
0

並べ替えをカウントして配列を並べ替えてから、 link3から link4 を引いた方法を実行します。目的に対して十分に効率的である必要があります。

于 2013-06-04T13:19:40.197 に答える