Hace tres días, pensé en combinar el conteo y la clasificación de árboles. Después de discutirlo con un colega, llegamos a la siguiente decisión: usar HashMap en lugar de TreeSet (qué tiene que ver TreeSet con eso, puede ver a continuación). Pero incluso esto me pareció un poco, así que decidí implementar mi propia tabla hash y ver qué sucedía. Los resultados me parecieron bastante interesantes.
Los tres tipos de clasificación son excelentes para los casos en que el poder de muchos elementos únicos en la matriz es relativamente pequeño (lo que significa esto quedará claro después de que analicemos los resultados de la prueba).
Conde de árboles Ordenar
Construimos el árbol de Steam (Clave, Cantidad), donde la Clave es responsable del elemento de la matriz, y la Cantidad es el número de repeticiones de este elemento de la matriz. El árbol es naturalmente equilibrado, negro y rojo, por ejemplo.
Además, todo es lógico. Agregamos todos los elementos de la matriz al par y buscamos el par en el árbol (para evitar volver a crear los objetos, utilizamos el par creado previamente, desde el cual cambiamos la clave. Aquí no estamos interesados en el número, ya que estamos buscando una coincidencia solo con la clave). Si dicha clave ya existe, aumente la cantidad, de lo contrario agregue un nuevo par (clave, 1).
Reescribimos la matriz, eliminamos el vértice cada vez y escribimos la Clave tantas veces como su Número.
Para no implementar el árbol en sí, para el algoritmo descrito utilicé TreeSet, que funciona en un árbol negro-rojo.
Usando HashMap
Almacenaremos el elemento de matriz como la clave y el número de repeticiones como el valor de la clave.
Usando mi propia tabla hash
Decidí recurrir al método de direccionamiento abierto. En la tabla hash, almacenamos objetos de la clase Pair, donde primero es la clave, segundo es el número de repeticiones. Naturalmente, se agregó un constructor que toma el tamaño inicial de la tabla y el factor de carga. La función hash es la más simple: tomamos el módulo de clave, en el caso de acceso repetido, agregamos uno (la unidad funciona bien porque la matriz de claves es la más ordenada, y al final tendremos que clasificar todas las claves con clasificación rápida estándar, porque en la tabla pueden resultar desordenadas ) Entonces podemos decir que esta es una combinación de hashing y otro tipo.
Colisiones
Obviamente, pueden ocurrir colisiones y esto afectará gravemente tanto el tiempo de determinación del hash como la velocidad de clasificación del conjunto resultante de hashes (los datos ordenados o casi ordenados se ordenan más rápido). Pero aquí está la cosa: nuestro hash ff cambia a medida que la tabla se expande. Por lo tanto, seleccionar tales datos específicamente se vuelve mucho más difícil. Además, es posible hacer que el factor de carga y el coeficiente de expansión sean aleatorios (en un cierto rango, por supuesto), lo que hará imposible preseleccionar los valores que conducen a colisiones. Bueno, si en una tabla algunos datos condujeron a colisiones, luego de volver a hacer hash, el número de colisiones puede reducirse significativamente (varias veces). El punto débil será factoriales de números, pero son increíblemente pequeños (hasta 2 ^ 31, por ejemplo, solo hay 11 de ellos (excluyendo 0)).
Los hash criptográficos no son adecuados para nosotros, y porque con ellos puedes olvidarte de una matriz de hashes casi ordenada (en el sentido de ordenar por teclas).
Tiempo de trabajo
Tipo de conteo de árboles: en el peor de los casos, para O (n log n), en el mejor de los casos, para tiempo lineal.
Clasificación de la tabla hash: tiempo de hash + complejidad de ordenar la matriz hash (puede variar según el algoritmo y la implementación elegidos, por lo que no indicaré nada aquí). Estimar la complejidad es difícil debido al uso de una función hash y varios enfoques posibles para clasificar hash. Esta pregunta necesita investigación adicional, pero es obvio que en el peor de los casos (cuando los datos de entrada se correspondan intencionalmente con una función hash específica en una etapa particular de ejecución), el tiempo operativo será O (n ^ 2).
¿Qué de memoria?
La ordenación del recuento de árboles requerirá O (distinta (n)) memoria adicional
Para una tabla hash, necesitamos O (memoria distinta (n)) + memoria para ordenar los hash (según el algoritmo seleccionado).
Aquí están los resultados en milisegundos que obtuve en números aleatorios al ordenar una matriz de objetos en 10 millones de elts, con un rango de valores [0; x]:
En las pruebas, factor de carga en mi tabla hash = 0.75, capacidad inicial = 20, la tabla se duplica cada vez
Para x = 10:
2044 - integrado
285 - recuento de árboles (clasificación de Usatov)
276 - HashMap (tipo Usatov-Prokurat)
140 - con mi tabla hash (clasificación Usatov-Prokurat usando MyHashTable)
x = 100:
2406 - incorporado
455 - árbol de conteo
283 - HashMap
134 - tabla hash
x = 1_000:
2171 - integrado
930 - árbol de conteo
380 - HashMap
209 - tabla hash
x = 10_000
2879 - integrado
1666 - árbol de conteo
634 - HashMap
326 - tabla hash
x = 100_000
4045 - integrado
2899 - árbol de conteo
866 - HashMap
762 - tabla hash
x = 1_000_000
4997 - integrado
5762 - árbol de conteo
2505- HashMap
1294 - tabla hash
x = 10_000_000
5083 - integrado
11480 - árbol de conteo
5099 - HashMap
3240 - tabla hash
Como dije al principio, estas clasificaciones son más adecuadas para aquellos casos en que la potencia de muchos elementos de la matriz es suficientemente pequeña en relación con el tamaño de la matriz.
También vale la pena señalar que la clasificación integrada funciona mucho más rápido en datos ordenados (casi ordenados) (o una matriz en el orden inverso), pero mi método lo hace más rápido en números aleatorios.
Clasificación del conteo de árboles:
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)
Ordenar a través de 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; }
Ordenar a través de mi tabla 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; }
Implementación de la tabla 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++; } } }
Clase de vapor:
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; } }