Obtén 100 números más altos de una lista infinita

A uno de mis amigos se le hizo esta pregunta de entrevista:

"Hay un flujo constante de números que provienen de una lista infinita de números de los cuales necesita mantener una estructura de datos para devolver los 100 números más altos en cualquier momento dado. Suponga que todos los números son números enteros".

Esto es simple, debe mantener una lista ordenada en orden descendente y realizar un seguimiento del número más bajo en esa lista. Si el nuevo número obtenido es mayor que el número más bajo, entonces debe eliminar ese número más bajo e insertar el nuevo número en la lista ordenada según sea necesario.

Entonces la pregunta se extendió:

"¿Puede asegurarse de que la Orden de inserción sea O (1)? ¿Es posible?"

Hasta donde yo sabía, incluso si agrega un nuevo número a la lista y lo ordena de nuevo usando cualquier algoritmo de clasificación, lo mejor sería O (logn) para quicksort (creo). Entonces mi amigo me dijo que no era posible. Pero no estaba convencido, pidió mantener cualquier otra estructura de datos en lugar de una lista.

Pensé en un árbol binario equilibrado, pero incluso allí no obtendrás la inserción con el orden de 1. Así que la misma pregunta que tengo ahora también. Quería saber si existe alguna estructura de datos que pueda realizar la inserción en el orden de 1 para el problema anterior o si no es posible en absoluto.

Digamos que k es el número de números más altos que desea saber (100 en su ejemplo). Luego, puede agregar un nuevo número en el O(k)que también está O(1). Debido O(k*g) = O(g) if k is not zero and constant.

Mantenga la lista sin clasificar. Averiguar si se inserta o no un nuevo número llevará más tiempo, pero la inserción será O (1).

Esto es facil. El tamaño de la lista de constantes, por lo tanto, el tiempo de clasificación de la lista es constante. Se dice que una operación que se ejecuta en tiempo constante es O (1). Por lo tanto, ordenar la lista es O (1) para una lista de tamaño fijo.

Una vez que pase 100 números, el costo máximo en el que incurrirá para el próximo número es el costo para verificar si el número está en los 100 números más altos (etiquetemos ese CheckTime ) más el costo para ingresarlo en ese conjunto y expulsar el el más bajo (llamemos a eso EnterTime ), que es tiempo constante (al menos para números acotados) u O (1) .

Worst = CheckTime + EnterTime

Luego, si la distribución de números es aleatoria, el costo promedio disminuye a medida que tenga más números. Por ejemplo, la posibilidad de que tenga que ingresar el número 101 en el conjunto máximo es 100/101, las posibilidades para el número 1000 serían 1/10, y las posibilidades para el enésimo número serían 100 / n. Por lo tanto, nuestra ecuación para el costo promedio será:

Average = CheckTime + EnterTime / n

Por lo tanto, a medida que n se acerca al infinito, solo CheckTime es importante:

Average = CheckTime

Si los números están vinculados, CheckTime es constante y, por lo tanto, es el tiempo O (1) .

Si los números no están vinculados, el tiempo de verificación aumentará con más números. Teóricamente, esto se debe a que si el número más pequeño en el conjunto máximo es lo suficientemente grande, su tiempo de verificación será mayor porque tendrá que considerar más bits. Eso hace que parezca que será un poco más alto que el tiempo constante. Sin embargo, también podría argumentar que la posibilidad de que el próximo número esté en el conjunto más alto se aproxima a cero cuando n se acerca al infinito y, por lo tanto, la posibilidad de que necesite considerar más bits también se acerca a 0, lo que sería un argumento para O (1) hora.

No soy positivo, pero mi instinto dice que es el momento O (log (log (n))) . Esto se debe a que la probabilidad de que aumente el número más bajo es logarítmica, y la posibilidad de que el número de bits que debe considerar para cada verificación sea también logarítmico. Estoy interesado en que otras personas asuman esto, porque no estoy realmente seguro ...

este es fácil si conoces árboles de montón binarios . Los montones binarios admiten la inserción en tiempo constante promedio, O (1). Y le brinda fácil acceso a los primeros x elementos.

Si por la pregunta que el entrevistador realmente quería preguntar "podemos asegurarnos de que cada número entrante se procese en tiempo constante", entonces, como muchos ya señalaron (por ejemplo, ver la respuesta de @ duedl0r), la solución de su amigo ya es O (1), y Sería así incluso si hubiera usado una lista sin clasificar, o hubiera usado un tipo de burbuja, o cualquier otra cosa. En este caso, la pregunta no tiene mucho sentido, a menos que sea una pregunta difícil o la recuerdes mal.

