structures sort sheet data complexity cheat big best asymptotic algorithms algorithm time-complexity xor space-complexity

algorithm - sheet - radix sort complexity



Encuentre los k elementos no repetitivos en una lista con "poco" espacio adicional (10)

Desviación del algoritmo en OP para k > = 7

Este algoritmo usa la posibilidad de dividir recursivamente un conjunto de k valores únicos en dos grupos usando el valor de un solo bit cuando al menos uno de estos grupos está XORed a un valor distinto de cero. Por ejemplo, los siguientes números.

01000 00001 10001

puede ser dividido en

01000

y

00001 10001

utilizando el valor del bit menos significativo.

Si se implementa correctamente, esto funciona para k <= 6. Pero este enfoque falla para k = 8 y k = 7. Supongamos que m = 4 y usamos 8 números pares de 0 a 14:

0000 0010 0100 0110 1000 1010 1100 1110

Cada bit, excepto el menos significativo, tiene exactamente 4 valores distintos de cero. Si intentamos particionar este conjunto, debido a esta simetría, siempre obtendremos un subconjunto con 2 o 4 o 0 valores distintos de cero. El XOR de estos subconjuntos siempre es 0. Lo que no permite que el algoritmo realice ninguna división, por else que la else parte simplemente imprime el XOR de todos estos valores únicos (un solo cero).

3x + 1 truco 3x + 1 no ayuda: solo baraja estos 8 valores y alterna el bit menos significativo.

Exactamente los mismos argumentos son aplicables para k = 7 si eliminamos el primer valor (todo cero) del subconjunto anterior.

Dado que cualquier grupo de valores únicos se puede dividir en un grupo de 7 u 8 valores y algún otro grupo, este algoritmo también falla para k > 8.

Algoritmo probabilístico

Es posible no inventar un algoritmo completamente nuevo, sino modificarlo en OP, para que funcione con cualquier valor de entrada.

Cada vez que el algoritmo accede a un elemento de la matriz de entrada, debe aplicar alguna función de transformación a este elemento: y=transform(x) . Este valor transformado y se puede usar exactamente como se usó x en el algoritmo original, para particionar los conjuntos y XORAR los valores.

Inicialmente transform(x)=x (algoritmo original sin modificar). Si después de este paso tenemos menos de k resultados (algunos de los resultados son varios valores únicos XORed), cambiamos la transform a alguna función hash y repetimos los cálculos. Esto debería repetirse (cada vez con una función hash diferente) hasta que obtengamos exactamente k valores.

Si estos valores de k se obtienen en el primer paso del algoritmo (sin hashing), estos valores son nuestro resultado. De lo contrario, deberíamos escanear la matriz una vez más, calculando el hash de cada valor y reportando esos valores, que coincidan con uno de los k hashes.

Cada paso subsiguiente de cálculos con diferentes funciones hash puede realizarse en el conjunto original de valores k o (mejor) por separado en cada uno de los subconjuntos, que se encuentran en el paso anterior.

Para obtener una función hash diferente para cada paso del algoritmo, puede utilizar el hashing universal . Una propiedad necesaria para la función hash es la reversibilidad: el valor original debe ser (en teoría) reconstruible a partir del valor hash. Esto es necesario para evitar el hashing de varios valores "únicos" al mismo valor de hash. Dado que el uso de cualquier función reversible de hash de mbit no tiene muchas posibilidades de resolver el problema del "contraejemplo", los valores de hash deben ser más largos que m bits. Un ejemplo simple de dicha función hash es la concatenación del valor original y alguna función hash unidireccional de este valor.

Si k no es muy grande, no es probable que obtengamos un conjunto de datos similar a ese ejemplo de contador. (No tengo pruebas de que no haya otros patrones de datos "malos", con una estructura diferente, pero esperemos que tampoco sean muy probables). En este caso, la complejidad del tiempo promedio no es mucho mayor que O ( k * m 2 * n ).

