Moyen le plus efficace pour stocker mille numéros de téléphone

Ceci est une question d’interview de google:

Il y a environ mille numéros de téléphone à stocker, chacun comportant 10 chiffres. Vous pouvez supposer que les 5 premiers chiffres de chacun sont les mêmes pour 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 de faire de la place pour cela?

J’ai répondu à la table de hachage et plus tard au codage huffman mais mon interlocuteur m’a dit que je n’allais pas dans la bonne direction. S’il vous plaît aidez-moi ici.

L’utilisation d’un suffixe peut-elle aider?

Idéalement, 1 000 numéros stockés prennent 4 octets par numéro. En tout, il faudrait 4 000 octets pour stocker 1 000 numéros. Quantitativement, je souhaite réduire le stockage à <4000 octets, c'est ce que mon interlocuteur m'a expliqué.

Voici une amélioration à la réponse de 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); ainsi, à 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 binarys de 17 bits et stockons k de ces bits en utilisant une méthode et 17 – k = m avec une méthode différente, déterminant k à la fin pour minimiser l’espace requirejs.

Nous sortingons d’abord les numéros de téléphone (tous réduits à 5 chiffres décimaux). Ensuite, nous comptons le nombre de numéros de téléphone pour lesquels le nombre binary composé des premiers m bits est égal à 0, pour combien de numéros de téléphone les premiers m bits sont au maximum 0 … 01, pour combien de numéros le premier les bits sont au plus 0 … 10, etc., jusqu’au nombre de numéros de téléphone pour lesquels les premiers m bits sont 1 … 11 – ce dernier compte est 1000 (décimal). Il y a 2 ^ m de tels comptages et chaque comptage est au maximum de 1000. Si nous omettons le dernier (parce que nous soaps que c’est 1000 de toute façon), 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 derniers k 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, par exemple, 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 , qui atteint son minimum 11287 pour k = 10. Nous pouvons donc stocker tous les numéros de téléphone dans ceil ( 11287/8) = 1411 octets.

Un espace supplémentaire peut être enregistré en observant qu’aucun de nos nombres ne peut par exemple commencer par 1111111 (binary), car le nombre le plus bas qui commence par 130048 et nous n’avons que cinq chiffres décimaux. Cela nous permet de raser quelques entrées sur le premier bloc de mémoire: au lieu de 2 ^ m – 1 comptes, nous n’avons besoin que de ceil (99999/2 ^ k ). Cela signifie que la formule devient

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

qui atteint étonnamment son minimum 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 figure dans notre ensemble, nous vérifions d’abord si les cinq premiers chiffres binarys correspondent aux cinq chiffres que nous avons enregistrés. Ensuite, nous divisons les cinq chiffres restants en m = 7 bits (c’est-à-dire le nombre m- bits M ) et son k = 10 bits inférieur (le nombre K ). Nous trouvons maintenant le numéro a [M-1] des numéros de téléphone réduits pour lesquels les premiers chiffres sont au plus M – 1, et le numéro a [M] des numéros de téléphone réduits pour lesquels les premiers chiffres M sont au plus M , à la fois du premier bloc de bits. Nous vérifions maintenant entre le a [M-1] th et une [M] e séquence de k bits dans le deuxième bloc de mémoire pour voir si nous trouvons K ; dans le pire des cas, il y a 1000 séquences de ce type, donc si nous utilisons la recherche binary, nous pouvons terminer dans les opérations O (log 1000).

