Я уже писал об этом однажды на SO, но я воспроизведу это здесь, потому что это довольно круто. Он использует хеширование, создавая что-то вроде хэша, установленного на месте. Он гарантированно будет O (1) в подмышечном пространстве (рекурсия - это хвостовой вызов), и, как правило, O (N) сложность времени. Алгоритм выглядит следующим образом:
- Возьмите первый элемент массива, это будет страж.
- Переупорядочьте остальную часть массива, насколько это возможно, так, чтобы каждый элемент находился в позиции, соответствующей его хешу. По завершении этого шага будут обнаружены дубликаты. Установите их равными часовому.
- Переместить все элементы, для которых индекс равен хешу, в начало массива.
- Переместить все элементы, равные часовому, кроме первого элемента массива, в конец массива.
- То, что осталось между правильно хешированными элементами и дублирующимися элементами, будет теми элементами, которые не могли быть помещены в индекс, соответствующий их хешу из-за столкновения. Рекурс для работы с этими элементами.
Можно показать, что это O (N), если в хешировании нет патологического сценария: даже если дубликатов нет, примерно 2/3 элементов будут исключаться при каждой рекурсии. Каждый уровень рекурсии равен O (n), где small n - количество оставшихся элементов. Единственная проблема состоит в том, что на практике это медленнее, чем быстрая сортировка, когда имеется несколько дубликатов, то есть много коллизий. Однако, когда есть огромное количество дубликатов, это удивительно быстро.
Редактировать: в текущих реализациях D hash_t составляет 32 бита. Все, что касается этого алгоритма, предполагает, что в 32-битном пространстве будет очень мало коллизий хешей, если они вообще есть. Однако столкновения могут часто происходить в пространстве модулей. Однако это предположение, по всей вероятности, будет справедливо для любого набора данных разумного размера. Если ключ меньше или равен 32 битам, это может быть собственный хэш, что означает, что конфликт в полном 32-битном пространстве невозможен. Если он больше, вы просто не сможете разместить их достаточно в адресном пространстве 32-битной памяти, чтобы это стало проблемой. Я предполагаю, что hash_t будет увеличен до 64 бит в 64-битных реализациях D, где наборы данных могут быть больше. Кроме того, если это когда-либо окажется проблемой, можно изменить хэш-функцию на каждом уровне рекурсии.
Вот реализация на языке программирования 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);
}