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

C'est un google les questions de l'entrevue:

Il y a environ mille numéros de téléphone stockés ayant chacun des 10 chiffres. Vous pouvez prendre les 5 premiers chiffres de chaque être même à travers des milliers de numéros. Vous devez effectuer les opérations suivantes:
un. Recherche si un nombre donné existe.
b. Imprimer tout le nombre

Ce qui est le plus efficace d'économiser de l'espace façon de le faire ?

J'ai répondu à la table de hachage et, plus tard, le codage de huffman mais mon interviewer dit que je n'allait pas dans la bonne direction. Merci de m'aider ici.

Pourrait à l'aide d'un suffixe trie aider?

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

Je répondrais que l'utilisation normale de la base de données, vous pouvez les stocker sous forme de texte, voire des milliers/millions de dollars, et les opérations de recherche va encore être très rapide. Je vous déconseille de faire "intelligents" les choses depuis l'ensemble du système devra être refait si ils veulent à l'avenir pour soutenir les numéros internationaux, ou si les numéros de téléphone qui commencent par un "0" commencent à apparaître, ou si le gouvernement décide de modifier le numéro de téléphone de format, et ainsi de suite.
Je serais probablement donner cette réponse, à moins que j'ai été interviewer une compagnie comme Google ou Facebook, ont été hors de la boîte solutions il suffit de ne pas le couper. Bien que postgres, par exemple, a tente, trop, je ne voudrais pas être sûr que ces couper le débit de données de google a besoin de prendre de.
gardez à l'esprit que l'OP spécifiquement indiqué que "près d'un millier de numéros"
Vrai, aurait également été un test, que la personne sait interpréter de telles contraintes correctement et choisir la meilleure solution en fonction de cela.
"efficace" dans cette question doit vraiment être définies efficace dans lequel les moyens? l'espace, le temps, les deux?
La Trie mentionné dans les réponses est très similaire à ce que nous avons en fait utilisé pour les numéros de téléphone sur un téléphone commutateur. Il est très efficace quand vous avez un plan de numérotation où les préfixes sont réellement affectés dans les groupes - comme la façon dont la physique utilisation des lignes téléphoniques d'être attribués. Mais avec le numéro de téléphone de la portabilité, je suis sûr qu'ils ont des différents algorithmes.
vous pouvez envisager de bitset<17> structure de données pour le stockage efficace de 5 chiffres au lieu d'un entier de sorte que vous permettra d'économiser au moins 15 bits pour chaque numéro, c'est presque la moitié de l'espace nécessaire

InformationsquelleAutor princess of persia | 2011-10-07

algorithm data-structures

36

Voici une amélioration de aix réponse. Envisager d'utiliser des trois "couches" de la structure de données: la première est une constante pour les cinq premiers chiffres (17 bits); donc à partir de là, chaque numéro de téléphone n'a que les cinq derniers chiffres de gauche. Nous considérons ces cinq derniers chiffres 17-bit binaire des entiers et de les stocker k de ces morceaux à l'aide d'une méthode et de 17 k = m avec une autre méthode, la détermination de k à la fin pour minimiser l'espace requis.

Nous avons d'abord trier les numéros de téléphone (tous les réduit à 5 chiffres après la virgule). Alors nous comptons combien de numéros de téléphone il y a pour qui le nombre binaire composé de la première m bits est 0, pour combien de numéros de téléphone de la première m bits les plus à 0...01, pour combien de numéros de téléphone de la première m bits sont à plus de 0...10, etc, jusqu'à le nombre de numéros de téléphone pour lequel la première m bits sont à 1...11 - cette dernière décompte de 1000(décimal). Il y a 2^m le recensement et chaque nombre est à plus de 1000. Si nous omettons le dernier (parce que nous savons que c'est 1000 de toute façon), nous pouvons stocker tous ces chiffres dans un bloc contigu de (2^m - 1) * 10 bits. (10 bits est suffisant pour le stockage d'un nombre inférieur à 1024.)

La dernière k bits de tous (réduit) les numéros de téléphone sont stockés de manière contiguë en mémoire; donc, si k est, disons, 7, puis les 7 premiers bits de ce bloc de mémoire (bits 0 à 6) correspondent aux 7 derniers bits de la première (réduit) numéro de téléphone, les bits 7 à 13 correspondent aux 7 derniers bits de la seconde (réduit) numéro de téléphone, 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. Donc on peut stocker tous les numéros de téléphone dans ceil(11287/8)=1411 octets.

De l'espace supplémentaire peut être sauvé que par l'observation qu'aucun de nos numéros pouvez commencer avec, par exemple, 1111111(binaire), parce que le plus petit nombre qui commence avec ça, c'est 130048 et nous n'avons que cinq chiffres après la virgule. Cela nous permet de se raser quelques entrées le premier bloc de mémoire: au lieu de 2^m - 1 compte, nous avons besoin seulement d'ceil(99999/2^k). Que signifie la formule devient

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

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