Le pseudocode pour imprimer tous les 1000 numéros suit, où j’accède à l’entrée K’th k- bit du premier bloc de mémoire en tant que [K] et à l’entrée M ‘th-bit du second bloc de mémoire en tant que b [M] (ces deux opérations nécessiteraient quelques opérations 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; 

Quelque chose ne va pas avec le cas limite pour K = ceil (99999/2 ^ k ), mais c'est assez facile à corriger.

Enfin, du sharepoint vue de l’entropie, il n’est pas possible de stocker un sous-ensemble de 10 ^ 3 nombres entiers positifs tous inférieurs à 10 ^ 5 dans moins que ceil (log [2] (binomial (10 ^ 5, 10 ^ 3)) ) = 8073. En comptant les 17 premiers chiffres, il rest 10997 à 8090 = 2907 bits. C'est un défi intéressant de voir s'il existe de meilleures solutions pour 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. Trier les nombres.
  2. Divisez chaque nombre en 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 numéro stocké dans l’ordre croissant.

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

La recherche est O(log n) (recherche binary) 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 (éventuellement 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 à temps constant et l’impression sera effectuée en temps linéaire.

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

1) Puisque l’ordre n’a pas d’importance, nous pouvons les sortinger et enregistrer uniquement les différences entre les valeurs consécutives. Dans notre cas, les différences moyennes seraient de 100 000/1000 = 100

2) Codez 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 la base 128 (non pas parce que cela donnerait les meilleurs résultats, mais parce que c’est plus facile à calculer):

Nous allons enregistrer la première valeur telle quelle (32 bits).
Les 999 autres valeurs sont des différences (nous pensons qu’elles sont petites, 100 en moyenne) contiendront:

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

Nous devons estimer les limites (appelons-le VBL ) pour le nombre de bits variables:
limite inférieure: considérez que nous avons de la chance, et aucune différence n’est plus grande que notre base (128 dans ce cas). cela voudrait dire donner 0 bits supplémentaires.
limite haute: comme toutes les différences plus petites que la base seront encodées en partie binary du nombre, le nombre maximum que nous aurons besoin d’encoder en unaire est 100000/128 = 781.25 (encore moins, car la plupart des différences ne sont pas nulles) ).

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

Ceci est un problème bien connu de Programming Pearls de Bentley.

Solution: Enlevez les cinq premiers chiffres des nombres car ils sont identiques pour chaque nombre. Utilisez ensuite les opérations binarys pour représenter la valeur 9999 restante possible. Vous aurez seulement besoin de 2 ^ 17 Bits pour représenter les nombres. Chaque bit représente un nombre. Si le bit est défini, le numéro est dans le répertoire téléphonique.

Pour imprimer tous les nombres, imprimez simplement tous les nombres où le bit est placé concaténé avec le préfixe. Pour rechercher un nombre donné, faites le calcul arithmétique nécessaire pour vérifier la représentation binary du nombre.

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

HTH Chris.

Stockage fixe de 1073 octets pour 1 000 numéros:

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

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

Regroupement:
Ensuite, nous devons trouver un regroupement de bonne taille pour les nombres. Essayons d’avoir environ 1 numéro par groupe. Comme nous soaps qu’il y a environ 1000 numéros à stocker, nous divisons 99 999 en environ 1000 parties. Si nous avons choisi la taille du groupe comme 100, il y aurait des bits gaspillés, 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.

Compte:
Ensuite, pour chacun des 782 groupes, nous devons stocker le nombre d’entrées dans chaque groupe. Un nombre 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 décomptes de taille variable avec des 1 en tête pour chaque nombre dans un groupe suivi d’un 0. Ainsi, si nous avions des nombres x dans un groupe, nous aurions x 1's suivi d’un 0 pour représenter le nombre. Par exemple, si nous avions 5 numéros dans un groupe, le compte serait représenté par 111110 . Avec cette méthode, s’il y a 1 000 numéros, nous obtenons 1000 1 et 782 0 pour un total de 1000 + 782 = 1 782 bits pour les comptes .

Décalage:
Enfin, le format de chaque numéro 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 seraient 110 0000000 0000001 . En supposant 1 000 numéros, il y aura 7 000 bits pour les décalages .

Ainsi, notre décompte final en supposant 1 000 numéros 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 du groupe. En choisissant x comme nombre de bits pour représenter chaque groupe, la formule de la taille est la suivante:

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

