Números que se repiten con mayor frecuencia en una enorme lista de números

Question

Tengo un archivo que tiene un número entero aleatorio (alrededor de un millón), cada uno separado por un espacio en blanco. Necesito encontrar los 10 números más frecuentes en ese archivo. ¿Cuál es la forma más eficiente de hacer esto en Java? Puedo pensar en 1. Crea un mapa hash, la clave es el número entero del archivo y el valor es el recuento. Para cada número en el archivo, compruebe si esa clave ya existe en el mapa hash, en caso afirmativo, valor ++, sino haga una nueva entrada en hash 2. Haga una BST, cada nodo es el número entero del archivo. Para cada entero del archivo, vea si hay un nodo en la BST si es así, haga value ++, el valor es parte del nodo.

Creo que el mapa de hash es la mejor opción si se me ocurre una buena función hash, ¿Puede alguien sugerirme cuál es el mejor modo de hacerlo? ¿Hay algún otro algo eficiente que pueda usar?

Answer 1

Controles de Java hashing. No necesita escribir una función hash. Solo comienza a empujar cosas en el mapa hash.

Además, si esto es algo que solo necesita ejecutarse una vez (o solo ocasionalmente), entonces no optimice ambos. Será lo suficientemente rápido. Solo molesta si es algo que se ejecutará dentro de una aplicación.

Answer 2

Edición # 2:

bien, lo arruiné mi primera regla - Nunca optimizar prematuramente. El peor caso para esto es probablemente el uso de un HashMap estándar con un amplio rango, así que simplemente lo hice. Todavía funciona en un segundo, así que olvídate de todo lo demás aquí y hazlo.

Y me haré OTRA NOTA para SIEMPRE probar la velocidad antes de preocuparme por las implementaciones complicadas.

(continuación se muestra antigua Página obsoleta que todavía podría ser válida si alguien tenía más puntos de más que un millón)

Un HashSet quiere trabajar, pero si sus números enteros tienen un rango razonable (por ejemplo, 1-1000), Sería más eficiente crear una matriz de 1000 enteros, y para cada uno de sus millones de enteros, incrementar ese elemento de la matriz. (Más o menos la misma idea que un HashMap, pero la optimización de algunas de las incógnitas que un Hash tiene que tener en cuenta debería hacer que sea un poco más rápido).

También podría crear un árbol. Cada nodo en el árbol contendría (valor, conteo) y el árbol estaría organizado por valor (valores más bajos a la izquierda, más arriba a la derecha). Atraviese su nodo, si no existe, insértelo, si lo hace, simplemente incremente el conteo.