Otras mejoras para el algoritmo original.

  • Mientras se calcula el XOR de todos los valores (aún no particionados), es razonable verificar un valor de cero único en la matriz. Si hay uno, solo decrementa k .
  • En cada paso de recursión no siempre podemos saber el tamaño exacto de cada partición. Pero sabemos si es impar o par: cada división en un bit distinto de cero da un subconjunto de tamaño impar, la paridad del otro subconjunto es la paridad "conmutada" del subconjunto original.
  • En los últimos pasos de recursión, cuando el único subconjunto no dividido es del tamaño 1, podemos omitir la búsqueda del bit de división e informar el resultado inmediatamente (esta es una optimización para k muy pequeña).
  • Si obtenemos un subconjunto de tamaño impar después de alguna división (y si no sabemos con seguridad si su tamaño es 1), escanee la matriz e intente encontrar un valor único, igual a XOR de este subconjunto.
  • No es necesario recorrer cada bit para dividir el conjunto de tamaño par. Simplemente use cualquier bit distinto de cero de sus valores XORed. El hecho de XOR en uno de los subconjuntos resultantes puede producir cero, pero esta división sigue siendo válida porque tenemos un número impar de "unos" para este bit de división, pero incluso el tamaño establecido. Esto también significa que cualquier división, que produce un subconjunto de tamaño par que no es cero cuando XORed, es una división válida, incluso si el subconjunto restante XOR es cero.
  • No debe continuar dividiendo la búsqueda de bits en cada recursión (como solve(ary, h + 1... ). En su lugar, debe reiniciar la búsqueda desde el principio. Es posible dividir el conjunto en el bit 31, y tener la única división posibilidad de uno de los subconjuntos resultantes en el bit 0.
  • No debe escanear la matriz completa dos veces (por lo tanto, el segundo y = compute_xors(ary, m, bits) no es necesario). Ya tiene XOR de todo el conjunto y XOR de un subconjunto donde el bit de división no es cero. Lo que significa que puede calcular y inmediatamente: y = x ^ old_xor .

Prueba de algoritmo en OP para k = 3

Esta es una prueba no del programa real en OP, sino de su idea. El programa actual actualmente rechaza cualquier división cuando uno de los subconjuntos resultantes es cero. Vea las mejoras sugeridas para los casos en los que podemos aceptar algunas de estas divisiones. Por lo tanto, la siguiente prueba se puede aplicar a ese programa solo después de que if x is None or y is None se cambie a alguna condición que tenga en cuenta la paridad de los tamaños de los subconjuntos o después de agregar un paso de preprocesamiento para excluir un elemento cero exclusivo de la matriz.

Tenemos 3 números diferentes. Deben ser diferentes en al menos 2 posiciones de bit (si son diferentes en solo un bit, el tercer número debe ser igual a uno de los otros). El bucle en la función de solve encuentra a la izquierda de estas posiciones de bit y divide estos 3 números en dos subconjuntos (de un solo número y de 2 números distintos). El subconjunto de 2 números tiene bits iguales en esta posición de bit, pero los números aún deberían ser diferentes, por lo que debería haber una posición de bit de división más (obviamente, a la derecha del primero). El segundo paso de recursión divide fácilmente este subconjunto de 2 números en dos números simples. El truco con i * 3 + 1 es redundante aquí: solo duplica la complejidad del algoritmo.

Aquí hay una ilustración de la primera división en un conjunto de 3 números:

2 1 *b**yzvw *b**xzvw *a**xzvw

Tenemos un bucle que recorre cada posición de bit y calcula XOR de las palabras completas, pero por separado, un valor XOR (A) para los bits verdaderos en una posición dada, otro valor XOR (B) para el bit falso. Si el número A tiene un bit cero en esta posición, A contiene XOR de algún subconjunto de valores de tamaño par, si no es cero - subconjunto de tamaño impar. Lo mismo es cierto para B. Estamos interesados ​​solo en el subconjunto de tamaño par. Puede contener 0 o 2 valores.

Si bien no hay diferencia en los valores de bits (bits z, v, w), tenemos A = B = 0, lo que significa que no podemos dividir nuestros números en estos bits. Pero tenemos 3 números no iguales, lo que significa que en alguna posición (1) deberíamos tener bits diferentes (x e y). Uno de ellos (x) se puede encontrar en dos de nuestros números (¡subconjunto de tamaño uniforme!), Otro (y) - en un número. Veamos el XOR de los valores en este subconjunto de tamaño par. Desde A y B, seleccione el valor (C), que contiene el bit 0 en la posición 1. Pero C es solo un XOR de dos valores no iguales. Son iguales en la posición de bit 1, por lo que deben diferir en al menos una posición de bit más (posición 2, bits a y b). Entonces, C! = 0 y corresponde al subconjunto de tamaño par. Esta división es válida porque podemos dividir este subconjunto de tamaño par aún más por un algoritmo muy simple o por la siguiente recursión de este algoritmo.

Si no hay elementos únicos de cero en la matriz, esta prueba puede simplificarse. Siempre dividimos los números únicos en 2 subconjuntos, uno con 2 elementos (y no puede XOR a cero porque los elementos son diferentes), y otro con un elemento (que no es cero por definición). Así que el programa original con poco preprocesamiento debería funcionar correctamente.

La complejidad es O ( m 2 * n ). Si aplica las mejoras que sugerí anteriormente, la cantidad esperada de veces que este algoritmo escanee la matriz es m / 3 + 2. Debido a que se espera que la primera posición del bit de división sea m / 3, se necesita un solo escaneo para tratar con 2- subconjunto de elementos, cada subconjunto de 1 elemento no necesita exploraciones de matriz, y se necesita una exploración más inicialmente (fuera del método de solve ).

Prueba de algoritmo en OP para k = 4 .. 6

Aquí suponemos que se aplican todas las mejoras sugeridas al algoritmo original.

k = 4 y k = 5 : dado que hay al menos una posición con bits diferentes, este conjunto de números se puede dividir de tal manera que uno de los subconjuntos tenga el tamaño 1 o 2. Si el tamaño del subconjunto es 1, no es -zero (no tenemos cero valores únicos). Si el tamaño del subconjunto es 2, tenemos XOR de dos números diferentes, que es distinto de cero. Así que en ambos casos la división es válida.

k = 6 : Si XOR de todo el conjunto es distinto de cero, podemos dividir este conjunto por cualquier posición donde este XOR tenga un bit distinto de cero. De lo contrario, tenemos un número par de bits distintos de cero en cada posición. Como hay al menos una posición con diferentes bits, esta posición divide el conjunto en subconjuntos de tamaños 2 y 4. El subconjunto de tamaño 2 siempre tiene un XOR distinto de cero porque contiene 2 números diferentes. Nuevamente, en ambos casos tenemos la división válida.

Algoritmo determinista

La corrección para k > = 7 muestra el patrón donde el algoritmo original no funciona: tenemos un subconjunto de tamaño mayor que 2 y en cada posición de bit tenemos un número par de bits distintos de cero. Pero siempre podemos encontrar un par de posiciones donde los bits que no son cero se superponen en un solo número. En otras palabras, siempre es posible encontrar un par de posiciones en el subconjunto de tamaño 3 o 4 con XOR no cero de todos los bits en el subconjunto en ambas posiciones. Esto nos sugiere usar una posición de división adicional: iterar a través de las posiciones de bit con dos punteros separados, agrupar todos los números en la matriz en dos subconjuntos donde un subconjunto tiene ambos bits distintos de cero en estas posiciones, y otro - todos los números restantes. Esto aumenta la complejidad del peor de los casos, pero permite más valores para k . Una vez que no haya más posibilidad de obtener un subconjunto de tamaño inferior a 5, agregue el tercer "puntero de división", y así sucesivamente. Cada vez que k se duplica, es posible que necesitemos un "puntero de división" adicional, lo que aumenta la complejidad del peor de los casos una vez más.

Esto podría considerarse como un boceto de una prueba para el siguiente algoritmo:

  1. Utilice el algoritmo original (mejorado) para encontrar cero o más valores únicos y cero o más subconjuntos no divisibles. Deténgase cuando no haya más subconjuntos no divisibles.
  2. Para cualquiera de estos subconjuntos no divisibles, intente dividirlos mientras aumenta el número de "punteros de división". Cuando se encuentra la división, continúe con el paso 1.

La complejidad del peor caso es O ( k * m 2 * n * m max (0, piso (log (floor ( k / 4)))) ), que puede ser aproximada por O ( k * n * m log (k) ) = O ( k * n * k log (m) ).

El tiempo de ejecución esperado de este algoritmo para k pequeño es un poco peor que para el algoritmo probabilístico, pero aún no es mucho mayor que O ( k * m 2 * n ).

La declaración del problema original es esta:

Dada una matriz de enteros sin signo de 32 bits en los que cada número aparece exactamente dos veces, excepto tres de ellos (que aparecen exactamente una vez), encuentre esos tres números en tiempo O (n) utilizando O (1) espacio adicional. La matriz de entrada es de solo lectura. ¿Qué pasa si hay k excepciones en lugar de 3?

Es fácil resolver esto en Ο(1) tiempo y Ο(1) espacio si acepta un factor constante muy alto debido a la restricción de entrada (la matriz puede tener como máximo 2 33 entradas):

for i in lst: if sum(1 for j in lst if i == j) == 1: print i

Entonces, por el bien de esta pregunta, eliminemos la restricción en la longitud de bits y concentrémonos en el problema más general donde los números pueden tener hasta m bits.

Generalizando un algoritmo para k = 2 , lo que tenía en mente es lo siguiente:

  1. XOR esos números con un bit menos significativo de 1 y aquellos con un 0 separado. Si para ambas particiones, el valor resultante no es cero, sabemos que hemos dividido los números no repetidos en dos grupos, cada uno de los cuales tiene al menos un miembro
  2. Para cada uno de esos grupos, intente dividirlo aún más examinando el segundo bit menos significativo y así sucesivamente

Sin embargo, hay un caso especial a considerar. Si después de particionar un grupo, los valores XOR de uno de los grupos son cero, no sabemos si uno de los subgrupos resultantes está vacío o no. En este caso, mi algoritmo simplemente deja este bit y continúa con el siguiente, que es incorrecto, por ejemplo, falla para la entrada [0,1,2,3,4,5,6] .

Ahora, la idea que tuve fue calcular no solo la XOR del elemento, sino también la XOR de los valores después de aplicar una función determinada (elegí f(x) = 3x + 1 aquí). Vea la respuesta de Evgeny a continuación para ver un contraejemplo de esta verificación adicional.

Ahora, aunque el algoritmo de abajo no es correcto para k> = 7 , todavía incluyo la implementación aquí para darle una idea:

def xor(seq): return reduce(lambda x, y: x ^ y, seq, 0) def compute_xors(ary, mask, bits): a = xor(i for i in ary if i & mask == bits) b = xor(i * 3 + 1 for i in ary if i & mask == bits) return a if max(a, b) > 0 else None def solve(ary, high = 0, mask = 0, bits = 0, old_xor = 0): for h in xrange(high, 32): hibit = 1 << h m = mask | hibit # partition the array into two groups x = compute_xors(ary, m, bits | hibit) y = compute_xors(ary, m, bits) if x is None or y is None: # at this point, we can''t be sure if both groups are non-empty, # so we check the next bit continue mask |= hibit # we recurse if we are absolutely sure that we can find at least one # new value in both branches. This means that the number of recursions # is linear in k, rather then exponential. solve(ary, h + 1, mask, bits | hibit, x) solve(ary, h + 1, mask, bits, y) break else: # we couldn''t find a partitioning bit, so we output (but # this might be incorrect, see above!) print old_xor # expects input of the form "10 1 1 2 3 4 2 5 6 7 10" ary = map(int, raw_input().split()) solve(ary, old_xor=xor(ary))

Según mi análisis, este código tiene una complejidad en el peor de los casos de O(k * m² * n) donde n es el número de elementos de entrada (XORing es O(m) y como máximo k operaciones de partición pueden ser exitosas) y la complejidad del espacio O(m²) (porque m es la profundidad máxima de recursión y los números temporales pueden ser de longitud m ).

La pregunta es, por supuesto, si existe un enfoque correcto y eficiente con un buen tiempo de ejecución asintótico (supongamos que k << n y m << n aquí para completar), que también necesita poco espacio adicional (por ejemplo, enfoques que no se aceptará la clasificación, ya que necesitaríamos al menos O(n) espacio adicional para eso, ¡ya que no podemos modificar la entrada!).

EDITAR: Ahora que el algoritmo anterior ha demostrado ser incorrecto, sería bueno ver cómo podría corregirse, posiblemente haciéndolo un poco menos eficiente. La complejidad del espacio debe estar en o(n*m) (es decir, sublineal en el número total de bits de entrada). Estaría bien tomar k como una entrada adicional si eso facilita la tarea.

Aquí hay una solución adecuada para el caso k = 3 que ocupa solo una cantidad mínima de espacio, y el requisito de espacio es O (1).

Sea ''transform'' una función que toma un entero x sin signo de bit m y un índice i como argumentos. i está entre 0 .. m - 1, y la transformación lleva el entero x a

  • x sí mismo, si el bit i de x no está establecido
  • a x ^ (x <<< 1) donde <<< denota cambio de barril (rotación)

Utilícelo en la siguiente T (x, i) como abreviatura para la transformación (x, i).

Ahora reclamo que si a, b, c son tres enteros distintos sin signo de m-bit y a '', b'', c ''y otros tres enteros distintos sin signo de m-bit distintos, de modo que a XOR b XOR c == a'' XOR b '' XOR c '', pero los conjuntos {a, b, c} y {a'', b '', c''} son dos conjuntos diferentes, entonces hay un índice i tal que T (a, i) XOR T (b, i) ) XOR T (c, i) difiere de T (a '', i) XOR T (b'', i) XOR T (c '', i).