Minimiser cette équation pour des valeurs entières de x donne 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: 1 562
  • 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 une place à la mise en œuvre, le moyen le plus efficace est d’indexer tous les ensembles possibles de 10000 derniers chiffres dans une table d’indexation gigantesque. En supposant que vous avez exactement 1000 numéros, 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 plus grande compression possible, car alors vous auriez deux ensembles qui sont identifiés avec le même état.

Des problèmes avec ceci sont que vous devriez représenter chacun des 2 ^ 8000 ensembles de votre programme comme un lutin, et même google ne serait pas capable de cela à distance.

La recherche serait O (1), imprimant tout le numéro O (n). L’insertion serait O (2 ^ 8000), ce qui en théorie est O (1), mais en pratique, elle est inutilisable.

Dans une interview, je donnerais seulement cette réponse, si j’en étais sûr, que la société recherche quelqu’un capable de sortir des sentiers battus. Sinon, cela pourrait vous faire ressembler à un théoricien sans inquiétude réelle.

EDIT : Ok, voici une “implémentation”.

Étapes pour construire l’implémentation:

  1. Prendre un tableau constant de taille 100 000 * (1000 choisir 100 000) bits. Oui, je suis conscient du fait que ce tableau aura besoin de plus d’espace que les atomes de l’univers par plusieurs grandeurs.
  2. Séparez ce grand tableau en morceaux de 100 000 chacun.
  3. Dans chaque bloc, stocker 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 LUT gigantesque qui peut maintenant être utilisée dans un programme. Les éléments constants du programme ne sont normalement pas comptabilisés lors du calcul de l’efficacité de l’espace, nous ne nous soucions donc pas de ce tableau, lorsque nous effectuons 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 quels morceaux de votre tableau correspondent à cet ensemble.
  3. Stockez le numéro de l’ensemble dans un seul numéro de bit 8074 (appelez ceci c).

Cela signifie que pour le stockage, nous n’avons besoin que de 8091 bits, ce qui s’est avéré être le codage optimal. Trouver le morceau correct prend cependant O (100 000 * (100 000 choisissez 1000)), ce qui, selon les règles mathématiques, est O (1), mais dans la pratique, cela prendra toujours plus de temps que l’univers.

La recherche est simple cependant:

  1. bande des cinq premiers chiffres (le numéro restant sera appelé n ‘).
  2. tester si elles correspondent
  3. Calculer i = c * 100000 + n ‘
  4. Vérifiez si le bit à i dans la table de correspondance est réglé sur un

Imprimer tous les nombres est aussi simple (et prend O (100000) = O (1) en fait, car vous devez toujours vérifier tous les bits du bloc en cours, alors j’ai mal calculé ce qui précède).

