Dado un flujo de alrededor de mil millones de números en una matriz, que tiene aproximadamente solo 1000 números únicos, ¿cómo puedo imprimir los números únicos? La complejidad debe ser menor que O (n).

Dado:

  • mil millones de números en una matriz sin clasificar
  • una garantía de que solo hay 1000 números diferentes, y
  • algunos supuestos sobre la frecuencia relativa

entonces podemos usar un algoritmo probabilístico que se ejecuta con una “pequeña constante” en relación con el número de elementos de entrada.

  1. Elige un número aleatorio de la matriz
  2. Agréguelo a un conjunto.
  3. Si el conjunto tiene 1000 elementos, finalice e imprima el resultado.
  4. De lo contrario, regrese al paso 1

Es posible que desee vincular el número de muestras en la práctica e informar un error, o cambiar a un algoritmo más lento pero determinista, si se requieren demasiadas muestras.

Suponga que cada número aparece al menos 1000 veces (una frecuencia de 0.0001%). Para hacer un análisis del peor de los casos, asumiremos que aparecen 999 números con una frecuencia mínima y el otro ocupa todo el resto. Como estimación aproximada, podemos decir que la probabilidad de encontrar un nuevo número en cada prueba es de aproximadamente [matemática] 10 ^ {- 6} [/ matemática]. (Obviamente, es más alto que eso, pero no pude encontrar una manera simple de hacer los cálculos en este momento; la mayoría de los ejemplos de este tipo de problema solo se refieren al caso uniforme).

Eso significa que, después de las pruebas [matemática] K [/ matemática], habremos encontrado todos los números con probabilidad aproximadamente [matemática] 1- (1-10 ^ {- 6}) ^ K [/ matemática].

[matemáticas] K = 10000 [/ matemáticas]: menos del 1%

[matemática] K = 10 ^ 5 [/ matemática]: menos del 9.5%

[matemáticas] K = 10 ^ 6 [/ matemáticas]: aproximadamente 63%

[matemáticas] K = 10 ^ 7 [/ matemáticas]: aproximadamente 99.99%

Entonces, después de muestrear al menos el 1% de los cubos, es casi seguro que habremos encontrado las 1000 entradas, incluso si la mayoría de ellas son raras.

Si en cambio asumiéramos una distribución uniforme, ¡solo necesitaríamos unas 50,000 muestras! Por lo tanto, el tiempo de ejecución esperado está determinado por las propiedades de la distribución, en lugar de estrictamente por el tamaño de entrada.

Como el autor ya ha mencionado,
Javascript
var input = [1,11,1,2,3,4,5,…. billones de números];
Salida Var = {}, cuenta = 0;
// atraviesa cada elemento y lo almacena en el mapa de salida si el elemento no existe
para (i = 0; i {
If (! Output [input [i]]))
{
salida [input [i]]) = verdadero;
// si el objeto de salida alcanza 1000 elementos, el bucle se rompe y muestra la matriz
if (++ count === 1000)
rotura;
}
}
// imprimir matriz de salida

La peor complejidad del caso O (n)
Mejor caso O (1000) = O (1)

Si la matriz es monotónica, como su ejemplo, donde los valores están cada vez más ordenados, hay una forma de hacerlo mucho más rápido que O (n) – O (log (n)) en realidad.

Esto se puede lograr con un algoritmo de recursión muy corto y agradable (en mi opinión).

Pondré aquí el código de Matlab y luego explicaré ( x es la matriz de entrada).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
funciones únicas = findunique (x);

if (x (1) == x (end))% Para una matriz constante, devuelve el primer valor
únicos = x (1);
sino% De lo contrario, divida en 2 sub matrices
% y realizar en cada sub-matriz
pivote = piso (longitud (x) / 2);
izquierda = findunique (x (1: pivote));
right = findunique (x (pivote + 1: final));
 
if (left (end) == right (1))% Descarte de valores repetitivos
derecha (1) = [];
fin;
únicos = [izquierda derecha]; % Agregar sublistas de valores únicos
fin;

regreso;
%%%%%%%%%%%%%%%%%%%%%%%

