algorithm - telefono - La manera más eficiente de almacenar miles de números de teléfono

numeros de telefonos de mexico (13)

Mi solución: mejor caso 7.025 bits / número, peor caso 14.193 bits / número, promedio aproximado 8.551 bits / número. Codificado en secuencia, sin acceso aleatorio.

Incluso antes de leer la respuesta de ruslik, inmediatamente pensé en codificar la diferencia entre cada número, ya que sería pequeño y debería ser relativamente uniforme, pero la solución también debe ser capaz de acomodarse al peor de los casos. Tenemos un espacio de 100000 números que contienen solo 1000 números. En una guía telefónica perfectamente uniforme, cada número sería 100 veces mayor que el número anterior:

55555-12 3 45
55555-12 4 45
55555-12 5 45

Si ese fuera el caso, requeriría cero almacenamiento para codificar las diferencias entre los números, ya que es una constante conocida. Desafortunadamente, los números pueden variar de los pasos ideales de 100. Codificaría la diferencia del incremento ideal de 100, de modo que si dos números adyacentes difieren por 103, codificaría el número 3 y si dos números adyacentes difieren por 92, codificaría -8. Llamo al delta desde un incremento ideal de 100 la " varianza ".

La varianza puede variar de -99 (es decir, dos números consecutivos) a 99000 (la agenda entera consta de los números 00000 ... 00999 y un número adicional más lejano 99999), que es un rango de 99100 valores posibles.

