Le moyen le plus efficace de stocker des milliers de numéros de téléphone

Ceci est une question d'entrevue Google:

Il y a environ un millier de numéros de téléphone à stocker, chacun comportant 10 chiffres. Vous pouvez supposer que les 5 premiers chiffres de chacun sont identiques sur mille nombres. Vous devez effectuer les opérations suivantes: a. Rechercher si un nombre donné existe. b. Imprimer tout le numéro

Quelle est la manière la plus efficace d'économiser de l'espace pour ce faire?

J'ai répondu à la table de hachage et au codage Huffman plus tard, mais mon intervieweur a dit que je n'allais pas dans la bonne direction. Veuillez m'aider ici.

L'utilisation d'un suffixe pourrait-elle aider?

Idéalement, le stockage de 1000 numéros prend 4 octets par numéro, donc en tout, il faudrait 4000 octets pour stocker 1000 numéros. Quantitativement, je souhaite réduire le stockage à <4000 octets, c'est ce que m'a expliqué mon intervieweur.

Voici une amélioration de la réponse d' Aix . Envisagez d'utiliser trois "couches" pour la structure de données: la première est une constante pour les cinq premiers chiffres (17 bits); donc à partir de maintenant, chaque numéro de téléphone n'a plus que les cinq chiffres restants. Nous considérons ces cinq chiffres restants comme des entiers binaires de 17 bits et stockons k de ces bits en utilisant une méthode et 17 - k = m avec une méthode différente, en déterminant k à la fin pour minimiser l'espace requis.

