algorithme de recherche rapide de fichiers pour les adresses IP

Question

Question

Quel est le meilleur moyen de trouver si une adresse IP existe dans un fichier contenant des adresses IP classés 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

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

Détails du fichier

• Une adresse IP par ligne
• 9500+ lignes

Solutions possibles

• Créer une hiérarchie de répertoires ( radix arbre ?) puis utilisez is_dir() (malheureusement, cette utilisation 87 méga-octets)

Answer 1

Numérisation 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 IP et que vous voulez juste voir si l'on est « dans » la liste.

Que faire 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 les adresses IP qui commencent par ce nombre.

Si vous avez eu la chance d'avoir la distribution même ... vous auriez 256 fichiers, mais chacun aviez 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

Étant donné que vos fichier stocke les adresses IP dans l'ordre de tri déjà vous pouvez rapidement trouver une adresse IP spécifique dans O (log (n)) en utilisant une recherche binaire.

Si vous voulez accélérer ce encore plus loin, vous pouvez mettre en cache par exemple tous les 100 rangs en mémoire et utiliser une recherche binaire d'abord en mémoire, alors vous savez quelle partie du fichier que 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é la balise 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, alors que je venais de faire un tableau de int32, traduisez 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 ~ 10 k 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 cache (peut-être Memcache) et la recherche à partir de là toutes les demandes.