Me propongo asignar un almacenamiento mínimo para codificar las diferencias más comunes y expandir el almacenamiento si encuentro mayores diferencias (como el ProtoBuf de varint ). Utilizaré trozos de siete bits, seis para el almacenamiento y un bit de indicador adicional al final para indicar que esta varianza se almacena con un trozo adicional después del actual, hasta un máximo de tres trozos (lo que proporcionará un máximo de 3 * 6 = 18 bits de almacenamiento, que son 262144 valor posible, más que el número de variaciones posibles (99100). Cada fragmento adicional que sigue a un indicador elevado tiene bits de mayor importancia, por lo que el primer fragmento siempre tiene bits 0- 5, los segundos trozos opcionales tienen los bits 6-11, y el tercer trozo opcional tiene los bits 12-17.

Un solo fragmento proporciona seis bits de almacenamiento que pueden acomodar 64 valores. Me gustaría asignar las 64 varianzas más pequeñas para que quepan en ese solo trozo (es decir, varianzas de -32 a +31) así que usaré la codificación ProtoBuf ZigZag, hasta las varianzas de -99 a +98 (ya que no es necesario para una varianza negativa más allá de -99), en ese punto cambiaré a codificación regular, compensada por 98:

Variance | Encoded Value -----------+---------------- 0 | 0 -1 | 1 1 | 2 -2 | 3 2 | 4 -3 | 5 3 | 6 ... | ... -31 | 61 31 | 62 -32 | 63 -----------|--------------- 6 bits 32 | 64 -33 | 65 33 | 66 ... | ... -98 | 195 98 | 196 -99 | 197 -----------|--------------- End of ZigZag 100 | 198 101 | 199 ... | ... 3996 | 4094 3997 | 4095 -----------|--------------- 12 bits 3998 | 4096 3999 | 4097 ... | ... 262045 | 262143 -----------|--------------- 18 bits

Algunos ejemplos de cómo las varianzas se codificarían como bits, incluido el indicador para indicar un fragmento adicional:

Variance | Encoded Bits -----------+---------------- 0 | 000000 0 5 | 001010 0 -8 | 001111 0 -32 | 111111 0 32 | 000000 1 000001 0 -99 | 000101 1 000011 0 177 | 010011 1 000100 0 14444 | 001110 1 100011 1 000011 0

Por lo tanto, los primeros tres números de una guía de teléfonos de muestra se codificarán como una secuencia de bits de la siguiente manera:

BIN 000101001011001000100110010000011001 000110 1 010110 1 00001 0 PH# 55555-12345 55555-12448 55555-12491 POS 1 2 3

En el mejor de los casos , la guía telefónica se distribuye de manera uniforme y no hay dos números telefónicos que tengan una variación mayor a 32, por lo que usaría 7 bits por número más 32 bits para el número inicial para un total de 32 + 7 * 999 = 7025 bits .
Un escenario mixto , donde la varianza de 800 números telefónicos se ajusta dentro de un fragmento (800 * 7 = 5600), 180 números caben en dos pedazos cada uno (180 * 2 * 7 = 2520) y 19 números caben en tres pedazos cada uno (20 * 3 * 7 = 399), más los 32 bits iniciales, un total de 8551 bits .
En el peor de los casos , 25 números caben en tres pedazos (25 * 3 * 7 = 525 bits) y los 974 restantes caben en dos pedazos (974 * 2 * 7 = 13636 bits), más 32 bits para el primer número para un gran total de 14193 bits

Amount of encoded numbers | 1-chunk | 2-chunks | 3-chunks | Total bits ---------+----------+----------+------------ 999 | 0 | 0 | 7025 800 | 180 | 19 | 8551 0 | 974 | 25 | 14193

Puedo ver cuatro optimizaciones adicionales que se pueden realizar para reducir aún más el espacio requerido:

El tercer fragmento no necesita los siete bits completos, puede ser solo cinco bits y sin un bit de marca.
Puede haber un pase inicial de los números para calcular los mejores tamaños para cada fragmento. Tal vez para un determinado directorio telefónico, sería óptimo tener el primer fragmento con 5 + 1 bits, el segundo 7 + 1 y el tercero 5 + 1. Eso reduciría aún más el tamaño a un mínimo de 6 * 999 + 32 = 6026 bits, más dos juegos de tres bits para almacenar los tamaños de los trozos 1 y 2 (el tamaño del trozo 3 es el resto de los 16 bits requeridos) para un total de 6032 bits!
El mismo pase inicial puede calcular un mejor incremento esperado que el 100 predeterminado. Tal vez haya una guía telefónica que comience en 55555-50000, por lo que tiene la mitad del rango numérico, por lo que el incremento esperado debería ser de 50. O tal vez no sea lineal distribución (desviación estándar tal vez) y algún otro incremento esperado óptimo puede ser utilizado. Esto reduciría la varianza típica y podría permitir que se use un primer trozo aún más pequeño.
Se puede realizar un análisis adicional en el primer pase para permitir que la guía telefónica se particione, con cada partición teniendo su propio incremento esperado y optimizaciones del tamaño de los fragmentos. Esto permitiría un primer fragmento de tamaño más pequeño para ciertas partes altamente uniformes de la guía telefónica (reduciendo la cantidad de bits consumidos) y tamaños de trozos más grandes para partes no uniformes (reduciendo la cantidad de bits desperdiciados en indicadores de continuación).

Esta es una pregunta de entrevista de google:

Hay alrededor de mil números de teléfono para almacenar, cada uno con 10 dígitos. Puede suponer que los primeros 5 dígitos de cada uno sean iguales en miles de números. Debe realizar las siguientes operaciones: a. Busque si existe un número dado. segundo. Imprime todo el número

¿Cuál es la manera más eficiente de ahorrar espacio para hacer esto?

Respondí la tabla de hash y luego la codificación de huffman pero mi entrevistador dijo que no iba en la dirección correcta. Por favor, ayúdame aquí.

¿Podría usar un sufijo para ayudar?

Idealmente, el almacenamiento de 1000 números requiere 4 bytes por número, por lo que tomaría 4000 bytes para almacenar 1000. Cuantitativamente, deseo reducir el almacenamiento a <4000 bytes, esto es lo que mi entrevistador me explicó.

¿Por qué no mantenerlo simple? Usa una matriz de estructuras.

Así que podemos guardar los primeros 5 dígitos como una constante, así que olvídalos por el momento.

65535 es lo máximo que puede almacenarse en un número de 16 bits, y el número máximo que podemos tener es 99999, que se ajusta al número de 17 bits con un máximo de 131071.

Usar tipos de datos de 32 bits es un desperdicio porque solo necesitamos 1 bit de esos 16 bits adicionales ... por lo tanto, podemos definir una estructura que tenga un booleano (o carácter) y un número de 16 bits ...

Asumiendo C / C ++

typedef struct _number { uint16_t number; bool overflow; }Number;

Esta estructura solo ocupa 3 bytes, y necesitamos una matriz de 1000, por lo que 3000 bytes en total. ¡Hemos reducido el espacio total en un 25%!

En cuanto a almacenar los números, podemos hacer cálculos simples en bits

overflow = (number5digits & 0x10000) >> 4; number = number5digits & 0x1111;

Y el inverso

//Something like this should work number5digits = number | (overflow << 4);

Para imprimirlos todos, podemos usar un simple bucle sobre la matriz. La recuperación de un número específico ocurre en tiempo constante, por supuesto, ya que es una matriz.

for(int i=0;i<1000;i++) cout << const5digits << number5digits << endl;

Para buscar un número, nos gustaría una matriz ordenada. Entonces, cuando se guardan los números, clasifique la matriz (yo elegiría un tipo de fusión personalmente, O (nlogn)). Ahora para buscar, elegiría un enfoque de fusión. Divida la matriz y vea cuál es nuestro número. Luego llame a la función solo en esa matriz. Recursivamente haga esto hasta que tenga una coincidencia y devuelva el índice; de lo contrario, no existe e imprime un código de error. Esta búsqueda sería bastante rápida, y el peor de los casos es mejor que O (nlogn) ya que se ejecutará absolutamente en menos tiempo que el tipo de combinación (solo recursing 1 lado de la división cada vez, en lugar de ambos lados :)), que es O (nlogn).