Je n’appellerais pas cela une “implémentation”, à cause du mépris flagrant des limitations (la taille de l’univers et le temps que 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 parfois sera fait. Par exemple, les réseaux de sorting sont un exemple de cette manière de coder et peuvent être utilisés comme une étape finale dans les algorithmes de sorting récursif, afin de gagner en rapidité.

Cela équivaut à stocker mille entiers non négatifs, chacun inférieur à 100 000. Pour ce faire, nous pouvons utiliser quelque chose comme un encodage arithmétique.

En fin de compte, les numéros seront stockés dans une liste sortingée. Je note que la différence attendue entre les nombres adjacents dans la liste est 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. Une manière 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 le prochain octet est lu pour produire un entier de 14 bits, sauf si son premier bit est défini, auquel cas le prochain octet est lu pour représenter un entier de 21 bits.

Ainsi, au moins la moitié des différences entre les entiers consécutifs peuvent être représentées avec un octet, et presque tous les autres nécessitent deux octets. Quelques nombres, séparés par des différences supérieures à 16 384, nécessiteront trois octets, mais il ne peut y en avoir plus de 61. Le stockage moyen sera alors d’environ 12 bits par nombre, ou un peu moins, ou tout 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 quelconque pour laquelle nous ne voudrions pas changer les nombres en une base 36. Cela ne vous épargnera pas autant d’espace, mais vous gagnerez du temps sur la recherche, car vous aurez beaucoup moins de 10digts. Ou je les diviserais en fichiers en fonction de chaque groupe. donc je nommerais un fichier (111) -222.txt et ensuite je ne stockerais que les nombres qui rentrent dans ce groupe et ensuite je les ferais rechercher par ordre numérique pour que je puisse toujours voir si le fichier se termine. avant que je lance une recherche de biger. ou pour être correct, je courrais à une recherche binary pour le fichier pour voir si elle se ferme. et une autre recherche sur le contenu du fichier

Pourquoi ne pas restr 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 plus grand nombre pouvant être stocké dans un nombre de 16 bits, et le nombre maximum que nous pouvons avoir est 99999, ce qui correspond au numéro de 17 bits avec un maximum de 131071.

Utiliser des types de données 32 bits est un gaspillage, car nous n’avons besoin que de 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 que 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. Récupérer un nombre spécifique se produit bien sûr, car il s’agit d’un tableau.

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

Pour rechercher un numéro, nous souhaitons un tableau sortingé. Donc, lorsque les nombres sont enregistrés, sortingez le tableau (je choisirais personnellement un type de fusion, O (nlogn)). Maintenant, pour effectuer une recherche, je choisirais une approche de sorting par fusion. Divisez le tableau et voyez lequel de nos numéros se situe. Ensuite, appelez la fonction uniquement sur ce tableau. Faites ceci récursivement 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 encore meilleur que O (nlogn) car il s'exécutera absolument en moins de temps que le sorting de fusion (ne récursant que 1 face du fractionnement à la place des deux côtés :)), ce qui est O (nlogn).

Ma solution: meilleur cas 7.025 bits / nombre, pire cas 14.193 bits / nombre, moyenne approximative 8.551 bits / nombre. Stream-encoded, aucun access aléatoire.

Avant même d’avoir lu la réponse de ruslik, j’ai immédiatement pensé à encoder la différence entre chaque nombre, car il serait petit et devrait être relativement cohérent, mais la solution doit également pouvoir s’adapter au pire des scénarios. Nous avons un espace de 100 000 numéros qui ne contient que 1 000 numéros. Dans un annuaire parfaitement uniforme, chaque numéro serait supérieur au chiffre précédent de 100:

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

Si tel était le cas, il ne nécessiterait aucun stockage pour coder les différences entre les nombres, car il s’agit d’une constante connue. Malheureusement, les nombres peuvent varier des pas idéaux 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, je coderais le nombre 3 et si deux nombres adjacents diffèrent de 92, je serait encoder -8. J’appelle le delta d’un incrément idéal de 100 la « variance ».

L’écart peut aller de -99 (soit deux chiffres consécutifs) à 99000 (le répertoire complet se compose des numéros 00000… 00999 et d’un numéro supplémentaire 99999), soit 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 le varint de varint ). J’utiliserai des morceaux de sept bits, six pour le stockage et un bit supplémentaire à la fin pour indiquer que cette variance est stockée avec un bloc supplémentaire après le dernier, jusqu’à un maximum de trois morceaux (ce qui fournira un maximum de 3 * 6 = 18 bits de stockage, soit 262144 valeurs possibles, plus que le nombre de variances possibles (99100) Chaque bloc supplémentaire qui suit un indicateur levé a des bits de signification supérieure, de sorte que le premier bloc a toujours des bits 0- 5, les deuxièmes morceaux optionnels ont les bits 6-11, et le troisième bloc optionnel a les bits 12-17.

Un bloc unique fournit six bits de stockage pouvant contenir 64 valeurs. Je voudrais mapper les 64 plus petites variances pour tenir dans ce morceau unique (c.-à-d. Les variances de -32 à +31), donc je vais utiliser 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 à un encodage régulier, avec un décalage de 98:

  La variance  Valeur encodé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 de 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 en tant que bits, y compris l’indicateur pour indiquer un bloc supplémentaire:

  La variance  Bits Encodé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 de répertoire téléphonique seraient encodés 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 dissortingbué de manière quelque peu uniforme et il n’y a pas deux numéros de téléphone dont l’écart est supérieur à 32, de sorte qu’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 correspond à un bloc (800 * 7 = 5600), 180 numéros de deux morceaux chacun (180 * 2 * 7 = 2520) et 19 numéros de trois morceaux chacun (20 * 3 * 7 = 399), plus les 32 bits initiaux, totalise 8551 bits .
Dans le pire des cas , 25 numéros correspondent à trois blocs (25 * 3 * 7 = 525 bits) et les 974 autres correspondent à deux blocs (974 * 2 * 7 = 13636 bits), plus 32 bits pour le premier chiffre d’un grand total de 14193 bits .

    Quantité de chiffres codés |
  1 morceau |  2 morceaux |  3 morceaux |  Total 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 requirejs:

  1. Le troisième morceau n’a pas besoin des sept bits complets, il ne peut s’agir que de cinq bits et sans bit de drapeau.
  2. Il peut y avoir une première passe des numéros pour calculer les meilleures tailles pour chaque morceau. Peut-être que pour un répertoire donné, il serait préférable que le premier bloc comporte 5 + 1 bits, le second 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 morceaux 1 et 2 (la taille du bloc 3 est le rest des 16 bits requirejs) pour un total de 6032 bits!
  3. Le même passage initial permet de calculer un meilleur incrément attendu que la valeur par défaut de 100. Peut-être y a-t-il un annuaire qui commence à 55555-50000, donc il a la moitié de la plage de numéros et l’incrément attendu devrait être 50. la dissortingbution (écart type peut-être) et une autre augmentation optimale attendue peuvent être utilisées. Cela réduirait la variance typique et permettrait d’utiliser un premier bloc encore plus petit.
  4. Une parsing plus poussée peut être effectuée lors du premier passage pour permettre le partitionnement de l’annuaire téléphonique, chaque partition ayant ses propres optimisations attendues d’incrément et de taille de bloc. Cela permettrait une première taille de bloc plus petite pour certaines parties très uniformes de l’annuaire (réduisant le nombre de bits consommés) et des tailles de blocs plus importantes pour les pièces non uniformes (réduisant le nombre de bits perdus sur les indicateurs de continuation).

La vraie question est de stocker des 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 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, au moment de remplir la firebase database, comptez le nombre de chiffres <50 000 et le nombre de chiffres> = 50 000. Allouez deux tableaux de uint16 de longueur appropriée: un pour les entiers inférieurs à 50 000 et un pour l’ensemble supérieur. Lorsque vous stockez des entiers dans le tableau supérieur, soustrayez 50 000 et, lorsque vous lisez des nombres entiers de ce tableau, ajoutez 50 000. Vous avez maintenant stocké vos 1 000 entiers en 2 000 mots de 8 octets.

La création de l’annuaire nécessitera deux parcours d’entrée, mais les recherches devraient être effectuées 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 que dans ces tailles, les performances seraient tirées de la mémoire et 2k restraient probablement dans le cache du processeur. journées.

S’il est dynamic , allouez un tableau de 1000 ou uint16 et ajoutez les nombres dans l’ordre de sorting. Définissez le premier octet sur 50 001 et définissez le deuxième octet sur une valeur null appropriée, telle que NULL ou 65 000. Lorsque vous enregistrez les numéros, stockez-les dans l’ordre sortingé. 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 à:

 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 traversez le tableau et si vous avez atteint la valeur 50 001, vous commencez à append 50 000 à vos valeurs de tableau.

Cela rend les encarts très coûteux, mais les recherches sont faciles et vous ne dépenserez pas beaucoup plus que 2k pour le stockage.