Fast file search algorithm for IP addresses
- by Dave Jarvis
Question
What is the fastest way to find if an IP address exists in a file that contains IP addresses sorted as:
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
Constraints
No database (e.g., MySQL, PostgreSQL, Oracle, etc.).
Infrequent pre-processing is allowed (see possibilities section)
Would be nice not to have to load the file each query (131Kb)
Uses under 5 megabytes of disk space
File Details
One IP address per line
9500+ lines
Possible Solutions
Create a directory hierarchy (radix tree?) then use is_dir() (sadly, this uses 87 megabytes)