Voici une amélioration à 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 bits en utilisant une méthode et 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 constitué par le premier 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 lesquels le premier m bits sont à 1...11 - cette dernière décompte de 1000(décimal). Il y a 2^m tel compte 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.)
Le dernier 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
ce 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, le m-nombre de bits M) et de sa faible k=10 bits (le nombre K). Nous nous trouvons aujourd'hui le numéro un[M-1] de la réduction des numéros de téléphone pour lesquels le premier m chiffres sont au plus M - 1, et le numéro un[M] de la réduction des numéros de téléphone pour lesquels le premier m chiffres sont au plus M, à la fois à partir du premier bloc de bits. Nous avons maintenant vérifier entre l' 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).
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 la 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 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 va mal avec la frontière 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!
