algorithme de recherche rapide des fichiers pour les adresses IP

Question

Question

Quel est le meilleur moyen de trouver si une adresse IP existe dans un fichier qui contient des adresses IP triées comme:

219.93.88.62 
219.94.181.87 
219.94.193.96 
220.1.72.201 
220.110.162.50 
220.126.52.187 
220.126.52.247 

Contraintes

• Aucune base de données (par exemple, MySQL, PostgreSQL, Oracle, etc.)
• prétraitement Infrequent est autorisé (voir la section possibilités)
• serait bien de ne pas avoir à charger le fichier chaque requête (131Ko)
• utilise de moins de 5 méga-octets d'espace disque
• Aucun modules PHP supplémentaires

Détails du fichier

• une adresse IP par ligne
• 9500+ lignes

Solutions possibles

• Créer une hiérarchie de répertoires (radix tree?) Puis utilisez is_dir() (malheureusement, il utilise 87 méga-octets)

Answer 1

balayage de la ligne de fichiers en ligne pour trouver une adresse IP semble comme une douleur si vous avez 9000 non-correspondances pour vérifier avant d'arriver à 232.0.17.1

Votre fichier contraint à un seul fichier? par exemple. disons que cette liste est interdite IPs et vous voulez juste voir si on est "dans" la liste.

si vous avez fait un DIR pour contenir plusieurs fichiers:

BannedIPs 
    +- 0.ips 
    +- 1.ips 
    +- 37.ips 
    +- 123.ips 
    +- 253.ips 
    +- 254.ips 

Chaque fichier ne contient que des adresses IP qui commencent par ce numéro.

Si vous étiez assez chanceux pour avoir une distribution égale ... vous auriez 256 fichiers, mais chacun aurait seulement ~ 37 entrées.

Ainsi, lorsque vous voulez tester: 232.0.17.1 vous regardez dans le fichier 232.ips et le recherche.

Answer 2

Depuis votre fichier stocke les adresses IP dans l'ordre de tri, vous pouvez déjà trouver rapidement une adresse IP spécifique i n O (log (n)) en utilisant une recherche binaire. Si vous voulez accélérer encore plus, vous pouvez mettre en cache par exemple toutes les 100 lignes en mémoire et utiliser d'abord une recherche binaire en mémoire, puis vous savez quelle partie du fichier vous devez lire pour terminer la recherche .

Cela dit 131kB est vraiment pas grand-chose, donc la solution la plus simple et la plus rapide est d'acheter plus de mémoire cache et le fichier entier en mémoire dans une table de hachage.

Answer 3

EDIT Je n'ai pas remarqué l'étiquette php, je ne sais pas si le genre de chose suivante est possible dans cette langue. Mais je vais le laisser à l'idée de toute façon.

Une adresse IPv4 est représentable en tant que numéro 32 bits, donc je juste faire un tableau de int32, traduire vos adresses dans le « ints` avec les éléments suivants psuedocode Python-ish:

x = 0 
i = 24 
s = '111.222.333.444' 
for part in s.split('.'): 
    x += part.toint() << i 
    i -= 8 
IPlist.append(x) 

ensuite, vous pouvez obtenir l'adresse d'entrée, le convertir en un int de la même façon, et faire la recherche binaire sur le tableau.

Pour k ~ 10 lignes, le tableau prendra ~ 40 kilo-octets.

Answer 4

peut-être pas rapide, mais je vais essayer ceci: Si le fichier d'adresse IP ne change pas beaucoup, lire le fichier dans un tableau et le cache (peut-être Memcache) et la recherche à partir de là toutes les demandes.