빠른 파일 검색 알고리즘은 주소

IP 주소로 정렬 된 IP 주소가 포함 된 파일에있는 경우 찾을 수있는 가장 빠른 방법은 무엇 :

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

은 제약 조건

파일 세부 사항

가능한 해결책

구체적인 것은 없지만 영감을 줄 수 있습니다. http://www.scribd.com/doc/10988897/IP-Address-Lookup-Algorithms – elias

당신이 당신의 파일을 하나의 파일로 제한되어 232.0.17.1

에 도착하기 전에 확인하는 9,000 비 일치가있는 경우 IP가 고통처럼 보인다 찾을 라인으로 파일 라인을 스캔? 예 : 이 목록이 금지 된 IP라고 말하면 목록에 "들어 있는지"확인하기 만하면됩니다.

이

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

각 파일은 해당 숫자로 시작 IP 주소가 포함 : 여러 파일을 포함하는 디렉터리를 만든 경우 어떻게

배포가 충분할만큼 운이 좋았다면 ... 256 개의 파일을 가질 수 있지만 각각 ~ 37 개의 항목 만 가질 수 있습니다.

따라서 232.0.17.1을 테스트하려면 232.ips 파일을보고 스캔하십시오.

2010-04-18 00:34:51 scunliffe

파일은 이미 정렬 된 순서로 IP 주소를 저장하므로 특정 IP 주소를 빠르게 찾을 수 있습니다. i 이진 검색을 사용하여 n O (log (n)) 시간.

속도를 더 높이려면 메모리에 100 번째 행을 모두 캐시하고 메모리 내 이진 검색을 먼저 수행 한 다음 파일의 어느 부분을 읽어야 검색을 완료해야하는지 알 수 있습니다 .

실제로 131kB는 그리 많지 않으므로 더 간단하고 빠른 솔루션은 더 많은 메모리를 구입하고 해시 테이블의 메모리에 전체 파일을 캐시하는 것입니다.

2010-04-18 00:08:46

EDITphp 태그를 눈치 채지 못했습니다. 그 언어에서 다음 유형의 것이 가능한지 모르겠습니다. 하지만 어쨌든 아이디어로 남겨 둘 것입니다.

IPv4 주소는 32 비트 숫자로 표현할 수있는, 그래서 난 그냥 int32의 배열을 다음 파이썬 틱 psuedocode와 'ints`로 주소를 변환 할 것 :

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

그런 다음 입력 주소를 가져 와서 같은 방식으로 int으로 변환하고 배열에서 이진 검색을 수행 할 수 있습니다.

~ 10 k 라인의 경우 어레이는 ~ 40 kBytes를 사용합니다.

2010-04-18 00:16:13 mtrw

빠르지는 않겠지 만,이 방법을 사용해보십시오. IP 주소 파일이 많이 변경되지 않으면 파일을 배열로 읽어 들여 캐시 (어쩌면 Memcache)를 검색하고 모든 요청에 대해 검색하십시오.

2010-04-18 00:18:30 Shiki

답변