71 votos

almacenamiento de 1 millón de números de teléfono

¿Cuál es la manera más eficiente, memoria-sabio, a la tienda de 1 millón de números de teléfono? Al parecer, esta es una pregunta de la entrevista en Google,por favor comparta sus ideas..

44voto

Rob Leclerc Puntos 375

Si la memoria es nuestra mayor consideración, entonces no necesitamos para almacenar el número en absoluto, sólo la diferencia entre i e i+1.

Ahora si los números van de 200 0000 - 999 9999, entonces hay 7,999,999 posibles números de teléfono. Ya tenemos de 1 millón de números, y si asumimos que son distribuidos de manera uniforme, tenemos una distancia Esperada de E = n_i+1 - n_i ~ 8 (3 bits) entre el número secuencial de n_i y n_i+1. Así que para una de 32 bits int potencialmente podríamos almacenar hasta 10 secuencial compensaciones (~400kb óptimo total de la huella de memoria), sin embargo es probable que tengamos algunos casos donde necesitamos un desplazamiento mayor de 8 (tal vez tenemos 400, o 1500??). En cuyo caso, simplemente se puede hacer la reserva de los 2 primeros bits de la int como un encabezado que nos dice lo que el tamaño de fotograma de la usamos para leer los bits que se almacena. Por ejemplo, tal vez utilizamos: 00 = 3x10, 01 = 5x6, 10 = 7x4, 11 = 1*30.

29voto

Steve Jessop Puntos 166970

Escribir en ASCII, separados por espacios.

Postal de la cadena resultante, con su favorito algoritmo de compresión. Si el orden no es importante, la clasificación de primera podría ayudar a la compresión, da más la repetición de más cerca.

Oh, ¿quieres eficiente de acceso aleatorio? Entonces usted debería haber dicho.

10voto

6502 Puntos 42700

Una posible solución es

  1. ordenar los números
  2. codificar los deltas de un número al siguiente

Delta la distribución de la frecuencia va a ser muy desigual.

He hecho un experimento utilizando un simple BER-como el embalaje de enfoque para los deltas el uso de un 7+3+3+... bits de codificación; codifica la función

def delta_write(x, b1, b2):
    lim = 1 << (b1 - 1)
    if x < lim:
        bit_write(x, b1)
    else:
        bit_write(lim + (x & (lim - 1)), b1)
        delta_write(x >> (b1 - 1), b2, b2)

(los dos parámetros de 7 y 3 se determinaron experimentalmente)

Con este enfoque, tengo un millón de 10-dígitos de los números con los 5 primeros dígitos elegidos de un millar de azar prefijos con un promedio de del 8,83 bits por número (bolsas de tamaño 1104188).

7voto

CodesInChaos Puntos 60274

Primero observo que nunca comenzar con 0, ya que 0 es utilizado como carácter de escape en el principio. Así que simplemente respecto de los números de teléfono como números enteros. Si esto no fuera el caso, yo simplemente le antepone un "1" al número y, a continuación, convertirlo a entero. Esto no afectará a la eficacia de la codificación de forma significativa(Probablemente la constante sobrecarga de unos pocos bytes). Si hay otros personajes fuera de los 10 dígitos dentro de los números de teléfono que sólo codifican con una base mayor que 10. Esto le va a doler la eficiencia, aunque.

Me gustaría ordenarlas por tamaño ascendente. A continuación, calcular las diferencias. Y, a continuación, serializar las diferencias con protobuf como lleno de campos repetidos.

Este método es similar a la RexKerr del método, excepto yo uso el perezoso solución de protobuf a través de un codificador de huffman. Probablemente un poco más grande ya que el protobuf entero codificar es de propósito general y no toma de la distribución de probabilidad de los números de teléfono en cuenta. Pero es mucho más fácil de código ya que sólo necesita usar una existente protobuf serializador. De esta manera se consigue problemática una vez que se excede el tamaño de un UInt64, es decir no son los números de teléfono de más de 19 dígitos. El formato de archivo que aún lo apoya, pero la mayoría de las implementaciones no.

Sin un índice de acceso veces va a ser muy malo, pero debe ser bastante compacto.

7voto

Rex Kerr Puntos 94401

La codificación Huffman en bloques de dígitos probablemente iba a dar muy buenos resultados. Si los números fueron de tipo mixto (por ejemplo, algunos de los EE.UU., algunos en el extranjero, incluyendo el código de acceso) tendría otro par de bits para especificar qué tipo eran (y por lo tanto que los bloques a utilizar).

Si los números fueron en algún pequeño campo de tiro, por ejemplo, de siete dígitos--el más compacto de camino a la tienda de ellos probablemente sería tratarlos como enteros, ordenar y almacenar (Huffman-codificado) las diferencias en los valores. E. g. con 10^6 números de 7 dígitos (10^7 posibilidades), se podría esperar que necesita acerca de log2(10) ~= 3.3 bits por número.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X