Para ver esto, deje a ''== a XOR a'' '', b'' == b XOR b '''' yc ''== c XOR c'' '', es decir, a'' ''denota el XOR de a y a'' etc. Debido a que XOR b XOR c es igual a ''XOR b'' XOR c ''en cada bit, se deduce que a'' ''XOR b'' ''XOR c'' ''== 0. Esto significa que en cada posición de bit, ya sea a'', b '', c'' son idénticos a a, b, c, o exactamente dos de ellos tienen el bit en la posición elegida invertida (0-> 1 o 1-> 0). Debido a que a '', b'', c ''difieren de a, b, c, sea P la posición de bit en cualquier lugar donde haya habido dos cambios de bit. Procedemos a mostrar que T (a '', P) XOR T (b'', P) XOR T (c '', P) difiere de T (a, P) XOR T (b, P) XOR T (c, P) . Supongamos, sin pérdida de generalidad, que a ''tiene bit flip en comparación con a, b'' tiene bit flip en comparación con b, y c ''tiene el mismo valor de bit que c en esta posición P.

Además de la posición de bit P, debe haber otra posición de bit Q donde a ''y b'' difieran (de lo contrario, los conjuntos no consisten en tres enteros distintos, o voltear el bit en la posición P no crea un nuevo conjunto de enteros, a case that does not need to be considered).El XOR de la versión girada en barril de la posición de bit Q crea un error de paridad en la posición de bit (Q + 1) mod m, lo que lleva a afirmar que T (a '', P) XOR T (b'', P) XOR T (c '', P) difiere de T (a, P) XOR T (b, P) XOR T (c, P). El valor real de c ''no afecta el error de paridad, obviamente.

Por lo tanto, el algoritmo es

  • ejecute la matriz de entrada y calcule (1) el XOR de todos los elementos y (2) el XOR de T (x, i) para todos los elementos x y i entre 0 .. m - 1
  • busque en el espacio constante tres enteros de 32 bits a, b, c tal que a XOR b XOR c y T (a, i) XOR b (a, i) XOR c (a, i) para todos los valores válidos de i match los calculados forman la matriz

Esto funciona obviamente porque los elementos duplicados se cancelan fuera de las operaciones XOR, y para los tres elementos restantes se mantiene el razonamiento anterior.

Yo implementé esto y funciona. Aquí está el código fuente de mi programa de prueba, que usa enteros de 16 bits para la velocidad.

#include <iostream> #include <stdlib.h> using namespace std; /* CONSTANTS */ #define BITS 16 #define MASK ((1L<<(BITS)) - 1) #define N MASK #define D 500 #define K 3 #define ARRAY_SIZE (D*2+K) /* INPUT ARRAY */ unsigned int A[ARRAY_SIZE]; /* ''transform'' function */ unsigned int bmap(unsigned int x, int idx) { if (idx == 0) return x; if ((x & ((1L << (idx - 1)))) != 0) x ^= (x << (BITS - 1) | (x >> 1)); return (x & MASK); } /* Number of valid index values to ''transform''. Note that here index 0 is used to get plain XOR. */ #define NOPS 17 /* Fill in the array --- for testing. */ void fill() { int used[N], i, j; unsigned int r; for (i = 0; i < N; i++) used[i] = 0; for (i = 0; i < D * 2; i += 2) { do { r = random() & MASK; } while (used[r]); A[i] = A[i + 1] = r; used[r] = 1; } for (j = 0; j < K; j++) { do { r = random() & MASK; } while (used[r]); A[i++] = r; used[r] = 1; } } /* ACTUAL PROCEDURE */ void solve() { int i, j; unsigned int acc[NOPS]; for (j = 0; j < NOPS; j++) { acc[j] = 0; } for (i = 0; i < ARRAY_SIZE; i++) { for (j = 0; j < NOPS; j++) acc[j] ^= bmap(A[i], j); } /* Search for the three unique integers */ unsigned int e1, e2, e3; for (e1 = 0; e1 < N; e1++) { for (e2 = e1 + 1; e2 < N; e2++) { e3 = acc[0] ^ e1 ^ e2; // acc[0] is the xor of the 3 elements /* Enforce increasing order for speed */ if (e3 <= e2 || e3 <= e1) continue; for (j = 0; j < NOPS; j++) { if (acc[j] != (bmap(e1, j) ^ bmap(e2, j) ^ bmap(e3, j))) goto reject; } cout << "Solved elements: " << e1 << ", " << e2 << ", " << e3 << endl; exit(0); reject: continue; } } } int main() { srandom(time(NULL)); fill(); solve(); }

Me desconecté y probé el algoritmo original sujeto a la conjetura de que los trucos de XOR funcionaron. Como sucede, los trucos de XOR no funcionan, pero el siguiente argumento puede interesar a algunas personas. (Volví a hacerlo en Haskell porque encuentro que las pruebas son mucho más fáciles cuando tengo funciones recursivas en lugar de bucles y puedo usar estructuras de datos. Pero para los pitonistas en la audiencia, traté de usar listas de comprensión siempre que sea posible).

Código compilable en http://pastebin.com/BHCKGVaV .

Hermosa teoría matada por un hecho feo.

Problema: se nos da una secuencia de n palabras de 32 bits distintas de cero en las que cada elemento es singleton o doubleton :

  • Si una palabra aparece exactamente una vez, es singleton .

  • Si una palabra aparece exactamente dos veces, es doubleton .

  • Ninguna palabra aparece tres o más veces.

El problema es encontrar los singletons. Si hay tres singletons, deberíamos usar el tiempo lineal y el espacio constante. Más generalmente, si hay k singletons, deberíamos usar el tiempo O (k * n) y el espacio O (k) . El algoritmo se basa en una conjetura no probada sobre exclusiva o.

Comenzamos con estos conceptos básicos:

module Singleton where import Data.Bits import Data.List import Data.Word import Test.QuickCheck hiding ((.&.))

Clave de abstracción: Especificación parcial de una palabra.

Para abordar el problema, voy a presentar una abstracción: para describir los $ w $ bits menos significativos de una palabra de 32 bits, presento una Spec :

data Spec = Spec { w :: Int, bits :: Word32 } deriving Show width = w -- width of a Spec

Una Spec coincide con una palabra si los w bits menos significativos son iguales a los bits . Si w es cero, por definición todas las palabras coinciden:

matches :: Spec -> Word32 -> Bool matches spec word = width spec == 0 || ((word `shiftL` n) `shiftR` n) == bits spec where n = 32 - width spec universalSpec = Spec { w = 0, bits = 0 }

Aquí hay algunas afirmaciones sobre Spec s:

  • Todas las palabras coinciden con la universalSpec , que tiene ancho 0

  • Si matches spec word y width spec == 32 , entonces word == bits spec

Idea clave: "ampliar" una especificación parcial.

Aquí está la idea clave del algoritmo: podemos extender una Spec agregando otro bit a la especificación. La extensión de una Spec produce una lista de dos Spec .

extend :: Spec -> [Spec] extend spec = [ Spec { w = w'', bits = bits spec .|. (bit `shiftL` width spec) } | bit <- [0, 1] ] where w'' = width spec + 1

Y aquí está la afirmación crucial: si la spec coincide con la word y si la width spec es menor que 32, entonces exactamente una de las dos especificaciones de la extend spec word coincidirá La prueba es por análisis de caso en el bit de word relevante. Esta afirmación es tan importante que la llamaré Lemma One. Aquí hay una prueba:

lemmaOne :: Spec -> Word32 -> Property lemmaOne spec word = width spec < 32 && (spec `matches` word) ==> isSingletonList [s | s <- extend spec, s `matches` word] isSingletonList :: [a] -> Bool isSingletonList [a] = True isSingletonList _ = False

Vamos a definir una función que, dada una Spec y una secuencia de palabras de 32 bits, devuelve una lista de las palabras singleton que coinciden con la especificación. La función tomará un tiempo proporcional a la longitud de los tiempos de entrada, el tamaño de los tiempos de respuesta 32, y el espacio adicional proporcional al tamaño de los tiempos de respuesta 32. Antes de abordar la función principal, definimos algunas funciones XOR de espacio constante.

XOR ideas que se rompen

La función xorWith f ws aplica la función f a cada palabra en ws y devuelve la exclusiva o el resultado.

xorWith :: (Word32 -> Word32) -> [Word32] -> Word32 xorWith f ws = reduce xor 0 [f w | w <- ws] where reduce = foldl''

Gracias a la fusión de secuencias (ver ICFP 2007), la función xorWith ocupa espacio constante.

Una lista de palabras que no son cero tiene un singleton si y solo si el exclusivo o no es cero, o si el exclusivo o de 3 * w + 1 es distinto de cero. (La dirección "si" es trivial. La dirección "solo si" es una conjetura que Evgeny Kluev ha refutado; para un contraejemplo, vea array testb continuación. Puedo hacer que el ejemplo de Evgeny funcione agregando una tercera función g , pero obviamente esta situación pide una prueba, y no tengo una.)

hasSingleton :: [Word32] -> Bool hasSingleton ws = xorWith id ws /= 0 || xorWith f ws /= 0 || xorWith g ws /= 0 where f w = 3 * w + 1 g w = 31 * w + 17

Búsqueda eficiente de singletons

Nuestra función principal devuelve una lista de todos los singletons que coinciden con una especificación.

singletonsMatching :: Spec -> [Word32] -> [Word32] singletonsMatching spec words = if hasSingleton [w | w <- words, spec `matches` w] then if width spec == 32 then [bits spec] else concat [singletonsMatching spec'' words | spec'' <- extend spec] else []

Probaremos su corrección por inducción en el ancho de la spec .

  • El caso base es que la spec tiene un ancho 32. En este caso, la comprensión de la lista dará la lista de palabras que son exactamente iguales a la bits spec . La función hasSingleton devolverá True si y solo si esta lista tiene exactamente un elemento, lo que será verdadero exactamente cuando la bits spec sea ​​singleton en words .

  • Ahora probemos que si singletonsMatching es correcto para m + 1 , también lo es para ancho m , donde * m <32 $. (Esta es la dirección opuesta a la inducción, pero no importa).

    Aquí está la parte que está rota : para anchos más estrechos, hasSingleton puede devolver False incluso cuando se le da una serie de singletons. Esto es trágico.

    Llamar a extend spec En una spec de ancho m devuelve dos especificaciones que tienen ancho $ m + 1 $. Por hipótesis, la singletonsMatching es correcta en estas especificaciones. Para probar: que el resultado contiene exactamente esos singletons que coinciden con la spec . Por Lemma One, cualquier palabra que coincida con las spec coincide exactamente con una de las especificaciones extendidas. Por hipótesis, las llamadas recursivas devuelven exactamente los singletons que coinciden con las especificaciones de extensión. Cuando combinamos los resultados de estas llamadas con concat , obtenemos exactamente los singletons coincidentes, sin duplicados ni omisiones.

En realidad, resolver el problema es anticlimático: los singletons son todos los singletons que coinciden con la especificación vacía:

singletons :: [Word32] -> [Word32] singletons words = singletonsMatching universalSpec words

Código de prueba

testa, testb :: [Word32] testa = [10, 1, 1, 2, 3, 4, 2, 5, 6, 7, 10] testb = [ 0x0000 , 0x0010 , 0x0100 , 0x0110 , 0x1000 , 0x1010 , 0x1100 , 0x1110 ]

Más allá de este punto, si desea seguir lo que está pasando, necesita saber QuickCheck .

Aquí hay un generador aleatorio para especificaciones:

instance Arbitrary Spec where arbitrary = do width <- choose (0, 32) b <- arbitrary return (randomSpec width b) shrink spec = [randomSpec w'' (bits spec) | w'' <- shrink (width spec)] ++ [randomSpec (width spec) b | b <- shrink (bits spec)] randomSpec width bits = Spec { w = width, bits = mask bits } where mask b = if width == 32 then b else (b `shiftL` n) `shiftR` n n = 32 - width

Usando este generador, podemos probar Lemma One usando quickCheck lemmaOne .

Podemos probar que cualquier palabra que se dice ser un singleton es de hecho singleton:

singletonsAreSingleton nzwords = not (hasTriple words) ==> all (`isSingleton` words) (singletons words) where isSingleton w words = isSingletonList [w'' | w'' <- words, w'' == w] words = [w | NonZero w <- nzwords] hasTriple :: [Word32] -> Bool hasTriple words = hasTrip (sort words) hasTrip (w1:w2:w3:ws) = (w1 == w2 && w2 == w3) || hasTrip (w2:w3:ws) hasTrip _ = False

Aquí hay otra propiedad que prueba los singletons rápidos contra un algoritmo más lento que usa la clasificación.

singletonsOK :: [NonZero Word32] -> Property singletonsOK nzwords = not (hasTriple words) ==> sort (singletons words) == sort (slowSingletons words) where words = [w | NonZero w <- nzwords ] slowSingletons words = stripDoubletons (sort words) stripDoubletons (w1:w2:ws) | w1 == w2 = stripDoubletons ws | otherwise = w1 : stripDoubletons (w2:ws) stripDoubletons as = as

Un enfoque probabilístico a tomar sería utilizar un filtro de conteo .

El algoritmo es como sigue:

  1. Escanear linealmente la matriz y ''actualizar'' el filtro de conteo.
  2. Escanee linealmente la matriz y cree una colección de todos los elementos que no son ciertamente del conteo 2 en el filtro, esto será <= k de las soluciones reales. (Los falsos positivos en este caso son elementos únicos que parecen no serlo).
  3. Elija una nueva base de funciones hash y repita hasta que tengamos todas las k soluciones.

Esto utiliza 2m bits de espacio (independiente de n ). La complejidad del tiempo es más complicada, pero sabiendo que la probabilidad de que no se encuentre un elemento único en el paso 2 es aprox (1 - e^(-kn/m))^k resolveremos una solución muy rápidamente, pero desafortunadamente No somos del todo lineales en n .

Aprecio que esto no satisfaga sus limitaciones ya que es superlineal en el tiempo y es probabilístico, pero dadas las condiciones originales pueden no ser satisfactorias, este enfoque puede valer la pena considerarlo.

Dos enfoques funcionarían.

(1) Cree una tabla hash temporal donde las claves son los enteros y los valores son el número de repeticiones. Por supuesto, esto usaría más espacio del especificado.

(2) ordene la matriz (o una copia) y luego cuente el número de casos donde la matriz [n + 2] == matriz [n]. Por supuesto, esto usaría más tiempo del especificado.

Estaré muy sorprendido de ver una solución que satisfaga las restricciones originales.

Esto es solo una intuición, pero creo que la solución es aumentar el número de particiones que evalúa hasta que encuentre una en la que su xor suma no sea cero.

Por ejemplo, para cada dos bits (x, y) en el rango [0, m), considere las particiones definidas por el valor de a & ((1<<x) || (1 << y)). En el caso de 32 bits, eso resulta en 32 * 32 * 4 = 4096 particiones y permite resolver correctamente el caso donde k = 4.

Lo interesante ahora sería encontrar una relación entre k y el número de particiones necesarias para resolver el problema, que también nos permitiría calcular la complejidad del algoritmo. Otra pregunta abierta es si hay mejores esquemas de partición.

Algún código de Perl para ilustrar la idea:

my $m = 10; my @a = (0, 2, 4, 6, 8, 10, 12, 14, 15, 15, 7, 7, 5, 5); my %xor; my %part; for my $a (@a) { for my $i (0..$m-1) { my $shift_i = 1 << $i; my $bit_i = ($a & $shift_i ? 1 : 0); for my $j (0..$m-1) { my $shift_j = 1 << $j; my $bit_j = ($a & $shift_j ? 1 : 0); my $k = "$i:$bit_i,$j:$bit_j"; $xor{$k} ^= $a; push @{$part{$k} //= []}, $a; } } } print "list: @a/n"; for my $k (sort keys %xor) { if ($xor{$k}) { print "partition with unique elements $k: @{$part{$k}}/n"; } else { # print "partition without unique elements detected $k: @{$part{$k}}/n"; } }

La solución al problema anterior (encontrar números uint32 únicos en O (N) con uso de memoria O (1)) es bastante simple, aunque no particularmente rápida:

void unique(int n, uint32 *a) { uint32 i = 0; do { int j, count; for (count = j = 0; j < n; j++) { if (a[j] == i) count++; } if (count == 1) printf("%u appears only once/n", (unsigned int)i); } while (++i); }

Para el caso en el que el número de bits M no está limitado, la complejidad se convierte en O (N * M * 2 M ) y el uso de la memoria sigue siendo O (1).

actualización : la solución complementaria que usa un mapa de bits da como resultado la complejidad O (N * M) y el uso de memoria O (2 M ):

void unique(int n, uint32 *a) { unsigned char seen[1<<(32 - 8)]; unsigned char dup[1<<(32 - 8)]; int i; memset(seen, sizeof(seen), 0); memset(dup, sizeof(dup), 0); for (i = 0; i < n; i++) { if (bitmap_get(seen, a[i])) { bitmap_set(dup, a[i], 1); } else { bitmap_set(seen, a[i], 1); } } for (i = 0; i < n; i++) { if (bitmap_get(seen, a[i]) && !bitmap_get(dup, a[i])) { printf("%u appears only once/n", (unsigned int)a[i]); bitmap_set(seen, a[i], 0); } } }

Curiosamente, ambos enfoques se pueden combinar dividiendo el espacio de 2 M en bandas. Luego tendrá que recorrer todas las bandas y, dentro de cada banda, encontrar valores únicos utilizando la técnica de vector de bits.

Con los requisitos de complejidad de espacio, afloje a O ( m * n ), esta tarea se puede resolver fácilmente en tiempo O ( n ). Solo cuente el número de instancias para cada elemento usando una tabla hash, luego filtre las entradas con un contador igual a uno. O utilice cualquier algoritmo de clasificación distributiva.

Pero aquí hay un algoritmo probabilístico, que tiene requisitos de espacio más ligeros.

Este algoritmo utiliza un conjunto de bits adicional de tamaño s . Para cada valor en la matriz de entrada, se calcula una función hash. Esta función hash determina un índice en el conjunto de bits. La idea es escanear la matriz de entrada, alternando el bit correspondiente en el conjunto de bits para cada entrada de la matriz. Las entradas duplicadas alternan el mismo bit dos veces. Los bits, alternados por las entradas únicas (casi todos) permanecen en el conjunto de bits. Esto es prácticamente lo mismo que contar el filtro Bloom, donde el único bit usado en cada contador es el bit menos significativo.

Al escanear la matriz una vez más, podemos extraer valores únicos (excluyendo algunos falsos negativos), así como algunos valores duplicados (falsos positivos).

El conjunto de bits debe ser lo suficientemente disperso como para dar la menor cantidad de falsos positivos posibles para disminuir el número de valores duplicados innecesarios y, por lo tanto, para disminuir la complejidad del espacio. El beneficio adicional de la alta dispersión del conjunto de bits es disminuir el número de falsos negativos, lo que mejora un poco el tiempo de ejecución.

Para determinar el tamaño óptimo para el conjunto de bits, distribuya el espacio disponible de manera uniforme entre el conjunto de bits y la matriz temporal que contiene valores únicos y falsos positivos (suponiendo que k << n ): s = n * m * k / s , que da s = sqrt ( n * m * k ). Y el requisito de espacio esperado es O (sqrt ( n * m * k )).

  1. Escanee la matriz de entrada y alterne los bits en el conjunto de bits.
  2. Escanee la matriz de entrada y filtre los elementos que tengan el bit distinto de cero en el conjunto de bits, escríbalos en la matriz temporal.
  3. Utilice cualquier método simple (clasificación de distribución o hash) para excluir duplicados de la matriz temporal.
  4. Si el tamaño de la matriz temporal más el número de elementos únicos conocidos hasta ahora es menor que k , cambie la función de troceo, borre el conjunto de bits y los bits de conmutación, correspondientes a valores únicos conocidos, continúe con el paso 1.

La complejidad del tiempo esperado está en algún lugar entre O ( n * m ) y O ( n * m * log ( n * m * k ) / log ( n * m / k )).

Su algoritmo no es O (n), porque no hay garantía de dividir los números en dos grupos del mismo tamaño en cada paso, también porque no hay límite en los tamaños de los números (no están relacionados con n), no hay límite para su pasos posibles, si no tiene ningún límite en el tamaño de sus números de entrada (si son independientes de ellos n), el tiempo de ejecución de su algoritmo podría ser) (n), suponga que los números de mbit de tamaño son inferiores y solo sus primeros nbits podrían ser diferentes: (supongamos m > 2n)

---- n bits --- ---- m-n bits -- 111111....11111 00000....00000 111111....11111 00000....00000 111111....11110 00000....00000 111111....11110 00000....00000 .... 100000....00000 00000....00000

Su algoritmo se ejecutará para los primeros mnbits y estará O(n)en cada paso, hasta ahora llegó O ((mn) * n) que es más grande que O (n ^ 2).

PD: si siempre tiene números de 32 bits, su algoritmo es O(n)y no es difícil de probar esto.

Supongo que sabe k de antemano
. Elijo Squeak Smalltalk como lenguaje de implementación.

  • inyectar: ​​en: es reducir y es O (1) en el espacio, O (N) en el tiempo
  • select: es filter, (no lo usamos porque O (1) espacio requerido)
  • recopilar: es un mapa, (no lo usamos porque O (1) requisito de espacio)
  • do: es forall, y es O (1) en el espacio, O (N) en el tiempo
  • un bloque entre corchetes es un cierre, o un lambda puro si no se cierra sobre ninguna variable y no usa retorno, el símbolo con el prefijo de dos puntos son los parámetros.
  • ^ significa retorno

Para k = 1, el singleton se obtiene reduciendo la secuencia con el bit xor

Así que definimos un método xorSum en la clase Collection (por lo tanto, self es la secuencia)

Collection>>xorSum ^self inject: 0 into: [:sum :element | sum bitXor:element]

y un segundo método

Collection>>find1Singleton ^{self xorSum}

Lo probamos con

self assert: {0. 3. 5. 2. 5. 4. 3. 0. 2.} find1Singleton = {4}

El costo es O (N), espacio O (1)

Para k = 2, buscamos dos singletons, (s1, s2)

Collection>>find2Singleton | sum lowestBit s1 s2 | sum := self xorSum.

la suma es diferente de 0 y es igual a (s1 bitXOr: s2), el xor de dos singletons

Dividir en el bit de suma de conjunto más bajo, y xo ambas secuencias, como usted propuso, obtiene los 2 singletons

lowestBit := sum bitAnd: sum negated. s1 := s2 := 0. self do: [:element | (element bitAnd: lowestBit) = 0 ifTrue: [s1 := s1 bitXor: element] ifFalse: [s2 := s2 bitXor: element]]. ^{s1. s2}

y

self assert: {0. 1. 1. 3. 5. 6. 2. 6. 4. 3. 0. 2.} find2Singleton sorted = {4. 5}

El costo es 2 * O (N), espacio O (1)

Para k = 3,

Definimos una clase específica que implementa una ligera variación de la división xor, de hecho usamos una división ternaria, la máscara puede tener valor1 o valor2, cualquier otro valor se ignora.

Object subclass: #BinarySplit instanceVariableNames: ''sum1 sum2 size1 size2'' classVariableNames: '''' poolDictionaries: '''' category: ''SO''.

con estos métodos de instancia:

sum1 ^sum1 sum2 ^sum2 size1 ^size1 size2 ^size2 split: aSequence withMask: aMask value1: value1 value2: value2 sum1 := sum2 := size1 := size2 := 0. aSequence do: [:element | (element bitAnd: aMask) = value1 ifTrue: [sum1 := sum1 bitXor: element. size1 := size1 + 1]. (element bitAnd: aMask) = value2 ifTrue: [sum2 := sum2 bitXor: element. size2 := size2 + 1]]. doesSplitInto: s1 and: s2 ^(sum1 = s1 and: [sum2 = s2]) or: [sum1 = s2 and: [sum2 = s1]]

Y este método del lado de la clase, una especie de constructor para crear una instancia

split: aSequence withMask: aMask value1: value1 value2: value2 ^self new split: aSequence withMask: aMask value1: value1 value2: value2

Luego calculamos:

Collection>>find3SingletonUpToBit: m | sum split split2 mask value1 value2 | sum := self xorSum.

Pero esto no proporciona ninguna información sobre el bit a dividir ... Así que intentamos cada bit i = 0..m-1.

0 to: m-1 do: [:i | split := BinarySplit split: self withMask: 1 << i value1: 1<<i value2: 0.

Si obtienes (sum1, sum2) == (0, sum), entonces obtienes los 3 singletons en la misma bolsa ...
Así que repite hasta que obtengas algo diferente
. Si es diferente, obtendrás una bolsa con s1 (el que tiene un tamaño impar) y otro con s2, s3 (tamaño par), así que solo aplique el algoritmo para k = 1 (s1 = suma1) yk = 2 con un patrón de bits modificado

(split doesSplitInto: 0 and: sum) ifFalse: [split size1 odd ifTrue: [mask := (split sum2 bitAnd: split sum2 negated) + (1 << i). value1 := (split sum2 bitAnd: split sum2 negated). value2 := 0. split2 := BinarySplit split: self withMask: mask value1: value1 value2: value2. ^{ split sum1. split2 sum1. split2 sum2}] ifFalse: [mask := (split sum1 bitAnd: split sum1 negated) + (1 << i). value1 := (split sum1 bitAnd: split sum1 negated) + (1 << i). value2 := (1 << i). split2 := BinarySplit split: self withMask: mask value1: value1 value2: value2. ^{ split sum2. split2 sum1. split2 sum2}]].

Y lo probamos con

self assert: ({0. 1. 3. 5. 6. 2. 6. 4. 3. 0. 2.} find3SingletonUpToBit: 32) sorted = {1. 4. 5}

El peor costo es (M + 1) * O (N)

Para k = 4,

Cuando nos dividimos, podemos tener (0,4) o (1,3) o (2,2) singletons.
(2,2) es fácil de reconocer, ambos tamaños son pares y ambos xo suma son diferentes de 0, caso resuelto.
(0,4) es fácil de reconocer, ambos tamaños son pares, y al menos una suma es cero, por lo que la búsqueda repetida con patrón de bits incrementado en la bolsa con la suma! = 0
(1,3) es más difícil, porque ambos tamaños son impares, y volvemos al caso de un número desconocido de singletons ... Sin embargo, podemos reconocer fácilmente el singleton individual, si un elemento de la bolsa es igual a la suma xor, que es imposible con 3 números diferentes ...

Podemos generalizar para k = 5 ... pero lo anterior será difícil porque debemos encontrar un truco para el caso (4,2) y (1,5), recuerde nuestra hipótesis, debemos conocer k por adelantado ... Tendremos que hacer hipótesis y verificarlas después ...

Si tiene un ejemplo de contador, simplemente envíelo, verificaré con la implementación anterior de Smalltalk

EDITAR: Cometí el código (licencia MIT) en http://ss3.gemstone.com/ss/SONiklasBContest.html