Si nous voulons savoir si un numéro de téléphone est dans notre série, nous avons d'abord vérifier si les cinq premiers chiffres binaires correspondent à cinq chiffres que nous avons enregistrées. Puis nous nous sommes répartis les cinq derniers chiffres en son sommet m=7 bits (qui est, disons, la m-nombre de bits M) et de sa faible k=10 bits (le nombre K). Nous avons maintenant de trouver le numéro de un[M-1] de la réduction des numéros de téléphone pour lequel la première m chiffres sont dans la plupart des M - 1, et le nombre un[M] de la réduction des numéros de téléphone pour lequel la première m chiffres sont dans la plupart des M, à la fois à partir du premier bloc de bits. Nous avons maintenant de vérification entre les un[M-1]th et un[M]th séquence de k bits dans le deuxième bloc de la mémoire pour voir si nous trouvons K; dans le pire des cas il y a 1000 telles séquences, donc si l'on utilise le binaire de recherche, nous pouvons terminer en O(log 1000) opérations.

Pseudo-code pour l'impression de toutes les 1000 numéros suit, où j'ai accès à la K'th kbits d'entrée du premier bloc de la mémoire comme un[K] et le M'th mbits d'entrée de la deuxième bloc de la mémoire comme b[M] (ces deux aurait besoin d'un peu d'opérations sur les bits qui sont pénibles à écrire). Les cinq premiers chiffres sont le numéro de 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 quelque chose va mal avec la limite de cas pour K = ceil(99999/2^k), mais c'est assez facile à corriger.

Enfin, à partir d'une entropie point de vue, il n'est pas possible de stocker un sous-ensemble de 10^3 entiers positifs tous à moins de 10^5 en moins de ceil(log[2](binomiale(10^5, 10^3))) = 8073. Y compris les 17 nous avons besoin pour les 5 premiers chiffres, il y a encore 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 à l'un des numéros de façon relativement efficace!
- Le discbased vous décrivez ici est en fait seulement une très efficace version de trie, qui n'utilise qu'aussi peu que nécessaire à l'indexation et à seulement deux niveaux. Dans la pratique, il serait agréable de voir si cela peut battre un trie avec plus de niveaux, mais je pense que cela dépend beaucoup de la répartition des nombres (Dans la vraie vie, les numéros de téléphone ne sont pas totalement aléatoire, mais seulement presque).
- Salut Erik, puisque vous avez dit que vous seriez intéressé pour voir d'autres alternatives, découvrez ma solution. Il la résout en nets 8 580 bits, ce qui est juste 490 bits d'arrêt du minimum théorique. C'est un peu inefficace pour rechercher des numéros individuels, mais l'espace de stockage est très compact.
- Je suppose qu'un sane interviewer préférez la réponse "un trie" au lieu de "un complexe personnalisé de la base de données". Si vous voulez montrer votre 133t compétences de piratage, vous pouvez ajouter - "il serait possible de faire un arbre spécifique algorithme spécial pour ce cas, si cela était nécessaire."
- Plaisir à travailler pour Google.
- Salut, Pouvez-vous nous expliquer comment 5 chiffres prendre 17 bits pour être stockées?
- Cinq chiffres coder un nombre entre 00000 et 99999 inclusive. Représenter un nombre en binaire. 2^17=131072, donc 17 bits suffisent pour que mais 16 ne le font pas.
InformationsquelleAutor Erik P.
43

Dans ce qui suit, je traite les nombres comme des variables de type entier (par opposition aux chaînes):
1. Trier les nombres.
2. Diviser chaque nombre dans les cinq premiers chiffres et les cinq derniers chiffres.
3. Les cinq premiers chiffres sont les mêmes dans tous les numéros, donc les stocker qu'une seule fois. Cela nécessitera de 17 bits de stockage.
4. Stocker les cinq derniers chiffres de chaque nombre individuellement. Cela nécessitera de 17 bits par numéro.
Pour rappel: les 17 premiers bits sont le préfixe commun, les 1000 groupes de 17 bits sont les cinq derniers chiffres de chaque numéro stocké dans l'ordre croissant.

Au total, nous sommes à la recherche à 2128 octets pour les 1000 numéros, ou 17.017 bits par 10 chiffres du numéro de téléphone.