A continuación, trato los números como variables enteras (en lugar de cadenas):

Ordena los números.
Divida cada número en los primeros cinco dígitos y los últimos cinco dígitos.
Los primeros cinco dígitos son los mismos en todos los números, así que guárdelos solo una vez. Esto requerirá 17 bits de almacenamiento.
Almacene los últimos cinco dígitos de cada número individualmente. Esto requerirá 17 bits por número.

Para recapitular: los primeros 17 bits son el prefijo común, los siguientes 1000 grupos de 17 bits son los últimos cinco dígitos de cada número almacenados en orden ascendente.

En total estamos viendo 2128 bytes para los 1000 números, o 17.017 bits por número de teléfono de 10 dígitos.

La búsqueda es O(log n) (búsqueda binaria) y la enumeración completa es O(n) .

Aquí hay una mejora a la respuesta de Aix . Considere usar tres "capas" para la estructura de datos: la primera es una constante para los primeros cinco dígitos (17 bits); así que a partir de ahora, cada número de teléfono tiene solo los cinco dígitos restantes. Vemos estos cinco dígitos restantes como enteros binarios de 17 bits y almacenamos k de esos bits usando un método y 17 - k = m con un método diferente, determinando k al final para minimizar el espacio requerido.

Primero ordenamos los números de teléfono (todos reducidos a 5 dígitos decimales). Luego contamos cuántos números de teléfono hay para los cuales el número binario que consiste en los primeros m bits es todo 0, para cuántos números de teléfono son los primeros m bits como máximo 0 ... 01, para cuántos números de teléfono el primer m los bits son como mucho 0 ... 10, etcétera, hasta el recuento de números de teléfono cuyos primeros m bits son 1 ... 11 - este último conteo es 1000 (decimal). Hay 2 ^ m tales conteos y cada recuento es como máximo 1000. Si omitimos el último (porque sabemos que es 1000 de todos modos), podemos almacenar todos estos números en un bloque contiguo de (2 ^ m - 1) * 10 bits. (10 bits es suficiente para almacenar un número inferior a 1024).

Los últimos k bits de todos los números de teléfono (reducidos) se almacenan contiguamente en la memoria; entonces si k es, digamos, 7, entonces los primeros 7 bits de este bloque de memoria (bits 0 a 6) corresponden a los últimos 7 bits del primer número de teléfono (reducido), los bits 7 a 13 corresponden a los últimos 7 bits del segundo número de teléfono (reducido), etcétera. Esto requiere 1000 * k bits para un total de 17 + (2 ^ (17 - k ) - 1) * 10 + 1000 * k , que alcanza su mínimo 11287 para k = 10. Así que podemos almacenar todos los números de teléfono en el cielo ( 11287/8) = 1411 bytes.

