¿Cómo contar en tiempo lineal el peor de los casos?

8

Esta pregunta y esta pregunta me hicieron pensar un poco. Para ordenar una matriz de longitud con elementos únicos en , necesitamos poder almacenar conteos de valores en la matriz. Hay algunas sugerencias, pero estoy buscando una manera de hacerlo en el peor de los casos, el tiempo lineal. Más específicamente:nkO(n+klogk)

Dada una lista A de n elementos con k elementos distintos, determinar una lista de tuplas U={(xi,ci)}k de todos los elementos únicos xiA tal que ci es el recuento de elemento xi en A .

Aquí hay algunas ideas (fallidas) que he tenido y que me han sugerido:

  1. Árbol de búsqueda binaria equilibrado : con esto se necesitará O(logk) para insertar en el árbol y aumentar los valores. Después de las inserciones podríamos hacer un recorrido del árbol en O(k) . Por lo tanto, el tiempo total sale a O(nlogk) que es demasiado lento.
  2. Hash Map : con esto podemos obtener O(1) inserciones esperadas y, por lo tanto, O(n) tiempo esperado . Sin embargo, esto todavía no es O(n) peor de los casos.
  3. Vaciar el mapeo espacial - Encontrar el mínimo y el máximo elemento en A . Asigne (pero no inicialice) suficiente memoria para cubrir este rango. Utilice esta memoria básicamente como un mapa hash e incluya un hash aleatorio para que no intentemos acceder a la memoria corrupta. Esta estrategia presenta problemas. (1) Es probabilístico con muy, muy baja probabilidad de falla, pero aún no está garantizado. Usar memoria como esta nos limita a las restricciones de punto flotante o entero.
  4. Matrices asociativas : hay muchas otras matrices asociativas que se pueden utilizar, de forma similar a los mapas hash y BST, pero no encuentro ninguna que coincida con estas restricciones.

Tal vez hay un método obvio que me falta, pero también creo que podría no ser posible. ¿Cuáles son tus pensamientos?

Ryan
fuente
3
No se puede hacer en el modelo de comparación ya que el problema de la distinción de elementos tiene un límite inferior de la complejidad del árbol de decisión . Ω(nlogn)
John L.
@ Apass.Jack, oh cierto, eso es correcto. Una reducción trivial que no consideré. Si lo escribe como una respuesta rápida, lo acepto.
ryan
¿Por qué el HashMap no está asegurado O (n) amortizado ?
javadba
1
@javadba Por ejemplo, supongamos que todos los elementos se combinan con el mismo valor.
John L.
Ah ok así que si es un hashing imperfecto.
javadba

Respuestas:

6

Esta es una buena pregunta.

En el modelo de comparación o, lo que es más general, el modelo de árbol de decisión algebraico, el problema de la distinción de elementos tiene un límite inferior de complejidad de tiempo en el peor de los casos, como se dice en este artículo de Wikipedia . Por lo tanto, no existe un algoritmo para contar elementos distintos en tiempo lineal en el peor de los casos, incluso sin contar las duplicidades.Θ(nlogn)

Sin embargo, no está claro si se puede hacer en otro modelo computacional. Parece poco probable en cualquier modelo computacional determinista razonable.

John L.
fuente
¿Es realmente una instancia del problema de distinción de elementos? Solo generar las tuplas no requiere la verificación de la distinción. No estoy en desacuerdo, solo curioso.
mascoj
2
Lo que digo es que si puede producir esa tupla de elementos distintos, también puede resolver el problema de la distinción de elementos comprobando si el tamaño de la tupla es . n
John L.
Buena llamada. Gracias
mascoj
1

Existen algoritmos aleatorios cuyo tiempo de ejecución esperado es ; o donde la probabilidad de que el tiempo de ejecución tarde más que es exponencialmente pequeña en .O(n)cnc

En particular, elija aleatoriamente una función hash universal 2, luego úsela para hash todos los elementos de la matriz. Esto logra los tiempos de ejecución establecidos, si elige la longitud de la salida del hash 2-universal adecuadamente.

Como otro ejemplo, puede construir un algoritmo aleatorio cuyo peor tiempo de ejecución es (siempre se ejecuta en tiempo lineal, sin importar qué) y tiene una probabilidad de error de como máximo . (¿Cómo? Ejecute el algoritmo anterior y termínelo si se ejecuta más de pasos para algunos elegidos apropiadamente .) En la práctica, eso es lo suficientemente bueno, ya que la probabilidad de que su computadora muestre la respuesta incorrecta debido a un rayo cósmico ya es mucho mayor que .O(n)1/2100cnc1/2100

DW
fuente
1

Su enfoque 3 puede ser seguro utilizando una solución para el ejercicio 2.12 de Aho, Hopcroft y Ullman (1974) El diseño y análisis de algoritmos informáticos como se describe, por ejemplo, en Uso de memoria no inicializada para diversión y beneficio .

Básicamente, además de su conjunto de N elementos con los recuentos, tiene dos conjuntos de N elementos y un recuento auxiliar para crear un conjunto disperso que indica cuáles de los recuentos son válidos.

En pseudocódigo tipo C:

uint* a = malloc(n);
uint* b = malloc(n);
uint* c = malloc(n);
uint len = 0;

get_count(uint x) {
    uint idx = a[x];
    return idx >= 0 && idx < len && b[idx] == x ? c[idx] : 0;
}

increment_count(uint x) {
    uint idx = a[x];
    if (idx < 0 || idx >= len || b[idx] != x) {
        idx = len;
        len++;
        a[x] = idx;
        b[idx] = x;
        c[idx] = 0;
    }
    c[idx]++;
}

La implementación práctica del conjunto disperso se analiza en esta respuesta de StackOverflow .

Peter Taylor
fuente
PS cpodría indexarse ​​en xo idx, pero lo usé idxpara una mejor localidad de caché.
Peter Taylor
Me gusta la respuesta, pero estoy confundido acerca de lo que hace que esto sea seguro. Si bien, completamente improbable, no podría acceder a una celda de memoria, que por algún milagro tiene una entrada "válida" aunque nunca se haya colocado allí. Si acabas de tener mala suerte con malloc?
Ryan
1
Esta solución solo funciona si tiene una memoria lo suficientemente grande: si todos los elementos de la matriz están en el rango , entonces necesita memoria de tamaño al menos . En la práctica esto es muy limitante. La forma en que creamos un gran espacio de direcciones virtuales en la práctica es mediante el uso de tablas de páginas, que son una estructura de datos basada en árboles; el hardware sigue invisiblemente tablas de páginas para nosotros. Como resultado, si bien consideramos que el acceso a la memoria toma tiempo , si está trabajando en un espacio de direcciones de memoria grande, cada acceso a la memoria en realidad toma tiempo logarítmico (para atravesar la estructura de árbol de la tabla de páginas). 1..uuO(1)
DW
@ryan, visite research.swtch.com/sparse para saber qué lo hace seguro. Definitivamente es un truco muy inteligente.
DW
@DW, , pero si es muy grande, puede hacerlo en varios niveles, utilizando una matriz de estructuras en lugar de una matriz de recuentos. Por ejemplo, si usa la raíz 512 para que cada una de las matrices quepa en una página (con punteros de 8 bytes), puede ir hasta usando como máximo memoria donde es el número de elementos distintos vistos. 3u+1u{a,b,c,len}cu=5123=134217728(3×512+1)(1+2k)k
Peter Taylor