De recherche est O(log n) (binaire de recherche) et dénombrement complet est O(n).
- +1 pour l'espace de la complexité 🙂
- Euh, où est l'espace de la complexité?
- Trop de temps à construire (O(log(n)*nk) (k est la longueur) pour le tri, par rapport à O(nk) pour la construction d'un trie). Aussi l'espace est loin d'être optimale, car plus les préfixes sont stockés individuellement. Le temps de recherche est également pas optimal. Pour les données de chaîne comme cela, il est facile d'oublier la longueur de la le nombre, qui domine la recherche. I. e. binaire de recherche est O(log(n)*k), alors qu'un trie uniquement besoin de O(k). Vous pouvez réduire les thèses des expressions, lorsque k est constant, mais c'est pour montrer d'une manière générale, le problème de raisonnement sur les structures de données stocker des chaînes de caractères.
- Qui a dit quelque chose à propos des chaînes? Je m'occupe exclusivement avec des variables de type entier, de sorte k n'est pas pertinent.
- Ok, j'ai mal lu la réponse, puis. Encore, les parties communes ne sont pas stockés, de sorte que le point sur l'efficacité de l'espace reste. Pour 1000 de 5 chiffres, il y aura une bonne quantité de la commune de préfixes, de sorte que la réduction de ces aidera beaucoup. Aussi dans le cas de nombres que nous avons O(log(n)) par rapport à O(k) pour les chaînes, qui est encore plus rapide.
- Pour les specs, cette réponse semble le plus efficace stockage.
- Comment vous avez calculé la valeur du total des 2128 octets?
- 1001 groupes de 17 bits est 17017 bits ou 2128 octets (avec quelques changements).
- pour le suivi de commentaires et la solution merveilleuse.
InformationsquelleAutor NPE
22

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

Une fois, j'ai eu un entretien où ils ont demandé des structures de données. J'ai oublié le "Tableau".
- +1 c'est certainement le chemin à parcourir. J'ai appris cela sous un autre nom, de la Bibliothèque de l'arbre ou lexicales arbre de recherche ou de quelque chose quand j'étais étudiant (si quelqu'un se souvient que l'ancien nom s'il vous plaît ne dites).
- Cela ne veut pas répondre à 4000 octets exigence. Pour le pointeur de stockage seul, le pire scénario est que vous aurez besoin de 1 pointeur pour les 1-4 feuilles au niveau suivant, de 10 pointeurs pour les 5e, 100 pour la 6ème, et 1000 pour les 7e, 8e et 9e niveaux, ce qui amène notre pointeur de total à 3114. Qui donne au moins 3114 distinctes emplacements de mémoire nécessaire pour les pointeurs à point, ce qui signifie que vous avez besoin d'au moins 12 bits pour chaque pointeur. 12*3114 = 37368 bits = 4671 octets > 4000 octets, et qui n'a même pas la figure dans la façon de représenter la valeur de chaque feuille!
InformationsquelleAutor Mikhail
16

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

Qui serait automagiquement profiter 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.
- La question est au sujet de la plupart de l'espace-efficace pour stocker les données. Pourriez-vous fournir une estimation de la quantité d'espace cette méthode requiert, pour l'1000 numéros de téléphone? Merci.
- De l'espace pour le trie est au plus O(n*k) où n est le nombre de chaînes et k est la longueur de chaque chaîne. Tenant compte du fait que vous n'avez pas besoin de 8 bits de caractères pour représenter les nombres, je suggère de stockage de 4 hexadécimal index hexadeximal et l'autre pour le reste des bits. De cette façon, vous avez besoin d'au maximum 17 bits par numéro. Parce que vous aurez dans tous les cas, ont des affrontements à tous les niveaux avec ce codage, vous pouvez réellement obtenir en dessous de ce. En attendant que nous stockons 1000 nombres, on peut déjà économiser un total de 250 bits pour les affrontements au premier niveau. Meilleur test le code correct sur les données de l'exemple.
- droit, et en remarquant que, par exemple, 1000 nombres ne peuvent pas avoir plus de 100 différents les deux derniers chiffres, la trie pourraient être réduits de manière significative au cours de la dernière niveaux.
- Les feuilles pourraient être réduites au dernier niveau, car il n'y a pas d'enfants. Cependant, les feuilles lors de la deuxième à dernier niveau besoin de 2^10=1024 unis (chaque dernier chiffre peut être allumé ou éteint), de sorte qu'il n'est pas réductible dans ce cas, il n'y a que 1000 numéros. Cela signifie que le nombre de pire-cas des pointeurs reste à 3114 (voir mon commentaire sur Misha réponse), alors que les feuilles nécessaires va à 5+10+100+1000+1000+10=2125, ce qui ne change pas le besoin de 12 octets pour chaque pointeur. Ainsi, cela met toujours un trie solution à 4671 octets en considérant seulement les pointeurs seul.
- pas sûr que je reçois votre "chaque dernier chiffre peut être activé ou désactivé" argument. Tous les numéros à 10 chiffres, non?
- Oui. Je voulais dire que chaque seconde à la dernière (9) de la feuille peut avoir un pointeur à 0 ou il ne pourrait pas, pourrait avoir un pointeur sur 1 ou pas, .., et pourrait avoir un pointeur vers 9 ou pas.
- Évidemment, c'est précisément l'un pointeur qui pointe vers le nœud sur le niveau 10 représentant le dernier chiffre dans le nombre.
- Avec seulement un pointeur sur la deuxième à la dernière feuille, comment voulez-vous représenter 11110 et 11111 dans un trie?
InformationsquelleAutor aioobe
15

J'ai entendu parler de ce problème avant (mais sans d'abord-5-chiffres-sont-la même hypothèse), et de la façon la plus simple de le faire était Riz De Codage:

1), Puisque l'ordre n'a pas d'importance, nous pouvons trier et enregistrer seulement les différences entre les valeurs consécutives. Dans notre cas, la moyenne des différences serait 100.000 /1000 = 100

2) Coder les différences à l'aide de Riz codes (de la base de 128 ou 64) ou encore les codes de Golomb (base de 100).

EDIT : Une estimation pour le Riz de codage avec la base de 128 (pas parce qu'il donnerait de meilleurs résultats, mais parce que c'est plus facile à calculer):

Nous allons enregistrer la première valeur-est (32 bits).

