La forma más eficiente de almacenar miles de números de teléfono

Esta es una pregunta de la entrevista de Google:

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

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

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

¿Podría ayudar el uso de un sufijo trie?

Idealmente, almacenar 1000 números toma 4 bytes por número, por lo que en total se necesitarían 4000 bytes para almacenar 1000 números. Cuantitativamente, deseo reducir el almacenamiento a <4000 bytes, esto es lo que me explicó mi entrevistador.

Aquí hay una mejora a la respuesta de aix . Considere utilizar 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, a cada número de teléfono solo le quedan los cinco dígitos restantes. Consideramos 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 consta de los primeros m bits es todo 0, para cuántos números de teléfono los primeros m bits son como máximo 0 ... 01, para cuántos números de teléfono los primeros m los bits son como máximo 0 ... 10, etcétera, hasta el recuento de números de teléfono para los que los primeros m bits son 1 ... 11; este último recuento es 1000 (decimal). Hay 2 ^ m de tales conteos y cada conteo 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 son suficientes para almacenar un número menor que 1024).

Los últimos k bits de todos los números de teléfono (reducidos) se almacenan de forma contigua en la memoria; así que 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 de 11287 para k = 10. De modo que podemos almacenar todos los números de teléfono en ceil ( 11287/8) = 1411 bytes.

Se puede ahorrar espacio adicional observando que ninguno de nuestros números puede comenzar con, por ejemplo, 1111111 (binario), porque el número más bajo que comienza con ese es 130048 y solo tenemos cinco dígitos decimales. Esto nos permite eliminar 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 en

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

que sorprendentemente alcanza su mínimo 10997 para k = 9 y k = 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 m bits número M ) y su inferior k = 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 del primer bloque de bits. Ahora comprobamos entre un[M-1] ésima y una [M] ésima secuencia 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).

Pseudocódigo para imprimir todos los números 1000 sigue, donde accedo a la K 'th k bits de entrada del primer bloque de la memoria como una [K] y el M ' th m entrada bits del segundo bloque de la memoria como b [M] (ambos requerirían algunas operaciones de bits 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;

Tal vez algo salga mal con el caso de límite para K = ceil (99999/2 ^ k ), pero eso es bastante fácil de solucionar.

Finalmente, desde el punto de vista de la entropía, no es posible almacenar un subconjunto de 10 ^ 3 enteros positivos todos menores de 10 ^ 5 en menos de 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 en las que aún puede acceder a los números de manera relativamente eficiente.

En lo que sigue, trato los números como variables enteras (en lugar de cadenas):

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

En resumen: 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 almacenado en orden ascendente.

En total, estamos buscando 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).

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

Una vez tuve una entrevista en la que preguntaron sobre estructuras de datos. Olvidé "Array".

Probablemente consideraría usar alguna versión comprimida de un Trie (posiblemente un DAWG como lo sugiere @Misha).

Eso aprovecharía automáticamente el 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.

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

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

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

EDITAR: Una estimación para la codificación de Rice con base 128 (no porque dé los mejores resultados, sino porque es más fácil de calcular):

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

valor unario value / 128(número variable de bits + 1 bit como terminador)
valor binario para 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 que 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 la 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.

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

Solución: quita los primeros cinco dígitos de los números, ya que son los mismos para todos los números. Luego use operaciones bit a bit para representar el valor posible restante de 9999. Solo necesitará 2 ^ 17 Bits para representar los números. Cada bit representa un número. Si el bit está establecido, el número está en la agenda telefónica.

Para imprimir todos los números, simplemente imprima todos los números donde se establece el bit concatenado con el prefijo. Para buscar un número dado, haga la aritmética de bits 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 bits.

HTH Chris.

Almacenamiento fijo de 1073 bytes para 1000 números:

El formato básico de este método de almacenamiento es almacenar los primeros 5 dígitos, un recuento 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 .

Agrupación:
A continuación, debemos encontrar una agrupación de números de buen tamaño. Intentemos tener alrededor de 1 número por grupo. Como sabemos que hay alrededor de 1000 números para almacenar, dividimos 99,999 en alrededor de 1000 partes. Si elegimos el tamaño del grupo como 100, se perderían bits, así que probemos con un tamaño de grupo de 128, que se puede representar con 7 bits. Esto nos da 782 grupos con los que trabajar.

Recuentos:
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 produciría 7*782=5,474 bits, lo cual es muy ineficiente porque el número promedio representado es aproximadamente 1 debido a cómo elegimos nuestros grupos.

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

Desplazamiento: Por
último, el formato de cada número será solo 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 las compensaciones .

Por tanto, nuestro recuento final, asumiendo 1.000 números, es el siguiente:

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

Ahora, verifiquemos si nuestra selección de tamaño de grupo redondeando a 128 bits fue la mejor opción para el tamaño de grupo. Al elegir xel 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

Minimizando esta ecuación para valores enteros de xda x=6, lo que produce 8.580 bits = 1.073 bytes . Por tanto, nuestro almacenamiento ideal es el siguiente:

