¿Cómo calcular la mediana de un mapa <Int,Int>?

Question

Para un mapa donde la clave representa una cantidad de una secuencia y el valor de la cuenta con qué frecuencia apareció este número en la secuencia, ¿cómo se vería una implementación de un algoritmo en Java para calcular la mediana?

Por ejemplo:

1,1,2,2,2,2,3,3,3,4,5,6,6,6,7,7 

en un mapa:

Map<Int,Int> map = ... 
map.put(1,2) 
map.put(2,4) 
map.put(3,3) 
map.put(4,1) 
map.put(5,1) 
map.put(6,3) 
map.put(7,2) 

double median = calculateMedian(map); 
print(median); 

resultaría en:

> print(median); 
3 
> 

Así que lo que estoy buscando es una aplicación java de calculateMedian.

Answer 1

• Utilice un SortedMap, es decir, un TreeMap
• Iterar a través del mapa una vez para calcular el número total de elementos, es decir, la suma de todas las ocurrencias
• Iterar de nuevo y se suman las ocurrencias hasta que haya alcanzado la mitad del total. El número que causó la suma exceda de la mitad del total es la mediana
• prueba ampliamente para off-by-one errores

Answer 2

Para fácil, pero en el algoritmo tal vez no tan eficiente que lo haría como esto:

1. expanda el mapa a una lista.

prácticamente hablado: itere por el mapa y agregue la clave 'valor-tiempos' a la nueva lista. Finalmente clasifique la lista.

//... 
List<Integer> field = new ArrayList<Integer>(); 
for (Integer key:map) { 
    for (int i = 0; i < map.get(key); i++) { 
    field.add(key); 
    } 
} 
Collections.sort(field); 

2. Calcular la mediana

Ahora usted tiene que poner en práctica un método int calculateMedian(List<Integer> sorted). Esto depende del tipo de mediana que necesita. Si solo se trata de la mediana de muestra, el resultado es el valor más intermedio (para listas con un número impar de elementos) o el promedio de los dos valores más bajos (para listas con una longitud igual). Tenga en cuenta que la lista debe ser ordenada.

(Ref: Sample Median/wikipedia)

---

bien, está bien, a pesar de que Chris no mencionó eficiencia, aquí está una idea de cómo calcular la mediana de la muestra sin ampliar el mapa ...

(!)

Set<Integer> sortedKeys = new TreeSet<Integer>(map.keySet()); // just to be sure ;) 
Integer median = null; // Using Integer to have a 'invalid/not found/etc' state 
int total = 0; 
for (Integer key:sortedKeys) { 
    total += map.get(key); 
} 
if (isOddNumber(total)) { // I don't have to implement everything, do I? 
    int counter = total/2; // index starting with 0 
    for (Integer key:sortedKeys) { 
    middleMost -= map.get(key); 
    if (counter < 0) { 
     // the sample median was in the previous bin 
     break; 
    } 
    median = key; 
    } 
} else { 
    int lower = total/2; 
    int upper = lower + 1; 
    for (Integer key:sortedKeys) { 
    lower -= map.get(key); 
    upper -= map.get(key); 
    if (lower < 0 && upper < 0) { 
     // both middlemost values are in the same bin 
     break; 
    } else (lower < 0 || upper < 0) { 
     // lower is in the previous, upper in the actual bin 
     median = (median + key)/2; // now we need the average 
     break; 
    } 
    median = key; 
    } 
} 

(no tengo a la mano compilador - si tiene que muchos errores de sintaxis, lo tratan como pseudo código, por favor;)) tiempo de

Answer 3

lineal

Si conoce el total de los números (en su caso es 16) puede ir desde el principio o el final del mapa y sumar los conteos hasta llegar al elemento redondo (n/2) th , o en caso de que la suma llegue a la media del piso (n/2) th y ceil (n/2) th elementos = median.

Si no conoce el recuento total, tendrá que pasar por todas ellas al menos una vez.

tiempo sublineal

Si usted puede decidir sobre la estructura de datos y puede hacer pre-procesamiento Véase Wikipedia sobre selection algorithm y puede obtener incluso algoritmo sublinear. También puede obtener tiempo sublineal si conoce algo acerca de la distribución de los datos.

EDIT: Así que bajo el supuesto de que tenemos una secuencia con un recuento de lo que podemos hacer es

• mientras se insertan los key -> count pares mantienen otro mapa - key -> running_total
• esta manera usted tendrá una estructura en la que usted podrá obtener total_count mirando la última clave de running_total
• y podrá realizar una búsqueda binaria para localizar el elemento donde el total acumulado está cerca de total_count/2

Esto duplicará el uso de la memoria, pero dará el rendimiento O (log n) para la mediana y O (1) para total_count.

Answer 4

Usando Guava:

Multiset<Integer> values = TreeMultiset.create(); 
Collections.addAll(values, 1,1,2,2,2,2,3,3,3,4,5,6,6,6,7,7); 

Ahora la respuesta a su pregunta es:

return Iterables.get(values, (values.size() - 1)/2); 

realmente. Eso es. (O comprobar si el tamaño es uniforme y promedie los dos valores centrales, para ser precisos al respecto.)

Si los recuentos son particularmente grandes, sería más rápido utilizar el conjunto múltiple de entrySet y guardar una suma continua, pero la La forma más simple generalmente está bien.