Se puede ahorrar espacio adicional al observar que ninguno de nuestros números puede comenzar, por ejemplo, con 1111111 (binario), porque el número más bajo que comienza con eso es 130048 y solo tenemos cinco dígitos decimales. Esto nos permite afeitar algunas entradas del primer bloque de memoria: en lugar de 2 ^ m - 1 conteos, solo necesitamos ceil (99999/2 ^ k ). Eso significa que la fórmula se convierte

17 + ceil (99999/2 ^ k ) * 10 + 1000 * k

que sorprendentemente alcanza su mínimo 10997 para k = 9 yk = 10, o ceil (10997/8) = 1375 bytes.

Si queremos saber si un determinado número de teléfono está en nuestro conjunto, primero verificamos si los primeros cinco dígitos binarios coinciden con los cinco dígitos que hemos almacenado. Luego dividimos los cinco dígitos restantes en su parte superior m = 7 bits (que es, por ejemplo, el número de mbit M ) y su k inferior es de 10 bits (el número K ). Ahora encontramos el número a [M-1] de números de teléfono reducidos para los cuales los primeros m dígitos son como máximo M - 1, y el número a [M] de números de teléfono reducidos para los cuales los primeros m dígitos son como máximo M , ambos desde el primer bloque de bits. Ahora comprobamos entre la secuencia a [M-1] th y a [M] th de k bits en el segundo bloque de memoria para ver si encontramos K ; en el peor de los casos hay 1000 de tales secuencias, por lo que si usamos la búsqueda binaria podemos terminar en operaciones O (log 1000).

Sigue el seudocódigo para imprimir los 1000 números, donde accedo a la entrada K ''th k- bit del primer bloque de memoria como una [K] y la entrada M '' th m- bit del segundo bloque de memoria como b [M] (ambos requerirían algunas operaciones de bit que son tediosas de escribir). Los primeros cinco dígitos están en el número c .

i := 0; for K from 0 to ceil(99999 / 2^k) do while i < a[K] do print(c * 10^5 + K * 2^k + b[i]); i := i + 1; end do; end do;

Quizás algo va mal con el caso límite para K = ceil (99999/2 ^ k ), pero eso es bastante fácil de arreglar.

Finalmente, desde un punto de vista de entropía, no es posible almacenar un subconjunto de 10 ^ 3 enteros positivos, todos menos de 10 ^ 5 en menos que el ceil (log [2] (binomial (10 ^ 5, 10 ^ 3)) ) = 8073. Incluyendo los 17 que necesitamos para los primeros 5 dígitos, todavía hay un espacio de 10997 - 8090 = 2907 bits. ¡Es un desafío interesante ver si hay mejores soluciones donde aún se puede acceder a los números de manera relativamente eficiente!

Este es un problema bien conocido de Bentley''s Programming Pearls.

Solución: quite los primeros cinco dígitos de los números ya que son los mismos para cada número. Luego use operaciones a nivel de bits para representar el valor posible 9999 restante. Solo necesitará 2 ^ 17 Bits para representar los números. Cada bit representa un número. Si el bit está configurado, el número está en el libro de teléfono.

Para imprimir todos los números, simplemente imprima todos los números donde el bit está configurado concatenado con el prefijo. Para buscar un número dado, haga la aritmética de bit necesaria para verificar la representación bit a bit del número.

Puede buscar un número en O (1) y la eficiencia del espacio es máxima debido a la representación de bit.

HTH Chris.

Esto es equivalente a almacenar mil enteros no negativos cada uno menos de 100,000. Podemos usar algo así como la codificación aritmética para hacer esto.

En última instancia, los números se almacenarán en una lista ordenada. Noto que la diferencia esperada entre los números adyacentes en la lista es 100,000 / 1000 = 100, que se puede representar en 7 bits. También habrá muchos casos en los que sean necesarios más de 7 bits. Una forma simple de representar estos casos menos comunes es adoptar el esquema utf-8 donde un byte representa un entero de 7 bits a menos que se establezca el primer bit, en cuyo caso se lee el siguiente byte para producir un entero de 14 bits, a menos su primer bit está configurado, en cuyo caso el siguiente byte se lee para representar un entero de 21 bits.