Le reste de 999 valeurs sont les différences (nous nous attendons à être de petite taille, 100 en moyenne) contiendra:

unaire valeur value /128 (nombre variable de bits + 1 bit comme terminator)

valeur binaire pour value % 128 (7 bits)

Nous avons à estimer en quelque sorte les limites (nous allons l'appeler VBL) pour le nombre variable de bits:

limite inférieure: considérons que nous sommes chanceux, et aucune différence n'est plus grand que notre base (128 dans ce cas). cela signifie donner à 0 des bits supplémentaires.

limite haute: depuis toutes les différences plus petit que la base sera codé en binaire partie du nombre, le nombre maximal, nous aurions besoin de coder en unaire est 100000/128 = 781.25 (même moins, parce que nous ne nous attendons pas plus de différences à zéro).

Alors, le résultat est 32 + 999 * (1 + 7) + variable(0..782) bits = 1003 + variable(0..98) octets.
- Pouvez-vous donner plus de détails sur la façon dont vous êtes l'encodage et sur le dernier calcul de la taille. 1101 octets ou 8808 bits semble très très proche de la limite théorique de 8091 bits, donc je suis très surpris, qu'il est possible d'obtenir quelque chose comme cela dans la pratique.
- Ne serait-il pas 32 + 999 * (1 + 7 + variable(0..782)) bits? Chaque 999 numéros besoin d'une représentation de value / 128.
- non, si tous sont dans la gamme de 5 chiffres. C'est parce que nous nous attendons à ce que la somme de toutes ces différences (rappelez-vous, nous encoder les différences entre les valeurs consécutives, et non pas entre la première et la Nième valeur) serait inférieure à 100000 (même dans le pire des cas)
- Vous avez besoin d'34 bits au lieu de 32 bits pour représenter la première valeur (9,999,999,999 > 2^32 = 4,294,967,296). Aussi, la différence maximale serait 00000 à 99001 étant donné que les numéros sont uniques, ce qui permettrait d'ajouter 774 1 à la place de 782 pour la base de 128. C'est ainsi que votre gamme de stockage de 1 000 numéros de la base de 128 est 8026-8800 bits ou 1004-1100 octets. 64-bits de la base de donne de meilleurs de stockage, avec des plages de 879-1072 octets.
- très intelligent.
- Je peux voir pourquoi nous avons besoin d'34 bits pour la première valeur et pourquoi nous avons besoin de 100.000/1000=100 moyenne des différences et la différence maximale est de 99.001 Aussi je comprends que nous avons besoin de 7+1 bits selon le lieu de codage, Ce que je ne peux pas comprendre, c'est pourquoi nous ajoutons seulement une fois que le VBL dans votre équation. Vous avez dit que "nous nous attendons à ce que la somme de toutes ces différences seraient en dessous des 100.000". Mais, la somme va nous aider? Supposons que j'ai les numéros de 00001,20001,70001,99003,99004,99005... Si nous n'avons qu'une somme, la hep-nous à comprendre, si nous parlons de 20001 ou 700001? - alex
- c'est ce que Kirk a demandé. Dans votre exemple, en codant une fois le 20k différence entre les deux premières valeurs, seulement 80k de portée maximale sera possible de se produire dans l'avenir. Cela permettra d'utiliser jusqu'à 20k/128 = 156 unaire bits de maximum 782 (qui correspondent à 100k)
- Nice.;seulement me battre pour elle, par une nuance de moins de cinq ans.
InformationsquelleAutor ruslik
7

C'est un puits de savoir problème de la Bentley de Programmation de Perles.

Solution:
Bande les cinq premiers chiffres de ce que les nombres sont les mêmes pour tous
numéro. Utilisez ensuite au niveau du bit-opérations pour représenter le reste 9999 possible
de la valeur. 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 téléphone livre.

Pour imprimer tous les numéros, il suffit d'imprimer tous les numéros où le bit est mis
concatened avec le préfixe. À la recherche pour un nombre donné de faire le nécessaire bits
l'arithmétique à vérifier au niveau du bit de la représentation du nombre.

Vous pouvez chercher un numéro dans O(1) et l'espace de l'efficacité est maximale en raison du peu represenatation.

HTH Chris.
- Ce serait une bonne approche pour une densité de jeu de nombres. Malheureusement, ici, l'ensemble est de très rares: il y a seulement 1 000 numéros de possible de 100 000. Cette approche serait donc en moyenne besoin de 100 bits par numéro. Voir ma réponse pour une alternative qui ne nécessite qu' ~17 bits.
- Ne serait-il pas temps qu'il faut pour imprimer tous les nombres proportionnels à 100 000 au lieu de 1 000?
- En combinant les deux idées que vous obtiendrez la trie immédiatement. À l'aide d'un bitvector avec 100 000 entrées est overallocating et prend beaucoup d'espace. Cependant O(log(n)) de recherche est souvent trop lent (dépend du nombre de requêtes ici). Donc, à l'aide d'une hierachie des ensembles de bits pour l'indexation permet de stocker au maximum de 17 bits par nombre, tout en continuant le O(1) recherche. De cette façon, le trie des œuvres. Aussi l'heure de l'impression est en O(n) pour la trie, dont il hérite de la triés cas.
- Ce n'est pas "le plus efficace d'économiser de l'espace de manière à le faire".
InformationsquelleAutor Chris
5

Fixes de stockage de 1073 octets pour 1 000 numéros:

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

Préfixe:

Nos 5 chiffres préfixe prend le premier 17 bits.

Groupement:

Ensuite, nous avons besoin de trouver une bonne taille de regroupement pour les nombres. Nous allons essayer d'avoir environ 1 nombre par groupe. Puisque nous savons qu'il ya environ 1000 numéros de stocker, de nous diviser à 99 999 sur 1000 parties. Si nous avons choisi le groupe de taille de 100, il n'y aurait bits perdus, essayons donc d'un groupe de taille de 128, ce qui peut être représenté avec 7 bits. Cela nous donne 782 groupes de travailler avec.

Compte:

Ensuite, pour chacun des 782 groupes, nous avons besoin de stocker le nombre d'entrées dans chaque groupe. 7-nombre de bits pour chaque groupe de rendement 7*782=5,474 bits, ce qui est très inefficace, parce que le nombre moyen représenté est d'environ 1 à cause de la façon dont nous avons choisi nos groupes.

Ainsi, au lieu de cela, nous avons de taille variable compte avec pointe 1 est pour chaque nombre dans un groupe suivi par un 0. Ainsi, si nous avions x numéros dans un groupe, nous aurions x 1's suivie par un 0 pour représenter le comte. Par exemple, si nous avions 5 numéros dans un groupe, le comte serait représentée par 111110. Avec cette méthode, si il y a 1000 numéros de nous retrouver avec 1000 1 et 782 0 pour un total de 1000 + 782 = 1,782 bits pour le compte.

Offset:

Enfin, le format de chaque numéro sera juste les 7 bits de décalage pour chaque groupe. Par exemple, si 00000 et 00001 sont les seuls numéros dans le 0-127 groupe, les bits de ce groupe devrait être 110 0000000 0000001. En supposant de 1 000 numéros, il y aura de 7 000 bits pour les décalages.

Ainsi, notre décompte final en supposant de 1 000 numéros est comme suit:
```
17 (prefix) + 1,782 (counts) + 7,000 (offsets) = 8,799 bits = 1100 bytes
```
Maintenant, nous allons vérifier si notre groupe-sélection de la taille par l'arrondissement jusqu'à 128 bits est le meilleur choix pour la taille du groupe. Le choix de x que le nombre de bits pour représenter chaque groupe, la formule de la taille de l'est:
```
Size in bits = 17 (prefix) + 1,000 + 99,999/2^x + x * 1,000
```
La diminution de cette équation pour les valeurs entières de x donne x=6, qui rendements nets 8 580 bits = de 1 073 octets. Ainsi, notre idéal de stockage est comme suit:
- Taille du groupe: 2^6 = 64
- Nombre de groupes: à 1 562
- Totale de stockage:
  
  1017 (prefix plus 1's) + 1563 (0's in count) + 6*1000 (offsets) = 8,580 bits = 1,073 bytes
InformationsquelleAutor Briguy37
1

De prendre cela comme une affaire purement théorique problème et en laissant la mise en œuvre asside, la seule et la plus efficace consiste à indexer tous les ensembles possibles de 10000 derniers chiffres à une gigantesque table d'indexation. En supposant que vous avez pétantes 1000 numéros, vous aurait 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, parce qu'alors, vous avez deux jeux qui sont identifiés avec le même état.

Problèmes avec cela est que vous devrez vous représenter chacun des 2^8000 de jeux dans votre programme comme un lut, et même pas de google serait à distance capable de cela.

De recherche serait en O(1), impression de tous les numéro de O(n). Insertion serait O(2^8000), ce qui en théorie est O(1), mais dans la pratique, est inutilisable.

Dans une interview, je tiens seulement à donner cette réponse, si j'étais sûr, que la société est à la recherche de quelqu'un qui est capable de penser hors de la boîte, beaucoup. Sinon, cela peut vous faire ressembler à un théoricien sans monde réel préoccupations.

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

Étapes pour construire la mise en œuvre:
1. Prendre une constante tableau de taille 100 000*(1000 choisissez 100 000) bits. Oui, je suis conscient du fait que ce tableau aura besoin de plus d'espace que d'atomes dans l'univers par plusieurs ordres de grandeur.
2. Séparer ce grand tableau en morceaux de 100 000 chacun.
3. Dans chaque morceau de 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 permettra de construire un gigantesque LUT qui peut maintenant être utilisé dans un programme. Constante des trucs du programme est normalement pas comptabilisés pour le calcul de l'efficacité de l'espace, de sorte que nous ne se soucient pas de ce tableau, quand on fait nos calculs finaux.

Ici est de savoir comment utiliser ce LUT:
1. Quand quelqu'un vous donne 1000 numéros, vous pouvez stocker les cinq premiers chiffres séparément.
2. De découvrir quels sont les morceaux de votre tableau correspond à ce jeu.
3. Stocker le numéro de l'ensemble dans un seul 8074 nombre de bits (appelons c).
Cela signifie pour le stockage, nous avons seulement besoin 8091 bits, qui nous ont prouvé ici pour être la meilleure de l'encodage. Trouver le bon morceau cependant prend O(100 000*(100 000 choisir 1000)), qui, selon les règles mathématiques est O(1), mais dans la pratique, toujours plus long que le temps de l'univers.

De recherche est simple:
1. bande des cinq premiers chiffres (nombre restant sera appelé n').
2. test si elles correspondent
3. Calculer i=c*100000+n'
4. Vérifier si le bit i dans la table de conversion est fixé à un
Impression de tous les chiffres est simple aussi (et prend O(100000)=O(1) en fait, parce que vous devez toujours vérifier tous les bits du segment actuel, de sorte que j'ai mal calculé ci-dessus).

Je n'appellerais pas cela une "mise en œuvre", en raison de la violation flagrante des limites (de la taille de l'univers et le temps, cet univers a vécu ou cette terre existera). Cependant, en théorie, c'est la solution optimale. Pour les petits problèmes, ce qui en fait peut être fait, et parfois va être fait. Par exemple le tri des réseaux sont un exemple de cette façon de coder, et peut être utilisé comme une étape finale dans récursive algorithmes de tri, d'obtenir une grosse accélération.
- Quel est le plus efficace économie de l'espace façon de le faire ?
- Quand à faire des calculs de temps d'exécution de l'espace, ce qui peut facilement être avéré pour être le plus efficace d'économiser de l'espace moyen, parce que vous énumérez tous les états possibles du système avec un seul numéro. Il n'y a pas de petites codant pour ce problème. L'astuce pour cette réponse, c'est que le programme de taille est presque jamais pris en considération, lorsque la méthode de calcul (essayez de trouver une réponse qui prend cela en compte, et vous verrez ce que je veux dire). Donc, pour tout problème qui a une taille lié, vous pouvez toujours énumérer tous les états, afin d'obtenir le plus d'économiser de l'espace façon de le gérer.
InformationsquelleAutor LiKao
1

C'est équivalent à stocker un millier d'entiers non négatifs chacun moins de 100 000 habitants. Nous pouvons utiliser quelque chose comme l'arithmétique codage pour ce faire.

En fin de compte, les numéros seront stockés dans une liste triée. Je remarque que la différence attendue entre les numéros de la liste est de 100 000/1000 = 100, ce qui peut être représenté sur 7 bits. Il y aura aussi de nombreux cas où plus de 7 bits sont nécessaires. Une façon simple de représenter ces cas fréquents d'adopter l'utf-8 schéma où un octet représente 7 bits entier, sauf si le premier bit est défini, dans lequel cas l'octet suivant est lu pour produire un 14 bits entier, à moins que son premier bit est défini, dans lequel cas l'octet suivant est lu pour représenter un 21-bit integer.

Si au moins la moitié de la différences entre les nombres entiers consécutifs peut être représenté par un octet, et presque tout le reste ont besoin de deux octets. Quelques chiffres, séparés par plus de différences que de 16,384, aura besoin de trois octets, mais il ne peut y avoir plus de 61 de ces. Le moyen de stockage puis sera d'environ 12 bits par numéro, ou un peu moins, ou tout au plus de 1500 octets.

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

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

InformationsquelleAutor Crosbie
1

Juste pour demander rapidement une raison que nous ne voulons pas changer les chiffres dans une base 36. Il ne peut pas gagner autant d'espace, mais il serait à coup sûr gagner du temps sur la recherche depuis u sera à regarder beaucoup moins de 10digts. Ou je les diviser en fichiers en fonction de chaque groupe. j'ai donc le nom de fichier (111)-222.txt et puis je tiens seulement à stocker les numéros qui correspondent à ce groupe et puis il y avoir seearchable dans l'ordre numérique de cette façon, je peux toujours vérifier pour voir si le fichier de sortie. avant de me lancer un biger de recherche. ou, pour être correct, je voudrais exécuter le binaire d'un morceau un pour le fichier pour voir s'il la quitte. et un autre bonary de recherche sur le contenu du fichier

InformationsquelleAutor WojonsTech
0

Pourquoi ne pas garder ça simple? Utiliser un tableau de structures.

Si nous pouvons sauver les 5 premiers chiffres comme une constante, de sorte oublier ceux pour l'instant.

65535 est plus qui peuvent être stockées dans une 16-bits, et le nombre maximum que nous pouvons avoir est 99999, qui s'inscrit dans le 17ème numéro du bit avec un max de 131071.

En utilisant 32 bits types de données est un vaste, parce que nous avons seulement besoin de 1 bit de ce supplément de 16 bits...donc, on peut définir une structure qui a une valeur booléenne (ou caractère) et de 16 bits nombre..

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, 3000 octets au total. Nous avons réduit le total de l'espace de 25%!

Aussi loin que le stockage des nombres, on peut faire simple au niveau du bit mathématiques
```
overflow = (number5digits & 0x10000) >> 4;
number = number5digits & 0x1111;
```
Et à l'inverse de
```
//Something like this should work
number5digits = number | (overflow << 4);
```
D'imprimer la totalité d'entre eux, on peut utiliser une simple boucle sur le tableau. Récupération d'un nombre spécifique qui se passe en temps constant, bien sûr, puisque c'est un tableau.
```
for(int i=0;i<1000;i++) cout << const5digits << number5digits << endl;
```
De recherche pour un certain nombre, nous voulons un tableau trié. Ainsi, lorsque les numéros sont enregistrés, trier le tableau (je choisirais une sorte de fusion personnellement, O(nlogn)). Maintenant, à la recherche, je voudrais aller de fusion tri approche. Diviser le tableau, et voir lequel notre nombre se situe entre les deux. Puis appeler la fonction uniquement sur ce tableau. De manière récursive le faire jusqu'à ce que vous avez un match et le retour à l'index, sinon, il n'existe pas d'imprimer un code d'erreur. Cette recherche serait assez rapide, et au pire des cas c'est toujours mieux que O(nlogn), car il sera absolument exécuter en moins de temps que la fusion de tri (seulement recursing 1 côté de la séparation, chaque fois, au lieu de deux côtés :)), qui est en O(nlogn).

InformationsquelleAutor jyore
0

Ma solution: dans le meilleur des cas 7.025 bits/nombre de, pire des cas 14.193 bits/nombre, moyenne approximative 8.551 bits/nombre. Flux codé, pas d'accès aléatoire.

Même avant de lire ruslik réponse, j'ai immédiatement pensé à l'encodage de la différence entre chaque numéro, car il sera petit et doit être relativement stable, mais la solution doit également être en mesure d'accueillir le pire des cas. Nous avons un espace de 100000 nombres qui contiennent seulement 1000 numéros. Dans une parfaite uniformité de l'annuaire téléphonique, chaque numéro serait plus grand que le précédent nombre par 100:

55555-12345

55555-12445

55555-12545

Si c'était le cas, il faudrait zéro de stockage pour coder les différences entre les nombres, car il est connu constante. Malheureusement, le nombre peut varier de l'idéal étapes de 100. Je voudrais coder la différence de l'idéal de l'incrément de 100, de sorte que si deux nombres adjacents diffèrent par 103, je voudrais encoder le nombre 3, et si deux nombres adjacents diffèrent en 92, je voudrais encoder -8. J'appelle le delta de l'idéal de l'incrément de 100 le “variance”.

L'écart peut varier de -99 (c'est à dire deux numéros consécutifs) à 99000 (l'ensemble du répertoire est composé de chiffres 00000...00999 et un autre plus loin-loin nombre 99999), qui est une plage de 99100 valeurs possibles.

J'avais pour objectif d'allouer un minimum de stockage pour encoder les différences les plus fréquentes et de développer les capacités de stockage si je rencontre de plus grandes différences (comme ProtoBuf’s varint). Je vais utiliser des morceaux de sept bits, six pour le stockage et un indicateur supplémentaire peu à la fin pour indiquer que cet écart est stocké avec un autre morceau après l'actuel, jusqu'à un maximum de trois morceaux (qui est de fournir un maximum de 3 * 6 = 18 bits de stockage, qui sont 262144 possible de la valeur, plus que le nombre de possibles écarts (99100). Chaque morceau qui suit d'un faux-drapeau a les bits d'une plus grande importance, de sorte que le premier morceau a toujours des bits de 0 à 5 ans; la seconde, facultative, de morceaux de a bits 6 à 11, et la troisième contient les bits 12 à 17 ans.

Un seul morceau fournit six bits de stockage qui peut accueillir 64 valeurs. Je voudrais une carte de 64 plus petit des écarts à tenir dans ce seul morceau (c'est à dire les écarts de -32 à +31) donc je vais utiliser ProtoBuf ZigZag encodage, jusqu'à les écarts de -99 à +98 (car il n'y a pas besoin d'un écart négatif au-delà de -99), à quel point je vais passer régulièrement l'encodage, compensée par 98:
```
 De 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 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 écarts seraient codées sous forme de bits, y compris le drapeau pour indiquer un supplément de morceau:
```
 De Variance | Codé Bits 
-----------+---------------- 
0 | 000000 0 
5 | 001010 0 
-8 | 0 001111 
-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 
```
Donc les trois premiers chiffres d'un échantillon de téléphone livre serait codé 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 
```
Meilleur des cas, le téléphone livre est un peu distribuée de manière uniforme et il n'y a pas deux numéros de téléphone qui ont une variance supérieure à 32, de sorte qu'il serait d'utilisation 7 bits par numéro de plus de 32 bits pour le numéro de départ pour un total de 32 + 7*999 = 7025 bits.

Un mixte scénario, où 800 numéros de téléphone de la variance s'inscrit dans un chunk (800 * 7 = 5600), 180 numéros fit en deux morceaux chacun (180 * 2 * 7 = 2520) et 19 numéros de l'ajustement en trois morceaux chacun (20 * 3 * 7 = 399), ainsi que l'32 bits, les totaux 8551 bits.

Pire des cas, 25 numéros d'ajustement en trois morceaux (25 * 3 * 7 = 525 bits) et le reste du 974 numéros fit en deux morceaux (974 * 2 * 7 = 13636 bits), plus de 32 bits pour le premier numéro, pour un grand total de 14193 bits.
```
 Montant de codé numéros | 
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 des optimisations supplémentaires qui peuvent être effectuées pour réduire l'espace requis:
1. Le troisième morceau n'a pas besoin de les sept bits, c'est peut être juste cinq bits et sans drapeau bits.
2. Il peut y avoir un passage initial des nombres pour calculer la meilleure tailles pour chaque morceau. Peut-être pour un certain répertoire, il serait optimal d'avoir le premier morceau ont 5+1 bits, le deuxième 7+1 et le troisième 5+1. Qui permettrait de réduire la taille d'un minimum de 6*999 + 32 = 6026 bits, et deux ensembles de trois bits pour stocker la taille des blocs 1 et 2 (bloc 3 est le reste de l'requis 16 bits) pour un total de 6032 bits!
3. Le même passage initial peut calculer une meilleure attendus de l'incrément de la valeur par défaut de 100. Peut-être il y a un livre de téléphone qui commence à partir de 55555-50000, et il en est ainsi de la moitié le nombre de la plage de l'attendu de l'incrément est de 50. Ou peut-être il y a une distribution non linéaire (écart-type peut-être), et quelques autres optimal devrait incrément peut être utilisé. Cela permettrait de réduire le typique de la variance et peut permettre à un encore plus petit premier morceau à être utilisé.
4. En outre, l'analyse peut être effectuée au cours du premier laissez-passer pour permettre le livre de téléphone pour être partitionné, chaque partition d'avoir son propre prévu d'incrémentation et de taille de bloc optimisations. Cela permettrait un plus petit premier morceau de la taille pour certaines très homogène des pièces du répertoire (en réduisant le nombre de bits de consommation) et de plus gros morceaux de tailles pour les non-uniforme des pièces (en réduisant le nombre de bits perdu sur la poursuite des drapeaux).
InformationsquelleAutor Allon Guralnek
0

La vraie question est l'une de stocker cinq chiffres des numéros de téléphone.

Le truc, c'est que vous auriez besoin de 17 bits pour stocker la gamme de nombres de 0..99 999 habitants. Mais le stockage de 17 bits sur les classiques de 8 octets limites de mot est un souci. C'est pourquoi ils demandent si vous pouvez le faire en moins de 4k en n'utilisant pas les nombres entiers de 32 bits.

Question: sont tous les nombres de combinaisons possibles?

En raison de la nature du système téléphonique, il y a peut être moins de 65k combinaisons possibles. Je vais supposer que oui parce que nous parlons de ce dernier cinq positions dans le numéro de téléphone, par opposition à la zone de code ou de l'échange de préfixes.

Question: est-ce que cette liste soit statique ou s'il aura besoin de l'appui des mises à jour?

Si c'est statique, puis, quand vient le temps de remplir la base de données, compter le nombre de chiffres < 50 000 et le nombre de chiffres >= 50 000 habitants. Allouer deux tableaux de uint16 de longueur appropriée: l'un pour les entiers en dessous des 50 000 et l'autre pour le plus élevé ensemble. Lors du stockage des entiers dans le haut du tableau, soustraire 50 000 et lors de la lecture des nombres entiers du tableau, ajouter 50 000. Maintenant, vous avez stocké votre des entiers de 1 000 à 2 000 de 8 octets mots.

De bâtiment de l'annuaire, deux entrée traversals, mais les recherches doivent se produire dans la moitié du temps, en moyenne, qu'ils ne le feraient avec un seul tableau. Si la recherche de l'époque était très important que vous pourriez utiliser plusieurs tableaux pour les plus petites gammes, mais je pense à ces tailles de votre performance lié serait tirant les tableaux à partir de la mémoire et 2k sera probablement cachette en cache du PROCESSEUR si vous inscrivez pas de l'espace sur tout ce que vous pourriez être à l'aide de ces jours.

Si c'est dynamique, allouer un tableau de 1000 uint16, et ajouter les numéros dans l'ordre de tri. Définir le premier octet de 50,001, et de définir le deuxième octet à une valeur nulle, comme NULL ou de 65 000. Lorsque vous stockez les nombres, les ranger dans l'ordre de tri. Si un nombre est inférieur à 50,001 puis le stocker avant la 50,001 marqueur. Si un nombre est 50,001 ou plus, de le stocker après la 50,001 marqueur, mais de soustraire 50 000 de la valeur stockée.

Votre tableau devrait ressembler à quelque chose comme:
```
00001 = 00001
12345 = 12345
50001 = reserved
00001 = 50001
12345 = 62345
65000 = end-of-list
```
Donc, quand vous regardez un numéro dans le répertoire, vous allez parcourir le tableau et si vous avez touché le 50,001 valeur que vous commencez à ajouter de 50.000 à votre tableau de valeurs.

Ce fait insère très cher, mais les recherches sont faciles, et vous n'allez pas dépenser beaucoup plus que 2k sur le stockage.

InformationsquelleAutor dannyman

Vous devez vous connecter pour publier un commentaire.

Ma solution: dans le meilleur des cas 7.025 bits/nombre de, pire des cas 14.193 bits/nombre, moyenne approximative 8.551 bits/nombre. Flux codé, pas d'accès aléatoire.