Há três dias, pensei em combinar contagem e classificação de árvores. Depois de discutir com um colega, tomamos a seguinte decisão: use o HashMap em vez do TreeSet (o que o TreeSet tem a ver com isso, você pode ver abaixo). Mas mesmo isso me pareceu um pouco, então decidi implementar minha própria tabela de hash e ver o que resultou dela. Os resultados pareciam bastante interessantes para mim.
Todos os três tipos de classificação são ótimos para casos em que o poder de muitos elementos exclusivos da matriz é relativamente pequeno (o que isso significa se tornará claro depois que examinarmos os resultados do teste).
Classificação da contagem de árvores
Construímos a árvore do Steam (Key, Quantity), onde a Key é responsável pelo elemento do array, e Quantity é o número de repetições desse elemento do array. A árvore é naturalmente equilibrada, preta e vermelha, por exemplo.
Além disso, tudo é lógico. Adicionamos todos os elementos da matriz ao Par e procuramos o Par na árvore (para evitar recriar os objetos, usamos o Par criado anteriormente, a partir do qual alteramos a Chave. Aqui não estamos interessados em Número, pois estamos procurando uma correspondência apenas pela Chave). Se essa chave já existir, aumente a quantidade, caso contrário, adicione um novo par (chave, 1).
Reescrevemos a matriz, excluindo o vértice a cada vez e anotando a chave tantas vezes quanto o seu número.
Para não implementar a própria árvore, para o algoritmo descrito, usei o TreeSet, que funciona em uma árvore preto-vermelha.
Usando o HashMap
Armazenaremos o elemento do array como chave e o número de repetições como valor da chave.
Usando minha própria tabela de hash
Decidi recorrer ao método de endereçamento aberto. Na tabela de hash, armazenamos objetos da classe Pair, onde primeiro é a chave e o segundo é o número de repetições. Naturalmente, foi adicionado um construtor que leva o tamanho inicial da tabela e o fator de carga. A função hash é a mais simples: pegamos o módulo de chave, no caso de acesso repetido, adicionamos um (a unidade funciona bem em que a matriz de chaves é a mais ordenada e, no final, teremos que classificar todas as chaves com a classificação rápida padrão, porque na tabela elas podem ficar desordenadas ) Então, podemos dizer que essa é uma combinação de hash e outro tipo.
Colisões
Obviamente, podem ocorrer colisões e isso afetará muito o tempo de determinação do hash e a velocidade de classificação da matriz resultante de hashes (os dados ordenados ou quase ordenados são classificados mais rapidamente). Mas eis o seguinte: nosso hash ff muda à medida que a tabela se expande. Portanto, selecionar esses dados especificamente se torna muito mais difícil. Além disso, é possível tornar o fator de carga e o coeficiente de expansão aleatórios (em um determinado intervalo, é claro), o que tornará impossível pré-selecionar valores que levam a colisões. Bem, se em uma tabela alguns dados levaram a colisões, depois do re-hash, o número de colisões pode ser significativamente reduzido (várias vezes). O ponto fraco será fatorial dos números, mas eles são incrivelmente pequenos (até 2 ^ 31, por exemplo, existem apenas 11 deles (excluindo 0)).
Os hashs criptográficos não são adequados para nós e, com eles, você pode esquecer uma matriz quase ordenada de hashes (no sentido de ordenar por chaves).
Tempo de trabalho
Classificação de contagem de árvores: no pior dos casos, para O (n log n), na melhor das hipóteses, para tempo linear.
Classificação da tabela de hash: tempo de hash + complexidade da classificação da matriz de hash (pode variar dependendo do algoritmo e da implementação escolhidos, por isso não vou indicar nada aqui). É difícil estimar a complexidade devido ao uso de uma função hash e a várias abordagens possíveis para classificar hashes. Essa pergunta precisa de pesquisas adicionais, mas é óbvio que, na pior das hipóteses (quando os dados de entrada serão correspondidos intencionalmente com uma função de hash específica em um estágio específico de execução), o tempo de operação será O (n ^ 2).
O que de memória?
A classificação de contagem de árvores exigirá memória adicional O (distinta (n))
Para uma tabela de hash, precisamos de memória O (distinta (n)) + memória para classificar os hashes (dependendo do algoritmo selecionado).
Aqui estão os resultados em milissegundos que obtive em números aleatórios ao classificar uma matriz de objetos em 10 milhões de elts, com um intervalo de valores [0; x]:
Nos testes, fator de carga na minha tabela de hash = 0,75, capacidade inicial = 20, a tabela é duplicada toda vez
Para x = 10:
2044 - integrado
285 - contagem de árvores (tipo Usatov)
276 - HashMap (classificação Usatov-Prokurat)
140 - com minha tabela de hash (classificação Usatov-Prokurat usando MyHashTable)
x = 100:
2406 - embutido
455 - árvore contadora
283 - HashMap
134 - tabela de hash
x = 1_000:
2171 - integrado
930 - árvore de contagem
380 - HashMap
209 - tabela de hash
x = 10_000
2879 - integrado
1666 - árvore contadora
634 - HashMap
326 - tabela de hash
x = 100_000
4045 - integrado
2899 - árvore de contagem
866 - HashMap
762 - tabela de hash
x = 1_000_000
4997 - integrado
5762 - árvore contadora
2505- HashMap
1294 - tabela de hash
x = 10_000_000
5083 - integrado
11480 - árvore contadora
5099 - HashMap
3240 - tabela de hash
Como eu disse no começo, essas classificações são mais adequadas para os casos em que a potência de muitos elementos da matriz é suficientemente pequena em relação ao tamanho da matriz.
Também é importante notar que a classificação interna funciona muito mais rapidamente em dados ordenados (quase ordenados) (ou em uma matriz na ordem inversa), mas meu método o faz mais rapidamente em números aleatórios.
Classificação da contagem de árvores:
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)
Classificar através do 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; }
Classificar através da minha tabela de hash:
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; }
Implementação da tabela de hash:
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; } }