J'ai déjà publié ce message sur SO, mais je le reproduis ici parce que c'est plutôt cool. Il utilise le hachage, en construisant quelque chose comme un ensemble de hachage en place. Il est garanti d'être O(1) dans l'espace axillaire (la récursion est un appel de queue), et est typiquement O(N) de complexité en temps. L'algorithme est le suivant :
- Prenez le premier élément du tableau, ce sera la sentinelle.
- Réorganisez le reste du tableau, autant que possible, de façon à ce que chaque élément se trouve à la position correspondant à son hachage. Au fur et à mesure de cette étape, des doublons seront découverts. Mettez-les à la valeur de sentinelle.
- Déplace tous les éléments pour lesquels l'index est égal au dièse au début du tableau.
- Déplace tous les éléments qui sont égaux à sentinel, sauf le premier élément du tableau, à la fin du tableau.
- Ce qui reste entre les éléments correctement hachés et les éléments en double sera les éléments qui n'ont pas pu être placés dans l'index correspondant à leur hachage à cause d'une collision. La récursion permet de traiter ces éléments.
On peut montrer que c'est O(N) à condition qu'il n'y ait pas de scénario pathologique dans le hachage : même s'il n'y a pas de doublons, environ 2/3 des éléments seront éliminés à chaque récursion. Chaque niveau de récursion est O(n) où petit n est la quantité d'éléments restants. Le seul problème est qu'en pratique, c'est plus lent qu'un tri rapide quand il y a peu de doublons, c'est-à-dire beaucoup de collisions. Cependant, lorsqu'il y a une grande quantité de doublons, il est étonnamment rapide.
Edit : Dans les implémentations actuelles de D, hash_t est de 32 bits. Tout ce qui concerne cet algorithme suppose qu'il y aura très peu, voire aucune, collision de hachage dans un espace complet de 32 bits. Les collisions peuvent, cependant, se produire fréquemment dans l'espace modulo. Cependant, cette hypothèse sera vraisemblablement vraie pour tout ensemble de données de taille raisonnable. Si la clé est inférieure ou égale à 32 bits, elle peut être son propre hachage, ce qui signifie qu'une collision dans l'espace 32 bits complet est impossible. Si elle est plus grande, on ne peut tout simplement pas en placer suffisamment dans l'espace d'adressage de la mémoire 32 bits pour que cela pose un problème. Je suppose que hash_t sera augmenté à 64 bits dans les implémentations 64 bits de D, où les ensembles de données peuvent être plus grands. De plus, si cela s'avérait être un problème, on pourrait changer la fonction de hachage à chaque niveau de récursion.
Voici une implémentation dans le langage de programmation 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);
}