Nous trions d'abord les numéros de téléphone (tous réduits à 5 chiffres décimaux). Ensuite, nous comptons combien de numéros de téléphone il y a pour lesquels le nombre binaire composé des m premiers bits est tout 0, pour combien de numéros de téléphone les m premiers bits sont au plus 0 ... 01, pour combien de numéros de téléphone les premiers m les bits sont au plus 0 ... 10, etc., jusqu'au nombre de numéros de téléphone pour lesquels les m premiers bits sont 1 ... 11 - ce dernier compte est 1000 (décimal). Il y a 2 ^ m de ces nombres et chaque compte est au maximum de 1000. Si nous omettons le dernier (parce que nous savons qu'il est de toute façon 1000), nous pouvons stocker tous ces nombres dans un bloc contigu de (2 ^ m - 1) * 10 bits. (10 bits suffisent pour stocker un nombre inférieur à 1024.)

Les k derniers bits de tous les numéros de téléphone (réduits) sont stockés de manière contiguë dans la mémoire; donc si k est, disons, 7, alors les 7 premiers bits de ce bloc de mémoire (bits 0 à 6) correspondent aux 7 derniers bits du premier numéro de téléphone (réduit), les bits 7 à 13 correspondent aux 7 derniers bits du deuxième numéro de téléphone (réduit), etc. Cela nécessite 1000 * k bits pour un total de 17 + (2 ^ (17 - k ) - 1) * 10 + 1000 * k , ce qui atteint son minimum de 11287 pour k = 10. Nous pouvons donc stocker tous les numéros de téléphone dans ceil ( 11287/8) = 1411 octets.

De l'espace supplémentaire peut être économisé en observant qu'aucun de nos nombres ne peut commencer par exemple par 1111111 (binaire), car le plus petit nombre commençant par cela est 130048 et nous n'avons que cinq chiffres décimaux. Cela nous permet de raser quelques entrées du premier bloc de mémoire: au lieu de 2 ^ m - 1 compte, nous n'avons besoin que de ceil (99999/2 ^ k ). Cela signifie que la formule devient

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

qui atteint étonnamment son minimum de 10997 pour k = 9 et k = 10, ou ceil (10997/8) = 1375 octets.

Si nous voulons savoir si un certain numéro de téléphone est dans notre ensemble, nous vérifions d'abord si les cinq premiers chiffres binaires correspondent aux cinq chiffres que nous avons stockés. Ensuite, nous divisons les cinq chiffres restants en son haut m = 7 bits (qui est, par exemple, le nombre à m bits M ) et son k inférieur = 10 bits (le nombre K ). On trouve maintenant le nombre a [M-1] de numéros de téléphone réduits dont les m premiers chiffres sont au plus M - 1, et le nombre a [M] de numéros de téléphone réduits dont les m premiers chiffres sont au plus M , les deux à partir du premier bloc de bits. Nous vérifions maintenant entre un[M-1] ème et une [M] ème séquence de k bits dans le deuxième bloc de mémoire pour voir si on trouve K ; dans le pire des cas, il y a 1000 de ces séquences, donc si nous utilisons la recherche binaire, nous pouvons terminer par des opérations O (log 1000).

Le pseudo-code pour imprimer les 1000 nombres suit, où j'accède à l'entrée K 'ème k bits du premier bloc de mémoire comme a [K] et à l' entrée M ' ème m bits du deuxième bloc de mémoire comme b [M] (les deux nécessiteraient quelques opérations binaires qui sont fastidieuses à écrire). Les cinq premiers chiffres sont dans le nombre 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;

Peut-être que quelque chose ne va pas avec le cas de limite pour K = ceil (99999/2 ^ k ), mais c'est assez facile à corriger.

Enfin, d'un point de vue entropique, il n'est pas possible de stocker un sous-ensemble de 10 ^ 3 entiers positifs tous inférieurs à 10 ^ 5 dans moins de ceil (log [2] (binomial (10 ^ 5, 10 ^ 3)) ) = 8073. En incluant les 17 dont nous avons besoin pour les 5 premiers chiffres, il y a toujours un écart de 10997 - 8090 = 2907 bits. C'est un défi intéressant de voir s'il existe de meilleures solutions où vous pouvez toujours accéder aux numéros de manière relativement efficace!

Dans ce qui suit, je traite les nombres comme des variables entières (par opposition aux chaînes):

1. Triez les nombres.
2. Divisez chaque numéro en les cinq premiers chiffres et les cinq derniers chiffres.
3. Les cinq premiers chiffres sont les mêmes pour tous les nombres, alors stockez-les une seule fois. Cela nécessitera 17 bits de stockage.
4. Stockez les cinq derniers chiffres de chaque numéro individuellement. Cela nécessitera 17 bits par nombre.

Pour récapituler: les 17 premiers bits sont le préfixe commun, les 1000 groupes suivants de 17 bits sont les cinq derniers chiffres de chaque nombre stockés dans l'ordre croissant.

Au total, nous examinons 2128 octets pour les 1000 numéros, ou 17,017 bits par numéro de téléphone à 10 chiffres.

La recherche est O(log n)(recherche binaire) et l'énumération complète est O(n).

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

J'ai eu une fois une interview où ils ont posé des questions sur les structures de données. J'ai oublié "Array".

J'envisagerais probablement d'utiliser une version compressée d'un Trie (peut-être un DAWG comme suggéré par @Misha).

Cela profiterait automatiquement du fait qu'ils ont tous un préfixe commun.

La recherche sera effectuée en temps constant et l'impression sera effectuée en temps linéaire.

J'ai déjà entendu parler de ce problème (mais sans l'hypothèse des 5 premiers chiffres sont les mêmes), et le moyen le plus simple de le faire était le codage du riz :

1) Comme l'ordre n'a pas d'importance, nous pouvons les trier et ne conserver que les différences entre les valeurs consécutives. Dans notre cas, les différences moyennes seraient de 100.000 / 1000 = 100

2) Encodez les différences en utilisant les codes Rice (base 128 ou 64) ou même les codes Golomb (base 100).

