[c] 알고리즘 : 배열에서 중복 정수를 제거하는 효율적인 방법

예전에 한번 올렸는데 꽤 멋있기 때문에 여기서 재현하겠습니다. 해싱을 사용하여 제자리에 설정된 해시와 같은 것을 만듭니다. 겨드랑이 공간에서 O (1)이 보장되며 (재귀는 꼬리 호출 임) 일반적으로 O (N) 시간 복잡도입니다. 알고리즘은 다음과 같습니다.

1. 배열의 첫 번째 요소를 가져 오면 이것이 센티널이됩니다.
2. 각 요소가 해시에 해당하는 위치에 있도록 가능한 한 나머지 배열의 순서를 변경하십시오. 이 단계가 완료되면 중복 항목이 발견됩니다. 센티넬과 동일하게 설정하십시오.
3. 인덱스가 해시와 동일한 모든 요소를 ​​배열의 시작 부분으로 이동합니다.
4. 배열의 첫 번째 요소를 제외하고 sentinel과 동일한 모든 요소를 ​​배열의 끝으로 이동합니다.
5. 올바르게 해시 된 요소와 중복 요소 사이에 남는 것은 충돌로 인해 해시에 해당하는 인덱스에 배치 할 수없는 요소입니다. 이러한 요소를 처리하려면 재귀하십시오.

이것은 해싱에 병리학 적 시나리오가없는 경우 O (N)으로 표시 될 수 있습니다. 중복 항목이 없더라도 각 재귀에서 요소의 약 2/3가 제거됩니다. 각 재귀 수준은 O (n)이며 small n은 남은 요소의 양입니다. 유일한 문제는 실제로 중복이 거의 없을 때 즉, 많은 충돌이있을 때 빠른 정렬보다 느리다는 것입니다. 그러나 엄청난 양의 중복이있을 때는 놀랍도록 빠릅니다.

편집 : D의 현재 구현에서 hash_t는 32 비트입니다. 이 알고리즘에 대한 모든 것은 전체 32 비트 공간에서 해시 충돌이 거의 없다고 가정합니다. 그러나 충돌은 모듈러스 공간에서 자주 발생할 수 있습니다. 그러나이 가정은 합리적인 크기의 데이터 세트에 대해 모두 사실입니다. 키가 32 비트보다 작거나 같으면 자체 해시가 될 수 있으므로 전체 32 비트 공간에서 충돌이 불가능합니다. 더 크면 문제가 될 수있는 32 비트 메모리 주소 공간에 충분히 들어갈 수 없습니다. 저는 D의 64 비트 구현에서 hash_t가 64 비트로 증가 할 것이라고 가정합니다. 여기서 데이터 세트는 더 클 수 있습니다. 또한 이것이 문제가된다면 각 재귀 수준에서 해시 함수를 변경할 수 있습니다.

다음은 D 프로그래밍 언어로 구현 된 것입니다.

void uniqueInPlace(T)(ref T[] dataIn) {
    uniqueInPlaceImpl(dataIn, 0);
}

void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) {
    if(dataIn.length - start < 2)
        return;

    invariant T sentinel = dataIn[start];
    T[] data = dataIn[start + 1..$];

    static hash_t getHash(T elem) {
        static if(is(T == uint) || is(T == int)) {
            return cast(hash_t) elem;
        } else static if(__traits(compiles, elem.toHash)) {
            return elem.toHash;
        } else {
            static auto ti = typeid(typeof(elem));
            return ti.getHash(&elem);
        }
    }

    for(size_t index = 0; index < data.length;) {
        if(data[index] == sentinel) {
            index++;
            continue;
        }

        auto hash = getHash(data[index]) % data.length;
        if(index == hash) {
            index++;
            continue;
        }

        if(data[index] == data[hash]) {
            data[index] = sentinel;
            index++;
            continue;
        }

        if(data[hash] == sentinel) {
            swap(data[hash], data[index]);
            index++;
            continue;
        }

        auto hashHash = getHash(data[hash]) % data.length;
        if(hashHash != hash) {
            swap(data[index], data[hash]);
            if(hash < index)
                index++;
        } else {
            index++;
        }
    }


    size_t swapPos = 0;
    foreach(i; 0..data.length) {
        if(data[i] != sentinel && i == getHash(data[i]) % data.length) {
            swap(data[i], data[swapPos++]);
        }
    }

    size_t sentinelPos = data.length;
    for(size_t i = swapPos; i < sentinelPos;) {
        if(data[i] == sentinel) {
            swap(data[i], data[--sentinelPos]);
        } else {
            i++;
        }
    }

    dataIn = dataIn[0..sentinelPos + start + 1];
    uniqueInPlaceImpl(dataIn, start + swapPos + 1);
}