Il y a trois jours, j'ai pensé à combiner le comptage et le tri des arbres. Après en avoir discuté avec un collègue, nous sommes arrivés à la décision suivante: utiliser HashMap au lieu de TreeSet (qu'est-ce que TreeSet a à voir avec cela, vous pouvez voir ci-dessous). Mais même cela m'a semblé un peu, alors j'ai décidé d'implémenter ma propre table de hachage et de voir ce qui en est ressorti. Les résultats m'ont paru assez intéressants.
Les trois types de tri sont parfaits dans les cas où la puissance de nombreux éléments uniques dans le tableau est relativement faible (ce que cela signifie deviendra clair après avoir examiné les résultats du test).
Tri du nombre d'arbres
Nous construisons l'arbre Steam (clé, quantité), où la clé est responsable de l'élément de tableau, et la quantité est le nombre de répétitions de cet élément de tableau. L'arbre est naturellement équilibré, noir et rouge par exemple.
De plus, tout est logique. Nous ajoutons tous les éléments du tableau à la paire et recherchons la paire dans l'arborescence (pour éviter de recréer les objets, nous utilisons la paire précédemment créée, à partir de laquelle nous modifions la clé. Ici, nous ne sommes pas intéressés par le nombre, car nous ne recherchons une correspondance que par la clé). Si une telle clé existe déjà, augmentez la quantité, sinon ajoutez une nouvelle paire (clé, 1).
Nous réécrivons le tableau, en supprimant le sommet à chaque fois et en notant la clé autant de fois que son nombre.
Afin de ne pas implémenter l'arbre lui-même, pour l'algorithme décrit, j'ai utilisé TreeSet, qui fonctionne sur un arbre noir-rouge.
Utilisation de HashMap
Nous allons stocker l'élément de tableau comme clé et le nombre de répétitions comme valeur de clé.
Utiliser ma propre table de hachage
J'ai décidé de recourir à la méthode d'adressage ouvert. Dans la table de hachage, nous stockons les objets de la classe Pair, où le premier est la clé, le deuxième le nombre de répétitions. Naturellement, un constructeur a été ajouté qui prend la taille initiale de la table et le facteur de charge. La fonction de hachage est la plus simple: nous prenons la clé modulo, dans le cas d'un accès répété, ajoutez-en une (l'unité fonctionne bien dans la mesure où le tableau de clés est le plus ordonné, et à la fin nous devrons trier toutes les clés avec un tri rapide standard, car dans le tableau elles peuvent s'avérer non ordonnées ) Nous pouvons donc dire qu'il s'agit d'une combinaison de hachage et d'un autre type.
Collisions
De toute évidence, des collisions peuvent se produire et cela affectera gravement le temps de détermination du hachage et la vitesse de tri du tableau de hachage résultant (les données ordonnées ou presque ordonnées sont triées plus rapidement). Mais voici la chose: notre hachage ff change à mesure que la table se développe. Il est donc beaucoup plus difficile de sélectionner spécifiquement ces données. De plus, il est possible de rendre le facteur de charge et le coefficient d'expansion aléatoires (dans une certaine plage, bien sûr), ce qui rendra impossible la présélection des valeurs qui conduisent à des collisions. Eh bien, si dans un tableau certaines données ont conduit à des collisions, après le re-hachage, le nombre de collisions peut être considérablement réduit (plusieurs fois). Le point faible sera la factorielle des nombres, mais ils sont incroyablement petits (jusqu'à 2 ^ 31, par exemple, il n'y en a que 11 (hors 0)).
Les hachages cryptographiques ne nous conviennent pas, et parce qu'avec eux, vous pouvez oublier un tableau de hachages presque ordonné (dans le sens de la commande par clés).
Temps de travail
Tri par comptage: dans le pire des cas, pour O (n log n), au mieux, pour un temps linéaire.
Tri de table de hachage: temps de hachage + complexité du tri du tableau de hachage (peut varier en fonction de l'algorithme et de l'implémentation choisis, donc je n'indiquerai rien ici). L'estimation de la complexité est difficile en raison de l'utilisation d'une fonction de hachage et de diverses approches possibles pour trier les hachages. Cette question nécessite des recherches supplémentaires, mais il est évident que dans le pire des cas (lorsque les données d'entrée seront intentionnellement mises en correspondance avec une fonction de hachage spécifique à un stade particulier de l'exécution), le temps de fonctionnement sera O (n ^ 2).
Et de mémoire?
Le tri du nombre d'arbres nécessite O (mémoire distincte (n)) supplémentaire
Pour une table de hachage, nous avons besoin d'une mémoire O (distincte (n)) + mémoire pour trier les hachages (selon l'algorithme sélectionné).
Voici les résultats en millisecondes que j'ai obtenus sur des nombres aléatoires lors du tri d'un tableau d'objets en 10 millions d'elfes, avec une plage de valeurs [0; x]:
Lors des tests, facteur de charge dans ma table de hachage = 0,75, capacité initiale = 20, la table est doublée à chaque fois
Pour x = 10:
2044 - intégré
285 - nombre d'arbres (tri Usatov)
276 - HashMap (type Usatov-Prokurat)
140 - avec ma table de hachage (tri Usatov-Prokurat utilisant MyHashTable)
x = 100:
2406 - intégré
455 - arbre de comptage
283 - HashMap
134 - table de hachage
x = 1_000:
2171 - intégré
930 - arbre de comptage
380 - HashMap
209 - table de hachage
x = 10_000
2879 - intégré
1666 - arbre de comptage
634 - HashMap
326 - table de hachage
x = 100_000
4045 - intégré
2899 - arbre de comptage
866 - HashMap
762 - table de hachage
x = 1_000_000
4997 - intégré
5762 - arbre de comptage
2505- HashMap
1294 - table de hachage
x = 10_000_000
5083 - intégré
11480 - arbre de comptage
5099 - HashMap
3240 - table de hachage
Comme je l'ai dit au début, ces tris conviennent mieux aux cas où la puissance de nombreux éléments du tableau est suffisamment petite par rapport à la taille du tableau.
Il convient également de noter que le tri intégré fonctionne beaucoup plus rapidement sur les données ordonnées (presque ordonnées) (ou un tableau dans l'ordre inverse), mais ma méthode le fait plus rapidement sur les nombres aléatoires.
Tri du nombre d'arbres:
static void usatovSort(Integer[] arr) { TreeSet<MyPair> tree = new TreeSet<>(); MyPair temp; MyPair mp = new MyPair(); for (int i : arr) { temp = mp; temp.first = i; temp = tree.ceiling(temp); if (temp != null && temp.first == i)
Trier via HashMap:
static void usatovProkuratSortUsingHashMap(Integer[] arr) { HashMap<Integer, Integer> hm = new HashMap<>(); Integer temp; for (Integer i : arr) { temp = hm.get(i); if (temp == null) hm.put(i, 1); else hm.put(i, temp + 1); } ArrayList<Integer> keys = new ArrayList<>(hm.keySet().size()); keys.addAll(hm.keySet()); keys.sort(Comparator.naturalOrder()); int ptr = 0; for (Integer i : keys) for (int j = 0; j < hm.get(i); j++) arr[ptr++] = i; }
Trier ma table de hachage:
static void usatovProkuratSortUsingMyHashTable(Integer[] arr) { MyHashTable mht = new MyHashTable(); for (Integer i : arr) mht.add(i); MyPair[] res = mht.getPairs(); int ptr = 0; Arrays.sort(res, Comparator.comparingInt(o -> o.first)); for (MyPair mp : res) for (int i = 0; i < mp.second; i++) arr[ptr++] = mp.first; }
Implémentation de la table de hachage:
public class MyHashTable { private MyPair[] hashArr; private double count = 0; private double loadFactor = 0.5; private double expansivity = 2; private static final int DEFAULT_CAPACITY = 20; public MyHashTable() { hashArr = new MyPair[DEFAULT_CAPACITY]; } public MyHashTable(double loadFactor) { hashArr = new MyPair[DEFAULT_CAPACITY]; this.loadFactor = loadFactor; } public MyHashTable(int capacity) { hashArr = new MyPair[capacity]; } public MyHashTable(int capacity, double loadFactor) { hashArr = new MyPair[capacity]; this.loadFactor = loadFactor; } public MyHashTable(int capacity, double loadFactor, double expansivity) { hashArr = new MyPair[capacity]; this.loadFactor = loadFactor; this.expansivity = expansivity; } public MyPair[] getPairs() { MyPair[] pairs = new MyPair[(int) count]; int ptr = 0; for (MyPair i : hashArr) if (i != null) pairs[ptr++] = i; return pairs; } public MyPair get(int key) { int add = 0; while (true) if (hashArr[(key + add) % hashArr.length].first == key) { return hashArr[(key + add) % hashArr.length]; } else if (add++ == hashArr.length) return null; } public void add(int key) { if (count / hashArr.length >= loadFactor) grow(); int add = 0; while (true) { if (hashArr[(key + add) % hashArr.length] == null) { hashArr[(key + add) % hashArr.length] = new MyPair(key, 1); count++; return; } if (hashArr[(key + add) % hashArr.length].first == key) { hashArr[(key + add) % hashArr.length].second++; return; } add++; } } public void add(MyPair newMP) { if (count / hashArr.length >= loadFactor) grow(); int add = 0; while (true) { if (hashArr[(newMP.first + add) % hashArr.length] == null) { hashArr[(newMP.first + add) % hashArr.length] = newMP; count++; return; } if (hashArr[(newMP.first + add) % hashArr.length].first == newMP.first) { hashArr[(newMP.first + add) % hashArr.length].second += newMP.second; return; } add++; } } private void grow() { MyPair[] oldHash = hashArr; hashArr = new MyPair[(int) (expansivity * hashArr.length)]; for (MyPair i : oldHash) if (i != null) innerAdd(i); } private void innerAdd(MyPair mp) { int add = 0; while (true) { if (hashArr[(mp.first + add) % hashArr.length] == null) { hashArr[(mp.first + add) % hashArr.length] = mp; return; } if (hashArr[(mp.first + add) % hashArr.length].first == mp.first) { hashArr[(mp.first + add) % hashArr.length].second += mp.second; return; } add++; } } }
Classe Steam:
public class MyPair implements Comparable<MyPair> { public int first; public int second; public MyPair() { } public MyPair(int first, int second) { this.first = first; this.second = second; } @Override public int compareTo(MyPair o) { return first - o.first; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MyPair myPair = (MyPair) o; return first == myPair.first; } @Override public int hashCode() { return first; } }