EDIT: Une estimation pour le codage Rice avec base 128 (non pas parce que cela donnerait les meilleurs résultats, mais parce que c'est plus facile à calculer):

Nous enregistrerons la première valeur telle quelle (32 bits).
Le reste des 999 valeurs sont des différences (nous nous attendons à ce qu'elles soient petites, 100 en moyenne) contiendront:

valeur unaire value / 128(nombre variable de bits + 1 bit comme terminateur)
valeur binaire pour value % 128(7 bits)

Nous devons en quelque sorte estimer les limites (appelons-le VBL) pour le nombre de bits variables:
limite inférieure: considérez que nous sommes chanceux, et aucune différence n'est plus grande que notre base (128 dans ce cas). cela signifierait donner 0 bits supplémentaires.
limite haute: puisque toutes les différences plus petites que la base seront encodées en partie binaire du nombre, le nombre maximum dont nous aurions besoin pour encoder en unaire est 100000/128 = 781,25 (encore moins, car nous ne nous attendons pas à ce que la plupart des différences soient nulles ).

Ainsi, le résultat est 32 + 999 * (1 + 7) + variable (0..782) bits = 1003 + variable (0..98) octets.

C'est un problème bien connu des perles de programmation de Bentley.

Solution: supprimez les cinq premiers chiffres des nombres car ils sont identiques pour chaque numéro. Utilisez ensuite des opérations au niveau du bit pour représenter les 9999 valeurs possibles restantes. Vous n'aurez besoin que de 2 ^ 17 bits pour représenter les nombres. Chaque bit représente un nombre. Si le bit est activé, le numéro se trouve dans le carnet de téléphonie.

Pour imprimer tous les nombres, imprimez simplement tous les nombres où le bit est défini concaténés avec le préfixe. Pour rechercher un nombre donné, effectuez l'arithmétique binaire nécessaire pour vérifier la représentation binaire du nombre.

Vous pouvez rechercher un nombre dans O (1) et l'efficacité de l'espace est maximale en raison de la représentation des bits.

HTH Chris.

Stockage fixe de 1073 octets pour 1000 numéros:

Le format de base de cette méthode de stockage est de stocker les 5 premiers chiffres, un compte pour chaque groupe et le décalage pour chaque numéro dans chaque groupe.

Préfixe:
notre préfixe à 5 chiffres occupe les 17 premiers bits .

Regroupement:
Ensuite, nous devons trouver un groupement de bonne taille pour les nombres. Essayons d'avoir environ 1 numéro par groupe. Puisque nous savons qu'il y a environ 1000 numéros à stocker, nous divisons 99 999 en environ 1000 parties. Si nous choisissons une taille de groupe de 100, il y aurait des bits perdus, alors essayons une taille de groupe de 128, qui peut être représentée avec 7 bits. Cela nous donne 782 groupes avec lesquels travailler.

Comptes:
Ensuite, pour chacun des 782 groupes, nous devons stocker le nombre d'entrées dans chaque groupe. Un décompte de 7 bits pour chaque groupe donnerait 7*782=5,474 bits, ce qui est très inefficace car le nombre moyen représenté est d'environ 1 en raison de la façon dont nous avons choisi nos groupes.

Ainsi, au lieu de cela, nous avons des xnombres de taille variable avec des 1 en tête pour chaque nombre d'un groupe suivi d'un 0. Ainsi, si nous avions des nombres dans un groupe, nous aurions x 1'ssuivi d'un 0pour représenter le nombre. Par exemple, si nous avions 5 nombres dans un groupe, le nombre serait représenté par 111110. Avec cette méthode, s'il y a 1000 nombres, nous nous retrouvons avec 1000 1 et 782 0 pour un total de 1000 + 782 = 1 782 bits pour les comptes .

Décalage:
Enfin, le format de chaque nombre sera juste le décalage de 7 bits pour chaque groupe. Par exemple, si 00000 et 00001 sont les seuls nombres du groupe 0-127, les bits de ce groupe seront 110 0000000 0000001. En supposant 1 000 nombres, il y aura 7 000 bits pour les décalages .

Ainsi notre décompte final en supposant 1000 nombres est le suivant:

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

Maintenant, vérifions si notre sélection de taille de groupe en arrondissant à 128 bits était le meilleur choix pour la taille de groupe. En choisissant xle nombre de bits pour représenter chaque groupe, la formule de la taille est:

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

Minimiser cette équation pour les valeurs entières de xdonne x=6, ce qui donne 8 580 bits = 1 073 octets . Ainsi, notre stockage idéal est le suivant:

• Taille du groupe: 2 ^ 6 = 64
• Nombre de groupes: 1562

• Stockage total:

  1017 (prefix plus 1's) + 1563 (0's in count) + 6*1000 (offsets) = 8,580 bits = 1,073 bytes

En prenant cela comme un problème purement théorique et en laissant de côté l'implémentation, le moyen le plus efficace consiste simplement à indexer tous les ensembles possibles de 10000 derniers chiffres dans une gigantesque table d'indexation. En supposant que vous ayez exactement 1000 nombres, vous auriez besoin d'un peu plus de 8000 bits pour identifier de manière unique l'ensemble actuel. Il n'y a pas de compression plus importante possible, car vous auriez alors deux ensembles qui sont identifiés avec le même état.

Le problème avec ceci est que vous auriez à représenter chacun des 2 ^ 8000 ensembles de votre programme comme un lut, et même pas Google ne serait capable de cela à distance.

La recherche serait O (1), imprimant tout le nombre O (n). L'insertion serait O (2 ^ 8000) qui en théorie est O (1), mais en pratique est inutilisable.

Dans une interview, je ne donnerais que cette réponse, si j'étais sûr, que l'entreprise recherche quelqu'un qui est capable de beaucoup sortir des sentiers battus. Sinon, cela pourrait vous faire passer pour un théoricien sans soucis du monde réel.

EDIT : Ok, voici une "mise en œuvre".

Étapes pour construire l'implémentation:

1. Prenez un tableau constant de taille 100 000 * (1000 choisissez 100 000) bits. Oui, je suis conscient du fait que ce réseau aura besoin de plus d'espace que les atomes dans l'univers de plusieurs magnitudes.
2. Séparez ce grand tableau en morceaux de 100 000 chacun.
3. Dans chaque bloc, stockez un tableau de bits pour une combinaison spécifique des cinq derniers chiffres.

Ce n'est pas le programme, mais une sorte de méta-programme, qui va construire une gigantesque LUT qui peut désormais être utilisée dans un programme. Les éléments constants du programme ne sont normalement pas comptés lors du calcul de l'efficacité de l'espace, donc nous ne nous soucions pas de ce tableau, lors de nos calculs finaux.

Voici comment utiliser cette LUT:

1. Lorsque quelqu'un vous donne 1000 numéros, vous stockez les cinq premiers chiffres séparément.
2. Découvrez lequel des morceaux de votre tableau correspond à cet ensemble.
3. Enregistrez le numéro de l'ensemble dans un seul numéro de 8074 bits (appelez-le c).

Cela signifie que pour le stockage, nous n'avons besoin que de 8091 bits, ce que nous avons prouvé ici comme étant le codage optimal. Trouver le morceau correct prend cependant O (100 000 * (100 000 choisir 1000)), qui selon les règles mathématiques est O (1), mais en pratique prendra toujours plus de temps que le temps de l'univers.

La recherche est simple cependant:

1. bande des cinq premiers chiffres (le nombre restant sera appelé n ').
2. tester s'ils correspondent
3. Calculer i = c * 100000 + n '
4. Vérifiez si le bit en i dans la LUT est réglé sur un

L'impression de tous les nombres est également simple (et prend en fait O (100000) = O (1), car vous devez toujours vérifier tous les bits du bloc actuel, j'ai donc mal calculé cela ci-dessus).

Je n'appellerais pas cela une «mise en œuvre», à cause du mépris flagrant des limitations (taille de l'univers et temps pendant lequel cet univers a vécu ou cette terre existera). Cependant, en théorie, c'est la solution optimale. Pour les petits problèmes, cela peut être fait, et le sera parfois. Par exemple, les réseaux de tri sont un exemple de cette manière de coder, et peuvent être utilisés comme étape finale dans les algorithmes de tri récursifs, pour obtenir une grande accélération.

Cela équivaut à stocker mille entiers non négatifs inférieurs à 100 000 chacun. Nous pouvons utiliser quelque chose comme l'encodage arithmétique pour ce faire.

En fin de compte, les numéros seront stockés dans une liste triée. Je note que la différence attendue entre les nombres adjacents de la liste est de 100 000/1000 = 100, ce qui peut être représenté en 7 bits. Il y aura également de nombreux cas où plus de 7 bits sont nécessaires. Un moyen simple de représenter ces cas moins courants consiste à adopter le schéma utf-8 où un octet représente un entier de 7 bits à moins que le premier bit ne soit défini, auquel cas l'octet suivant est lu pour produire un entier de 14 bits, à moins que son premier bit est mis à 1, auquel cas l'octet suivant est lu pour représenter un entier de 21 bits.

Ainsi, au moins la moitié des différences entre les entiers consécutifs peut être représentée par un octet, et presque tout le reste nécessite deux octets. Quelques nombres, séparés par des différences plus grandes que 16 384, nécessiteront trois octets, mais il ne peut pas y en avoir plus de 61. Le stockage moyen sera alors d'environ 12 bits par nombre, ou un peu moins, ou au plus 1500 octets.

L'inconvénient de cette approche est que la vérification de l'existence d'un nombre est maintenant O (n). Cependant, aucune exigence de complexité temporelle n'a été spécifiée.

Après avoir écrit, j'ai remarqué que ruslik avait déjà suggéré la méthode de différence ci-dessus, la seule différence est le schéma d'encodage. Le mien est probablement plus simple mais moins efficace.

Juste pour demander rapidement une raison pour laquelle nous ne voudrions pas changer les nombres en base 36. Cela ne fera peut-être pas gagner autant d'espace, mais cela gagnerait certainement du temps sur la recherche puisque vous allez regarder beaucoup moins de 10 chiffres. Ou je les diviserais en fichiers en fonction de chaque groupe. donc je nommerais un fichier (111) -222.txt, puis je ne stockerais que les numéros qui correspondent à ce groupe, puis je les ferais rechercher dans l'ordre numérique de cette façon, je peux toujours chercher pour voir si le fichier se termine. avant de lancer une recherche plus rapide. ou pour être correct, je courrais aux recherches binaires un pour le fichier pour voir s'il se termine. et une autre recherche bonaire sur le contenu du fichier

Pourquoi ne pas rester simple? Utilisez un tableau de structures.

Nous pouvons donc enregistrer les 5 premiers chiffres en tant que constante, alors oubliez-les pour le moment.

65535 est le maximum qui peut être stocké dans un nombre de 16 bits, et le nombre maximum que nous pouvons avoir est 99999, ce qui correspond au 17ème nombre de bits avec un maximum de 131071.

L'utilisation de types de données 32 bits est un gaspillage car nous n'avons besoin que d'1 bit de ces 16 bits supplémentaires ... par conséquent, nous pouvons définir une structure qui a un booléen (ou un caractère) et un nombre de 16 bits.

En supposant C / C ++

typedef struct _number {

    uint16_t number;
    bool overflow;
}Number;

Cette structure ne prend que 3 octets, et nous avons besoin d'un tableau de 1000, donc 3000 octets au total. Nous avons réduit l'espace total de 25%!

En ce qui concerne le stockage des nombres, nous pouvons faire des calculs simples au niveau du bit

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

Et l'inverse

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

Pour les imprimer tous, nous pouvons utiliser une simple boucle sur le tableau. La récupération d'un nombre spécifique se produit bien sûr en temps constant, puisqu'il s'agit d'un tableau.

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

Pour rechercher un nombre, nous voudrions un tableau trié. Ainsi, lorsque les numéros sont enregistrés, triez le tableau (je choisirais personnellement un tri de fusion, O (nlogn)). Maintenant, pour rechercher, j'opterais pour une approche de tri par fusion. Divisez le tableau et voyez entre lequel se situe notre numéro. Appelez ensuite la fonction uniquement sur ce tableau. Faites cela de manière récursive jusqu'à ce que vous ayez une correspondance et renvoyez l'index, sinon, il n'existe pas et imprimez un code d'erreur. Cette recherche serait assez rapide, et le pire des cas est toujours meilleur que O (nlogn) car elle s'exécutera absolument en moins de temps que le tri par fusion (ne récurant qu'un côté de la séparation à chaque fois, au lieu des deux côtés :)), qui est O (nlogn).

Ma solution: meilleur des cas 7,025 bits / nombre, pire des cas 14,193 bits / nombre, moyenne approximative de 8,551 bits / nombre. Encodé en flux, pas d'accès aléatoire.

Avant même de lire la réponse de ruslik, j'ai tout de suite pensé à encoder la différence entre chaque nombre, car elle sera petite et devrait être relativement cohérente, mais la solution doit aussi pouvoir s'adapter au pire des cas. Nous avons un espace de 100 000 nombres qui ne contiennent que 1 000 nombres. Dans un annuaire téléphonique parfaitement uniforme, chaque numéro serait supérieur de 100 au numéro précédent:

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

Si tel était le cas, il faudrait un stockage nul pour encoder les différences entre les nombres, car il s'agit d'une constante connue. Malheureusement, les nombres peuvent différer des étapes idéales de 100. Je coderais la différence par rapport à l'incrément idéal de 100, de sorte que si deux nombres adjacents diffèrent de 103, j'encoderais le nombre 3 et si deux nombres adjacents diffèrent de 92, je encoderait -8. J'appelle le delta d'un incrément idéal de 100 la « variance ».

La variance peut aller de -99 (c'est-à-dire deux numéros consécutifs) à 99000 (le répertoire entier comprend les numéros 00000… 00999 et un numéro supplémentaire le plus éloigné 99999), ce qui correspond à une plage de 99100 valeurs possibles.

Je viserais à allouer un stockage minimal pour encoder les différences les plus courantes et étendre le stockage si je rencontre des différences plus importantes (comme celles de ProtoBufvarint ). J'utiliserai des morceaux de sept bits, six pour le stockage et un bit d'indicateur supplémentaire à la fin pour indiquer que cette variance est stockée avec un morceau supplémentaire après l'actuel, jusqu'à un maximum de trois morceaux (ce qui fournira un maximum de 3 * 6 = 18 bits de stockage, soit 262144 valeurs possibles, soit plus que le nombre de variances possibles (99100). Chaque bloc supplémentaire qui suit un drapeau levé a des bits de plus grande signification, donc le premier bloc a toujours les bits 0- 5, les seconds morceaux facultatifs ont les bits 6-11 et le troisième bloc facultatif a les bits 12-17.

Un seul bloc fournit six bits de stockage pouvant accueillir 64 valeurs. Je voudrais mapper les 64 plus petites variances pour qu'elles tiennent dans ce seul bloc (c'est-à-dire des variances de -32 à +31), donc j'utiliserai l'encodage ProtoBuf ZigZag, jusqu'aux variances de -99 à +98 (car il n'y a pas besoin pour une variance négative au-delà de -99), à quel point je passerai à l'encodage normal, décalé de 98:  

Variance | Valeur codée
----------- + ----------------
    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
----------- | --------------- Fin du zigzag
   100 | 198
   101 | 199
   ... | ...
  3996 | 4094
  3997 | 4095
----------- | --------------- 12 bits
  3998 | 4096
  3999 | 4097
   ... | ...
 262045 | 262143
----------- | --------------- 18 bits

Quelques exemples de la façon dont les variances seraient codées sous forme de bits, y compris le drapeau pour indiquer un bloc supplémentaire:

Variance | Bits codés
----------- + ----------------
     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

Ainsi, les trois premiers numéros d'un exemple d'annuaire téléphonique seraient codés comme un flux de bits comme suit:

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

Dans le meilleur des cas , l'annuaire téléphonique est distribué de manière quelque peu uniforme et il n'y a pas deux numéros de téléphone qui ont une variance supérieure à 32, donc il utiliserait 7 bits par numéro plus 32 bits pour le numéro de départ pour un total de 32 + 7 * 999 = 7025 bits .
Un scénario mixte , où la variance de 800 numéros de téléphone s'inscrit dans un bloc (800 * 7 = 5600), 180 numéros entrent dans deux morceaux chacun (180 * 2 * 7 = 2520) et 19 nombres entrent dans trois morceaux chacun (20 * 3 * 7 = 399), plus les 32 bits initiaux, totalisent 8551 bits .
Dans le pire des cas , 25 nombres tiennent en trois morceaux (25 * 3 * 7 = 525 bits) et les 974 nombres restants entrent en deux morceaux (974 * 2 * 7 = 13636 bits), plus 32 bits pour le premier nombre d'un grand total de14193 bits .

   Quantité de nombres encodés |
 1-morceau | 2 morceaux | 3 morceaux | Nombre total de bits
--------- + ---------- + ---------- + ------------
   999 | 0 | 0 | 7025
   800 | 180 | 19 | 8551
    0 | 974 | 25 | 14193

Je peux voir quatre optimisations supplémentaires qui peuvent être effectuées pour réduire davantage l'espace requis:

1. Le troisième morceau n'a pas besoin des sept bits complets, il peut s'agir de seulement cinq bits et sans bit de drapeau.
2. Il peut y avoir une première passe des nombres pour calculer les meilleures tailles pour chaque morceau. Peut-être que pour un certain répertoire, il serait optimal que le premier bloc ait 5 + 1 bits, le deuxième 7 + 1 et le troisième 5 + 1. Cela réduirait encore la taille à un minimum de 6 * 999 + 32 = 6026 bits, plus deux ensembles de trois bits pour stocker les tailles des blocs 1 et 2 (la taille du bloc 3 est le reste des 16 bits requis) pour un total de 6032 bits!
3. La même passe initiale peut calculer un meilleur incrément attendu que la valeur par défaut 100. Peut-être y a-t-il un annuaire téléphonique qui commence de 55555-50000, et donc il a la moitié de la plage de numéros, donc l'incrément attendu devrait être de 50. Ou peut-être qu'il y a un répertoire non linéaire distribution (écart-type peut-être) et un autre incrément optimal attendu peut être utilisé. Cela réduirait la variance typique et pourrait permettre d'utiliser un premier bloc encore plus petit.
4. Une analyse plus approfondie peut être effectuée lors de la première passe pour permettre le partitionnement de l'annuaire téléphonique, chaque partition ayant ses propres optimisations d'incrément et de taille de bloc attendues. Cela permettrait une taille de premier bloc plus petite pour certaines parties très uniformes de l'annuaire téléphonique (réduisant le nombre de bits consommés) et des tailles de blocs plus grandes pour les parties non uniformes (réduisant le nombre de bits gaspillés sur les indicateurs de continuation).

La vraie question est de stocker les numéros de téléphone à cinq chiffres.

L'astuce est que vous auriez besoin de 17 bits pour stocker la plage de nombres de 0 à 99 999. Mais stocker 17 bits sur des limites de mot conventionnelles de 8 octets est un problème. C'est pourquoi ils vous demandent si vous pouvez faire en moins de 4k en n'utilisant pas d'entiers 32 bits.

Question: toutes les combinaisons de nombres sont-elles possibles?

En raison de la nature du système téléphonique, il peut y avoir moins de 65 000 combinaisons possibles. Je suppose que oui, car nous parlons des cinq dernières positions du numéro de téléphone, par opposition à l'indicatif régional ou aux préfixes d'échange.

Question: cette liste sera-t-elle statique ou devra-t-elle prendre en charge les mises à jour?

S'il est statique , alors quand vient le temps de remplir la base de données, comptez le nombre de chiffres <50 000 et le nombre de chiffres> = 50 000. Allouez deux tableaux de uint16longueur appropriée: un pour les entiers inférieurs à 50 000 et un pour l'ensemble supérieur. Lors du stockage des entiers dans le tableau supérieur, soustrayez 50 000 et lors de la lecture des entiers de ce tableau, ajoutez 50 000. Vous avez maintenant stocké vos 1 000 entiers dans 2 000 mots de 8 octets.

La construction du répertoire nécessitera deux traversées d'entrée, mais les recherches devraient se produire en moyenne deux fois moins de temps qu'avec un seul tableau. Si le temps de recherche était très important, vous pourriez utiliser plus de tableaux pour des plages plus petites, mais je pense qu'à ces tailles, vos performances seraient liées à l'extraction des tableaux de la mémoire et 2k se cacheraient probablement dans le cache du processeur si vous n'enregistriez pas d'espace sur tout ce que vous utiliseriez. journées.

S'il est dynamique , allouez un tableau d'environ 1 000 uint16et ajoutez les nombres dans l'ordre trié. Définissez le premier octet sur 50 001 et définissez le deuxième octet sur une valeur nulle appropriée, telle que NULL ou 65 000. Lorsque vous stockez les numéros, stockez-les dans un ordre trié. Si un nombre est inférieur à 50 001, stockez-le avant le marqueur 50 001. Si un nombre est égal ou supérieur à 50 001, stockez-le après le marqueur 50 001, mais soustrayez 50 000 de la valeur stockée.

Votre tableau ressemblera à quelque chose comme:

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

Ainsi, lorsque vous recherchez un numéro dans le répertoire, vous parcourez le tableau et si vous avez atteint la valeur 50 001, vous commencez à ajouter 50 000 à vos valeurs de tableau.

Cela rend les insertions très coûteuses, mais les recherches sont faciles et vous n'allez pas dépenser beaucoup plus de 2k en stockage.