Supongo que la pregunta del entrevistador fue significativa, que no estaba preguntando cómo hacer que algo sea O (1), lo cual ya es muy obvio.

Porque cuestionar la complejidad del algoritmo solo tiene sentido cuando el tamaño de la entrada crece indefinidamente, y la única entrada que puede crecer aquí es 100: el tamaño de la lista; Supongo que la pregunta real era "¿podemos asegurarnos de que Top N pase O (1) tiempo por número (no O (N) como en la solución de su amigo), ¿es posible?".

Lo primero que viene a la mente es contar el tipo, que comprará la complejidad de O (1) tiempo por número para el problema Top-N por el precio de usar el espacio O (m), donde m es la longitud del rango de números entrantes . Entonces sí, es posible.

Use una cola de prioridad mínima implementada con un montón de Fibonacci , que tiene un tiempo de inserción constante:

1. Insert first 100 elements into PQ
2. loop forever
       n = getNextNumber();
       if n > PQ.findMin() then
           PQ.deleteMin()
           PQ.insert(n)

La tarea es claramente encontrar un algoritmo que sea O (1) en la longitud N de la lista de números requerida. Por lo tanto, no importa si necesita el número 100 superior o 10000 números, el tiempo de inserción debe ser O (1).

El truco aquí es que, aunque ese requisito O (1) se menciona para la inserción de la lista, la pregunta no dice nada sobre el orden del tiempo de búsqueda en el espacio de números enteros, pero resulta que esto puede hacerse O (1) también. La solución entonces es la siguiente:

1. Organice una tabla hash con números para claves y pares de punteros de lista vinculados para valores. Cada par de punteros es el comienzo y el final de una secuencia de lista vinculada. Esto normalmente será solo un elemento y luego el siguiente. Cada elemento en la lista vinculada va al lado del elemento con el siguiente número más alto. Por lo tanto, la lista vinculada contiene la secuencia ordenada de números requeridos. Mantenga un registro del número más bajo.

2. Tome un nuevo número x de la secuencia aleatoria.

3. ¿Es más alto que el último número más bajo registrado? Sí => Paso 4, No => Paso 2

4. Golpee la tabla hash con el número que acaba de tomar. ¿Hay una entrada? Sí => Paso 5. No => Tome un nuevo número x-1 y repita este paso (esta es una simple búsqueda lineal descendente, solo tenga paciencia conmigo aquí, esto se puede mejorar y le explicaré cómo)

5. Con el elemento de lista recién obtenido de la tabla hash, inserte el nuevo número justo después del elemento en la lista vinculada (y actualice el hash)

6. Tome el número más bajo l registrado (y elimínelo del hash / list).

7. Golpee la tabla hash con el número que acaba de tomar. ¿Hay una entrada? Sí => Paso 8. No => Tome un nuevo número l + 1 y repita este paso (esta es una simple búsqueda lineal ascendente)

8. Con un golpe positivo, el número se convierte en el nuevo número más bajo. Ir al paso 2

Para permitir valores duplicados, el hash realmente necesita mantener el inicio y el final de la secuencia de la lista vinculada de elementos que son duplicados. Agregar o eliminar un elemento en una tecla dada aumenta o disminuye el rango al que apunta.

El inserto aquí es O (1). Las búsquedas mencionadas son, supongo, algo así como O (diferencia promedio entre números). La diferencia promedio aumenta con el tamaño del espacio numérico, pero disminuye con la longitud requerida de la lista de números.

Entonces, la estrategia de búsqueda lineal es bastante pobre, si el espacio numérico es grande (por ejemplo, para un tipo int de 4 bytes, 0 a 2 ^ 32-1) y N = 100. Para evitar este problema de rendimiento, puede mantener conjuntos paralelos de tablas hash, donde los números se redondean a magnitudes más altas (por ejemplo, 1s, 10s, 100s, 1000s) para hacer las teclas adecuadas. De esta manera, puede subir y bajar marchas para realizar las búsquedas necesarias más rápidamente. El rendimiento se convierte en un O (rango de números de registro), creo, que es constante, es decir, O (1) también.