Por lo tanto, al menos la mitad de las diferencias entre enteros consecutivos se pueden representar con un byte, y casi todo el resto requiere dos bytes. Unos pocos números, separados por diferencias mayores que 16,384, requerirán tres bytes, pero no puede haber más de 61 de estos. El almacenamiento promedio será aproximadamente de 12 bits por número, o un poco menos, o como máximo 1500 bytes.

La desventaja de este enfoque es que verificar la existencia de un número ahora es O (n). Sin embargo, no se especificó ningún requisito de complejidad de tiempo.

Después de escribir, noté que Ruslik ya sugirió el método de diferencia anterior, la única diferencia es el esquema de codificación. El mío es probablemente más simple pero menos eficiente.

He oído hablar de este problema antes (pero sin los primeros 5 dígitos son la misma suposición), y la forma más sencilla de hacerlo fue Rice Coding :

1) Como el orden no importa, podemos ordenarlos y guardar solo las diferencias entre los valores consecutivos. En nuestro caso, las diferencias promedio serían 100.000 / 1000 = 100

2) Codifique las diferencias usando códigos Rice (base 128 o 64) o incluso códigos Golomb (base 100).

EDITAR: una estimación para la codificación Rice con base 128 (no porque daría mejores resultados, sino porque es más fácil de calcular):

Guardaremos el primer valor como está (32 bits).
El resto de los 999 valores son diferencias (esperamos que sean pequeños, 100 en promedio) contendrán:

valor de value / 128 unario value / 128 (número variable de bits + 1 bit como terminador)
valor binario para el value % 128 (7 bits)

Tenemos que estimar de alguna manera los límites (llamémoslo VBL ) para el número de bits variables:
límite inferior: considere que tenemos suerte, y ninguna diferencia es mayor que nuestra base (128 en este caso). esto significaría dar 0 bits adicionales.
límite alto: dado que todas las diferencias menores que la base se codificarán en una parte binaria del número, el número máximo que necesitaríamos codificar en unario es 100000/128 = 781.25 (incluso menos, porque no esperamos que la mayoría de las diferencias sean cero )

Entonces, el resultado es 32 + 999 * (1 + 7) + variable (0..782) bits = 1003 + variable (0..98) bytes.

La verdadera pregunta es la de almacenar números de teléfono de cinco dígitos.

El truco es que necesitarías 17 bits para almacenar el rango de números de 0..99.999. Pero almacenar 17 bits en los límites de palabras convencionales de 8 bytes es una molestia. Es por eso que están preguntando si puede hacer en menos de 4k al no usar enteros de 32 bits.

Pregunta: ¿son posibles todas las combinaciones de números?

Debido a la naturaleza del sistema telefónico, puede haber menos de 65k combinaciones posibles. Asumiré que sí porque estamos hablando de las últimas cinco posiciones en el número de teléfono, a diferencia del código de área o los prefijos de intercambio.

Pregunta: ¿Esta lista será estática o necesitará soportar actualizaciones?

Si es estático , cuando llegue el momento de llenar la base de datos, cuente el número de dígitos <50,000 y el número de dígitos> = 50,000. Asigne dos arreglos de uint16 de longitud apropiada: uno para los enteros inferiores a 50,000 y uno para el conjunto superior. Al almacenar enteros en la matriz superior, reste 50,000 y cuando lea enteros de esa matriz, agregue 50,000. Ahora ha almacenado sus 1,000 enteros en 2,000 palabras de 8 bytes.

La construcción de la agenda requerirá dos recorridos de entrada, pero las búsquedas deberían ocurrir en la mitad del tiempo, en promedio, de lo que lo harían con una sola matriz. Si el tiempo de búsqueda fuera muy importante, podrías usar más arreglos para rangos más pequeños, pero creo que en estos tamaños tu rendimiento estaría tirando de las matrices de la memoria y 2k probablemente se esconda en la memoria caché de la CPU si no registras nada. dias.