El rango y la distribución de sus valores determinaría cuál de estos dos (o un hash regular) funcionaría mejor. Creo que un hash regular no tendría muchos casos "ganadores" (Tendría que ser un rango amplio y datos "agrupados", e incluso entonces el árbol podría ganar.

Dado que esto es bastante trivial - I recomiendo que implementar más de una velocidad de la solución y test contra el conjunto de datos real

Editar:. RE el comentario

TreeMap iba a funcionar, pero aún así añadir una capa de direccionamiento indirecto (y es tan increíblemente fácil y divertido impleméntese usted mismo). Si utiliza la implementación de stock, debe usar enteros y convertir constantemente hacia y desde int para cada incremento. Existe la indirección del puntero al entero y el hecho de que está almacenando en al menos 2x tantos objetos. Esto ni siquiera cuenta gastos generales para las llamadas a métodos, ya que deben incluirse con un poco de suerte.

Normalmente esto sería una optimización (mal), pero cuando comienzas a acercarte a cientos de miles de nodos, ocasionalmente tienes que garantizar la eficiencia, por lo que el TreeMap incorporado será ineficiente por las mismas razones que HashSet incorporado lo hará.

Answer 3

¿Por qué usar una tabla hash? Simplemente use una matriz que tenga el mismo tamaño que el rango de sus números. Entonces no pierdas el tiempo ejecutando la función hash. Luego ordena los valores una vez que hayas terminado. O (N log N)

Answer 4

Ésta es la fuente para java.lang.Integer.hashCode(), que es la función hash que se utilizará si almacena sus ingresos como una HashMap<Integer, Integer>:

public int hashCode() { 
return value; 
} 

Así, en otras palabras, el (por defecto el valor hash de java.lang.Integer es el entero en sí.

¿Qué es más eficiente que eso?

Answer 5

1. asignar una matriz/vector del mismo tamaño que el número de elementos de entrada que tiene
2. rellenar la matriz de su archivo con los números, un número por elemento
3. Ponga la lista en orden
4. Itera a través de la lista y realiza un seguimiento de las 10 principales series de números que has encontrado.
5. Imprime las diez mejores ejecuciones al final.

Como refinamiento en el paso 4, solo necesita dar un paso adelante en la matriz en pasos equivalentes a la décima carrera más larga. Cualquier ejecución más larga que eso se superpondrá con su muestreo. Si la décima carrera más larga tiene 100 elementos de longitud, solo necesita muestrear los elementos 100, 200, 300 y en cada punto contar la carrera del número entero que encuentre allí (tanto hacia adelante como hacia atrás). Cualquier carrera más larga que su décima más larga se superpondrá con su muestreo.

Debe aplicar esta optimización después de que su décima longitud de ejecución sea muy larga en comparación con otras ejecuciones en la matriz.

Un mapa es excesivo para esta pregunta a menos que tenga muy pocos números únicos cada uno con una gran cantidad de repeticiones.

NB: Similar a la respuesta de gshauger pero concretarse

Answer 6

Si usted tiene que hacer que sea lo más eficiente posible, utilizar una matriz de enteros, con la posición que representa el valor y el contenido que representa el recuento. De esta forma evitará el autoboxing y el unboxing, el asesino más probable de una colección Java estándar.

Si el rango de números es demasiado grande, eche un vistazo a las implementaciones de PJC y sus IntKeyIntMap. También evitará el autoboxing. Sin embargo, no sé si será lo suficientemente rápido para ti.

Answer 7

La forma correcta de hacerlo es con una lista vinculada. Cuando inserta un elemento, baja por la lista vinculada, si está allí aumenta el recuento de nodos; de lo contrario, cree un nuevo nodo con recuento de 1. Después de insertar cada elemento, tendría una lista ordenada de elementos en O (n * log (n)).

Para sus métodos, usted está haciendo n inserciones y luego ordenando en O (n * log (n)), por lo que su coeficiente en la complejidad es mayor.

Answer 8

Si el rango de números es pequeño (por ejemplo, 0-1000), use una matriz. De lo contrario, use un HashMap<Integer, int[]>, donde los valores son todas las matrices de longitud 1. Debería ser mucho más rápido incrementar un valor en una matriz de elementos primitivos que crear un nuevo entero cada vez que desee incrementar un valor. Aún estás creando objetos enteros para las claves, pero eso es difícil de evitar. No es factible crear una matriz de 2^31-1 ints, después de todo.

Si toda la entrada está normalizada, por lo que no tiene valores como 01 en lugar de 1, use cadenas como teclas en el mapa para no tener que crear claves enteras.

Answer 9

HashMap

Un millón de números enteros no es realmente mucho, incluso para los lenguajes interpretados, pero sobre todo para un lenguaje como Java rápida. Probablemente apenas notará el tiempo de ejecución. Intentaré esto primero y pasaré a algo más complicado si lo consideras demasiado lento.

Probablemente tomará más tiempo dividir y analizar cadenas para convertir a enteros que incluso el algoritmo más simple para encontrar frecuencias usando un HashMap.

Answer 10

Utilice un HashMap para crear su conjunto de datos (pares de valores) en la memoria mientras recorre el archivo. HashMap debería darle acceso cercano a O (1) a los elementos mientras crea el conjunto de datos (técnicamente, en el peor de los casos, HashMap es O (n)). Una vez que haya terminado de buscar el archivo, use Collections.sort() en el valor Collection devuelto por HashMap.values ​​() para crear una lista ordenada de pares de valores. Usar Collections.sort() está garantizado O (nLogn). Por ejemplo:

public static class Count implements Comparable<Count> { 
    int value; 
    int count; 
    public Count(int value) { 
     this.value = value; 
     this.count = 1; 
    } 
    public void increment() { 
     count++; 
    } 
    public int compareTo(Count other) { 
     return other.count - count; 
    } 
} 

public static void main(String args[]) throws Exception { 
    Scanner input = new Scanner(new FileInputStream(new File("..."))); 
    HashMap<Integer, Count> dataset = new HashMap<Integer, Count>(); 
    while (input.hasNextInt()) { 
     int tempInt = input.nextInt(); 
     Count tempCount = dataset.get(tempInt); 
     if (tempCount != null) { 
      tempCount.increment(); 
     } else { 
      dataset.put(tempInt, new Count(tempInt)); 
     } 
    } 

    List<Count> counts = new ArrayList<Count>(dataset.values()); 
    Collections.sort(counts); 

Answer 11

En realidad, no es un O (n) algoritmo para hacer exactamente lo que quiere hacer. Su caso de uso es similar a un caché LFU donde el conteo de acceso del elemento determina si se sincroniza en el caché o si se desaloja de él.

http://dhruvbird.blogspot.com/2009/11/o1-approach-to-lfu-page-replacement.html