Para aclarar esto, imagine que tiene a mano el número 197. Llegaste a la tabla hash de los 10, con '190', se redondea a los diez más cercanos. ¿Cualquier cosa? No. Entonces bajas en 10 segundos hasta que alcanzas decir 120. Luego puedes comenzar en 129 en la tabla hash de 1, luego prueba 128, 127 hasta que alcances algo. Ahora ha encontrado en qué parte de la lista vinculada insertar el número 197. Al ponerlo, también debe actualizar la tabla hash 1 con la entrada 197, la tabla hash 10 con el número 190, 100 con 100, etc. La mayoría de los pasos alguna vez tienes que hacer aquí son 10 veces el registro del rango de números.

Podría haber equivocado algunos de los detalles, pero dado que este es el intercambio de programadores, y el contexto fue entrevistas, espero que lo anterior sea una respuesta lo suficientemente convincente para esa situación.

EDITAR Agregué algunos detalles adicionales aquí para explicar el esquema de tabla hash paralela y cómo significa que las búsquedas lineales pobres que mencioné pueden reemplazarse con una búsqueda O (1). También me di cuenta de que, por supuesto, no hay necesidad de buscar el siguiente número más bajo, porque puede avanzar directamente hacia él al buscar en la tabla hash con el número más bajo y avanzar al siguiente elemento.

¿Podemos suponer que los números son de un tipo de datos fijo, como Integer? Si es así, mantenga un conteo de cada número agregado. Esta es una operación O (1).

1. Declare una matriz con tantos elementos como números posibles:
2. Lea cada número a medida que se transmite.
3. Cuenta el número. Ignórelo si ese número ya se ha contado 100 veces, ya que nunca lo necesitará. Esto evita que los desbordamientos lo cuenten un número infinito de veces.
4. Repita desde el paso 2.

Código VB.Net:

Const Capacity As Integer = 100

Dim Tally(Integer.MaxValue) As Integer ' Assume all elements = 0
Do
    Value = ReadValue()
    If Tally(Value) < Capacity Then Tally(Value) += 1
Loop

Cuando devuelva la lista, puede tomar el tiempo que desee. Simplemente itere desde el final de la lista y cree una nueva lista de los 100 valores más altos registrados. Esta es una operación O (n), pero eso es irrelevante.

Dim List(Capacity) As Integer
Dim ListCount As Integer = 0
Dim Value As Integer = Tally.Length - 1
Dim ValueCount As Integer = 0
Do Until ListCount = List.Length OrElse Value < 0
    If Tally(Value) > ValueCount Then
        List(ListCount) = Value
        ValueCount += 1
        ListCount += 1
    Else
        Value -= 1
        ValueCount = 0
    End If
Loop
Return List

Editar: de hecho, realmente no importa si se trata de un tipo de datos fijo. Dado que no hay límites impuestos al consumo de memoria (o disco duro), puede hacer que esto funcione para cualquier rango de enteros positivos.

Cien números se almacenan fácilmente en una matriz, tamaño 100. Cualquier árbol, lista o conjunto es excesivo, dada la tarea en cuestión.

Si el número entrante es más alto que el más bajo (= último) en la matriz, ejecute todas las entradas. Una vez que encuentre el primero que sea más pequeño que su nuevo número (puede usar búsquedas sofisticadas para hacerlo), recorra el resto de la matriz, presionando cada entrada "hacia abajo" en una.

Dado que mantiene la lista ordenada desde el principio, no necesita ejecutar ningún algoritmo de clasificación. Esto es O (1).

Puedes usar un binario Max-Heap. Tendría que realizar un seguimiento de un puntero al nodo mínimo (que podría ser desconocido / nulo).

Empiezas insertando los primeros 100 números en el montón. El máximo estará en la parte superior. Una vez hecho esto, siempre mantendrá 100 números allí.

Luego, cuando obtenga un nuevo número:

if(minimumNode == null)
{
    minimumNode = findMinimumNode();
}
if(newNumber > minimumNode.Value)
{
    heap.Remove(minimumNode);
    minimumNode = null;
    heap.Insert(newNumber);
}

Lamentablemente findMinimumNodees O (n), y usted incurre en ese costo una vez por inserción (pero no durante la inserción :). Eliminar el nodo mínimo e insertar el nuevo nodo son, en promedio, O (1) porque tenderán hacia la parte inferior del montón.

Yendo hacia el otro lado con un Binary Min-Heap, el min está en la parte superior, lo cual es ideal para encontrar el min para comparar, pero apesta cuando tienes que reemplazar el mínimo con un nuevo número que es> min. Esto se debe a que debe eliminar el nodo min (siempre O (logN)) y luego insertar el nuevo nodo (O promedio (1)). Entonces, todavía tienes O (logN) que es mejor que Max-Heap, pero no O (1).

Por supuesto, si N es constante, siempre tiene O (1). :)