• Tamaño del grupo: 2 ^ 6 = 64
• Número 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

Tomando esto como un problema puramente teórico y dejando de lado la implementación, 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 forma única el conjunto actual. No es posible una compresión mayor, porque entonces tendrías dos conjuntos que se identifican con el mismo estado.

El problema 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 capaz de hacerlo remotamente.

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 estuviera seguro, de que la empresa está buscando a alguien que sea capaz de pensar mucho. De lo contrario, esto podría hacer que parezca un teórico sin preocupaciones del mundo real.

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

Pasos para construir la implementación:

1. Tome una matriz constante de tamaño 100 000 * (1000 elija 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.
2. Separe esta gran matriz en trozos de 100 000 cada uno.
3. 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 metaprograma, 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 importa esta matriz cuando hacemos nuestros cálculos finales.

A continuación se explica cómo utilizar esta LUT:

1. Cuando alguien le da 1000 números, almacena los primeros cinco dígitos por separado.
2. Descubra cuál de los trozos de su matriz coincide con este conjunto.
3. Almacene el número del conjunto en un solo número de 8074 bits (llámelo c).

Esto significa que para el almacenamiento solo necesitamos 8091 bits, que aquí hemos demostrado que es la codificación óptima. Sin embargo, encontrar el fragmento correcto requiere O (100 000 * (100 000 elija 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.

Sin embargo, la búsqueda es simple:

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

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

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

Esto equivale a almacenar mil enteros no negativos cada uno de menos de 100.000. Podemos usar algo como codificación aritmética para hacer esto.

En última instancia, los números se almacenarán en una lista ordenada. Observo 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 sencilla de representar estos casos menos comunes es adoptar el esquema utf-8 donde un byte representa un entero de 7 bits a menos que el primer bit esté establecido, en cuyo caso el siguiente byte se lee para producir un entero de 14 bits, a menos que se establece su primer bit, en cuyo caso se lee el siguiente byte para representar un entero de 21 bits.

Por 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. Algunos 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 medio será de unos 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.

Solo para preguntar rápidamente cualquier razón por la que no quisiéramos cambiar los números a una base 36. Puede que no ahorre tanto espacio, pero sin duda ahorrará tiempo en la búsqueda, ya que estará viendo mucho menos de 10 dígitos. O los dividiría en archivos dependiendo de cada grupo. así que nombraría un archivo (111) -222.txt y luego solo almacenaría los números que encajan en ese grupo allí y luego los haría buscar en orden numérico de esta manera siempre puedo chack para ver si el archivo sale. antes de ejecutar una búsqueda más grande. o para ser correcto, ejecutaría una búsqueda binaria para el archivo para ver si sale. y otra búsqueda bastante en el contenido del archivo

¿Por qué no hacerlo simple? Utilice una matriz de estructuras.

Entonces podemos guardar los primeros 5 dígitos como una constante, así que olvídelos por ahora.

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

Usar tipos de datos de 32 bits es una pérdida 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.

Suponiendo 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 matemáticos simples a nivel de bits

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

Y la inversa

//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, querríamos una matriz ordenada. Entonces, cuando se guarden los números, ordene la matriz (yo elegiría una clasificación de combinación personalmente, O (nlogn)). Ahora, para buscar, optaría por un enfoque de combinación de tipos. Divida la matriz y vea en cuál se encuentra nuestro número. Luego llame a la función solo en esa matriz. Haga esto de forma recursiva 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 aún mejor que O (nlogn), ya que se ejecutará absolutamente en menos tiempo que el tipo de combinación (solo recuperó 1 lado de la división cada vez, en lugar de ambos lados :)), que es O (nlogn).

Mi solución: el mejor de los casos 7.025 bits / número, el peor de los casos 14.193 bits / número, promedio aproximado de 8.551 bits / número. Stream-codificado, sin acceso aleatorio.

Incluso antes de leer la respuesta de ruslik, inmediatamente pensé en codificar la diferencia entre cada número, ya que será pequeño y debería ser relativamente consistente, pero la solución también debe poder adaptarse 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 mayor que el número anterior en 100:

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

Si ese fuera el caso, requeriría almacenamiento cero para codificar las diferencias entre 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 en 103, codificaría el número 3 y si dos números adyacentes difieren en 92, I codificaría -8. Yo llamo al delta de un incremento ideal de 100 la " varianza ".

La variación puede variar de -99 (es decir, dos números consecutivos) a 99000 (toda la agenda telefónica 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 intentar asignar un almacenamiento mínimo para codificar las diferencias más comunes y ampliar el almacenamiento, si me encuentro con diferencias más grandes (como protobuf ‘s varint). Usaré fragmentos de siete bits, seis para almacenamiento y un bit de bandera adicional al final para indicar que esta variación se almacena con un fragmento adicional después del actual, hasta un máximo de tres fragmentos (que proporcionarán un máximo de 3 * 6 = 18 bits de almacenamiento, que son 262144 valores posibles, más que el número de posibles variaciones (99100). Cada fragmento adicional que sigue a una bandera elevada tiene bits de mayor importancia, por lo que el primer fragmento siempre tiene bits 0- 5, el segundo fragmento opcional tiene los bits 6-11, y el tercer fragmento opcional tiene los bits 12-17.

Un solo fragmento proporciona seis bits de almacenamiento que pueden albergar 64 valores. Me gustaría mapear las 64 variaciones más pequeñas para que quepan en ese único fragmento (es decir, variaciones de -32 a +31), así que usaré la codificación ProtoBuf ZigZag, hasta las variaciones de -99 a +98 (ya que no es necesario para una variación negativa más allá de -99), momento en el que cambiaré a la codificación normal, compensada por 98:  

Varianza | Valor codificado
----------- + ----------------
    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 | sesenta y cinco
   33 | 66
   ... | ...
  -98 | 195
   98 | 196
  -99 | 197
----------- | --------------- Fin de 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 variaciones se codificarían como bits, incluida la bandera para indicar un fragmento adicional:

Varianza | Bits codificados
----------- + ----------------
     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 telefónica de muestra se codificarían como un flujo 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 está distribuida de manera algo uniforme y no hay dos números de teléfono que tengan una variación mayor que 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 de teléfono se ajusta a una parte (800 * 7 = 5600), 180 números caben en dos partes cada uno (180 * 2 * 7 = 2520) y 19 números caben en tres partes cada uno (20 * 3 * 7 = 399), más los 32 bits iniciales, suman 8551 bits .
En el peor de los casos , 25 números caben en tres partes (25 * 3 * 7 = 525 bits) y los 974 números restantes caben en dos partes (974 * 2 * 7 = 13636 bits), más 32 bits para el primer número de un gran Total de14193 bits .

   Cantidad de números codificados |
 1 trozo | 2 trozos | 3 trozos | Bits totales
--------- + ---------- + ---------- + ------------
   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:

1. El tercer fragmento no necesita los siete bits completos, puede ser solo de cinco bits y sin un bit de bandera.
2. Puede haber un pase inicial de los números para calcular los mejores tamaños para cada fragmento. Tal vez para un directorio telefónico determinado, 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 conjuntos de tres bits para almacenar los tamaños de los fragmentos 1 y 2 (el tamaño del fragmento 3 es el resto de los 16 bits requeridos) para un total de 6032 bits!
3. El mismo paso inicial puede calcular un incremento esperado mejor que el valor predeterminado 100. Tal vez haya una guía telefónica que comience en 55555-50000, por lo que tenga la mitad del rango de números, por lo que el incremento esperado debería ser 50. O tal vez haya una guía no lineal Se puede utilizar la distribución (desviación estándar tal vez) y algún otro incremento esperado óptimo. Esto reduciría la variación típica y podría permitir el uso de un primer fragmento aún más pequeño.
4. Se pueden realizar más análisis en la primera pasada para permitir la partición de la guía telefónica, con cada partición con su propio incremento esperado y optimizaciones de tamaño de fragmento. Esto permitiría un tamaño de primer fragmento más pequeño para ciertas partes altamente uniformes de la guía telefónica (reduciendo el número de bits consumidos) y tamaños de fragmentos más grandes para partes no uniformes (reduciendo el número de bits desperdiciados en indicadores de continuación).

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

El truco es que necesitaría 17 bits para almacenar el rango de números de 0 a 99,999. Pero almacenar 17 bits en límites de palabras convencionales de 8 bytes es complicado. Es por eso que preguntan si puede hacerlo en menos de 4k sin 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 65.000 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 prefijos de intercambio.

Pregunta: ¿Esta lista será estática o deberá admitir actualizaciones?

Si es estático , cuando llegue el momento de completar la base de datos, cuente el número de dígitos <50.000 y el número de dígitos> = 50.000. Asigne dos matrices de uint16la longitud adecuada: una para los números enteros por debajo de 50.000 y otra para el conjunto superior. Al almacenar enteros en la matriz superior, reste 50.000 y cuando lea enteros de esa matriz, sume 50.000. Ahora ha almacenado sus 1,000 enteros en 2,000 palabras de 8 bytes.

La construcción de la guía telefónica requerirá dos recorridos de entrada, pero las búsquedas deberían realizarse en la mitad del tiempo, en promedio, que con una sola matriz. Si el tiempo de búsqueda fuera muy importante, podría usar más matrices para rangos más pequeños, pero creo que en estos tamaños su límite de rendimiento sería extraer las matrices de la memoria y 2k probablemente se guardará en el caché de la CPU si no registra espacio en cualquier cosa que esté usando. dias.

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

Tu matriz se verá así:

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

Entonces, cuando busca un número en la agenda, recorrerá la matriz y si ha alcanzado el valor de 50,001, comenzará a agregar 50,000 a los valores de su matriz.

Esto hace que las inserciones sean muy caras, pero las búsquedas son fáciles y no va a gastar mucho más de 2000 en almacenamiento.