Si es dinámico , asigne una matriz de 1000 o menos uint16 , y agregue los números en orden ordenado. Establezca el primer byte en 50,001 y establezca el segundo byte en un valor nulo apropiado, como NULL o 65,000. Cuando almacene los números, guárdelos en orden ordenado. Si un número está por debajo de 50,001, guárdelo antes del marcador 50,001. Si un número es 50,001 o superior, guárdelo después del marcador 50,001, pero reste 50,000 del valor almacenado.

Su matriz se verá algo así como:

00001 = 00001 12345 = 12345 50001 = reserved 00001 = 50001 12345 = 62345 65000 = end-of-list

Por lo tanto, cuando busca un número en la agenda telefónica, recorrerá la matriz y si ha alcanzado el valor 50,001, comenzará agregando 50,000 a los valores de la matriz.

Esto hace que los encartes sean muy caros, pero las búsquedas son fáciles, y no gastará mucho más de 2k en almacenamiento.

Probablemente consideraría usar alguna versión comprimida de un Trie (posiblemente un http://en.wikipedia.org/wiki/Acyclic_deterministic_finite_automaton como lo sugirió @Misha).

Eso automágicamente se aprovecharía del hecho de que todos tienen un prefijo común.

La búsqueda se realizará en tiempo constante, y la impresión se realizará en tiempo lineal.

Solo para preguntar rápidamente cualquier razón por la que no queremos cambiar los números a una base 36. Puede que no ahorre tanto espacio, pero seguramente ahorrará tiempo en la búsqueda ya que verá mucho menos que 10 dígitos. O los dividiría en archivos según cada grupo. así que nombraría un archivo (111) -222.txt y luego solo almacenaría los números que se ajustan a ese grupo y luego los haré seearcables en orden numérico, de esta manera siempre puedo chatear para ver si el archivo sale. antes de ejecutar una búsqueda biger. o para ser correctos, correría a búsquedas binarias, una para el archivo para ver si sale. y otra búsqueda bonary sobre el contenido del archivo

Tomando esto como un problema puramente teórico y dejando a la implementación como una alternativa, la forma más eficiente es simplemente indexar todos los conjuntos posibles de 10000 últimos dígitos en una tabla de indexación gigantesca. Suponiendo que tiene exactamente 1000 números, necesitaría un poco más de 8000 bits para identificar de manera única el conjunto actual. No hay compresión más grande posible, porque entonces tendría dos conjuntos que están identificados con el mismo estado.

Los problemas con esto es que tendría que representar cada uno de los 2 ^ 8000 conjuntos en su programa como un lut, y ni siquiera Google sería remotamente capaz de esto.

La búsqueda sería O (1), imprimiendo todos los números O (n). La inserción sería O (2 ^ 8000) que en teoría es O (1), pero en la práctica es inutilizable.

En una entrevista, solo daría esta respuesta, si estoy seguro, que la compañía está buscando a alguien que pueda pensar mucho de la caja. De lo contrario, esto podría hacerte parecer un teórico sin preocupaciones reales del mundo.

EDITAR : Ok, aquí hay una "implementación".

Pasos para construir la implementación:

Tome una matriz constante de tamaño 100 000 * (1000 elije 100 000) bits. Sí, soy consciente del hecho de que esta matriz necesitará más espacio que los átomos en el universo en varias magnitudes.
Separe esta gran matriz en trozos de 100 000 cada uno.
En cada fragmento, almacene una matriz de bits para una combinación específica de los últimos cinco dígitos.

Este no es el programa, sino una especie de meta programa, que construirá una LUT gigantesca que ahora se puede usar en un programa. Las cosas constantes del programa normalmente no se cuentan al calcular la eficiencia del espacio, por lo que no nos importan estos arreglos cuando hacemos nuestros cálculos finales.

Aquí está cómo usar esta LUT:

Cuando alguien te da 1000 números, almacenas los primeros cinco dígitos por separado.
Averigua cuál de los fragmentos de tu matriz coincide con este conjunto.
Almacene el número del conjunto en un solo número de 8074 bit (llame a este c).

Esto significa que para el almacenamiento solo necesitamos 8091 bits, que hemos demostrado que es la codificación óptima. Sin embargo, encontrar el trozo correcto toma O (100 000 * (100 000 elije 1000)), que según las reglas matemáticas es O (1), pero en la práctica siempre llevará más tiempo que el tiempo del universo.

La búsqueda es simple:

tira de los primeros cinco dígitos (el número restante se llamará n '').
prueba si coinciden
Calcular i = c * 100000 + n ''
Compruebe si el bit en i en la LUT está configurado en uno

Imprimir todos los números es simple también (y toma O (100000) = O (1) en realidad, porque siempre debe verificar todos los bits del fragmento actual, por lo que calculé mal esto anteriormente).

No llamaría esto una "implementación", debido a la descarada indiferencia de las limitaciones (el tamaño del universo y el tiempo que ha vivido este universo o existirá esta tierra). Sin embargo, en teoría, esta es la solución óptima. Para problemas más pequeños, esto realmente se puede hacer, y algunas veces se hará. Por ejemplo, las redes de clasificación son un ejemplo para esta forma de codificación, y se pueden usar como un paso final en los algoritmos de clasificación recursiva, para obtener una gran aceleración.

http://en.wikipedia.org/wiki/Acyclic_deterministic_finite_automaton

Una vez tuve una entrevista en la que me preguntaron acerca de las estructuras de datos. Olvidé "Matriz".

Almacenamiento fijo de 1073 bytes para 1,000 números:

El formato básico de este método de almacenamiento es almacenar los primeros 5 dígitos, un conteo para cada grupo y el desplazamiento para cada número en cada grupo.

Prefijo:
Nuestro prefijo de 5 dígitos ocupa los primeros 17 bits .

Agrupamiento:
A continuación, tenemos que encontrar una agrupación de buen tamaño para los números. Probemos tener aproximadamente 1 número por grupo. Como sabemos que hay alrededor de 1000 números para almacenar, dividimos 99.999 en aproximadamente 1000 partes. Si seleccionamos el tamaño del grupo como 100, habría bits desperdiciados, intentemos con un tamaño de grupo de 128, que se puede representar con 7 bits. Esto nos da 782 grupos para trabajar.

Cuenta:
A continuación, para cada uno de los 782 grupos, necesitamos almacenar el recuento de entradas en cada grupo. Un recuento de 7 bits para cada grupo arrojaría 7*782=5,474 bits , lo que es muy ineficiente porque el número promedio representado es aproximadamente 1 debido a la forma en que elegimos nuestros grupos.

Por lo tanto, en su lugar tenemos recuentos de tamaño variable con 1s principales para cada número en un grupo seguido de 0. Por lo tanto, si tuviéramos x números en un grupo, tendríamos x 1''s seguidos de un 0 para representar el recuento. Por ejemplo, si tuviéramos 5 números en un grupo, el conteo estaría representado por 111110 . Con este método, si hay 1,000 números terminamos con 1000 1''s y 782 0''s para un total de 1000 + 782 = 1,782 bits para los conteos .

Compensar:
Por último, el formato de cada número será el desplazamiento de 7 bits para cada grupo. Por ejemplo, si 00000 y 00001 son los únicos números en el grupo 0-127, los bits para ese grupo serían 110 0000000 0000001 . Suponiendo 1,000 números, habrá 7,000 bits para los desplazamientos .

Por lo tanto, nuestro recuento final suponiendo 1,000 números es el siguiente:

17 (prefix) + 1,782 (counts) + 7,000 (offsets) = 8,799 bits = 1100 bytes

Ahora, veamos si nuestra selección del tamaño de grupo al redondear hasta 128 bits fue la mejor opción para el tamaño del grupo. Al elegir x como el número de bits para representar cada grupo, la fórmula para el tamaño es:

Size in bits = 17 (prefix) + 1,000 + 99,999/2^x + x * 1,000

Al minimizar esta ecuación para valores enteros de x obtiene x=6 , que arroja 8,580 bits = 1,073 bytes . Por lo tanto, nuestro almacenamiento ideal es el siguiente:

Tamaño del grupo: 2 ^ 6 = 64
Cantidad de grupos: 1,562
Almacenamiento total:
1017 (prefix plus 1''s) + 1563 (0''s in count) + 6*1000 (offsets) = 8,580 bits = 1,073 bytes