El principio principal del algoritmo es este:
a) Divida la matriz en el medio en 2 sub-matrices.
Debido al comportamiento monótono de los valores en la matriz, los valores únicos en cada una de las matrices secundarias son diferentes, hasta una sola superposición posible alrededor de la posición de la división (pivote en el código).
Por lo tanto, la lista de valores únicos de cada matriz es simplemente la adición de los valores únicos de cada sub-matriz.

b) La etapa (a) se repetirá recursivamente para cada subconjunto.

c) Cuando una (sub) matriz contiene solo un único valor repetitivo, no hay necesidad de probar todos sus miembros , y la lista de valores únicos de esta matriz contiene un solo valor.
Para verificar que esta es la situación, todo lo que tenemos que hacer es comparar el primer y el último valor (nuevamente debido al aumento monotónico).

Hasta donde puedo estimar, estoy casi seguro de que la complejidad de este algoritmo es: K * O (log (n))
donde n es la longitud de la matriz de entrada y K es el número de valores únicos (~ 1000 en la pregunta).

(Que de hecho es ~ O (log (n)) ).

Espero que eso ayude.

void printUniqueIndex (int num [], int nLength)
//
int i <- 0
mientras yo hacer
imprimir num [i]
i <- findIndex (num, nLength, i) int findIndex (int num [], int nLength, int nIndex)
//
int nStore <- num [nIndex]
int j <- 1
nIndex <- nIndex + j
mientras nIndex hacer
j <- j * 2
nIndex <- nIndex + j
j <- nIndex - j + 1
si nIndex es mayor o igual que nLength
entonces
nIndex <- nLength - 1
int nMid
mientras que j es menor o igual que nIndex
hacer
nMid <- (j + nIndex) / 2
if num [nMid]> nStore yn [nMid – 1] == nStore
entonces
volver nMid
más si nStore entonces
nIndex <- nMid - 1
más
j <- nMid + 1
volver -1

Actualización 1: – Análisis de complejidad
Sea m el no de números únicos y X1, X2, X3, ….. Xm-1, Xm sea el no de ocurrencia de cada número único.
ahora,
Lo sabemos
X1 + X2 + X3 +… .. + Xm-1 + Xm = n – (1)

Deje que el elemento que ocurre Xi veces sea Yi.
entonces,
Yi único en Xi se puede encontrar en el tiempo O (log Xi).
Entonces, todos los Yi únicos se pueden encontrar en
O (suma de log Xi)
O (log X1 + log X2 + log X3…. + Log Xm-1 + log Xm)

Ahora, usando la propiedad que
Media aritmática de m números (AM)> = Media geométrica de m números (GM)
(X1 + X2 + X3… + Xm-1 + Xm) / m> = (X1 * X2 * X3 *…. Xm-1 * Xm) ^ (1 / m)

Usando la ecuación 1,
n / m> = (X1 * X2 * X3 * … Xm-1 * Xm) ^ (1 / m)
(n / m) ^ m> = (X1 * X2 * X3 *…. Xm-1 * Xm) – (2)

Ahora, Complejidad = O (Log X1 + X2 + Log X3 +…. Log Xm-1 + Log Xm)
= O (Log X1 * X2 * X3 *… ..Xm-1 * Xm)
Usando la ecuación 2,
Complejidad = O (Log ((n / m) ^ m))
= O (m Log (n / m))

Usar clasificación de cubo.

En el primer recorrido obtenga los números máximos y mínimos presentes en la matriz de mil millones de números, llamémoslo ArrayBillion.

Luego forme una matriz de min_number a max_number cada uno con un recuento inicial de 0, llamémoslo ArrayBucket

Complejidad de tiempo = O (n)

Ahora recorra la matriz una vez más y para cada número ArrayBillion aumente el recuento del elemento correspondiente en Array Bucket.

Complejidad de tiempo = O (n)

El número máximo de elementos en ArrayBucket puede ser n (la longitud de ArrayBillion).

Así que ahora atraviesa el ArrayBucket e imprime aquellos elementos cuya cuenta es 1. Serán los únicos.

Complejidad de tiempo <= O (n)

Complejidad de tiempo total <= 3O (n) ~ O (n)

Qué tal esto,
Tengo esa matriz, por lo que puedo convertirla en un SET (una estructura de datos en Python) y luego puedo imprimir los elementos en el conjunto.
estoy en lo cierto haciendo esto?