IP adresleri için hızlı dosya arama algoritması

4 Cevap php

Question

Bir IP adresi olarak sınıflandırılmaktadır IP adreslerini içeren bir dosya varsa bulmak için en hızlı yolu nedir:

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

  • Hayır veritabanı (örneğin, MySQL, PostgreSQL, Oracle, vb)
  • Seyrek ön işleme izin verilir (olasılıklar bölümüne bakınız)
  • Dosyaya her sorguyu yüklemek zorunda değil güzel olurdu (131KB)
  • Disk alanı 5 megabayt altında kullanır
  • Hiçbir ekstra PHP modülleri

File Details

  • Satıra bir IP adresi
  • 9500 + çizgileri

Possible Solutions

  • (radix tree?) Bir dizin hiyerarşisi oluşturma ardından is_dir() (ne yazık ki, bu 87 megabayt kullanir)

4 Cevap

Eğer 232.0.17.1 gelmeden önce kontrol etmek için 9,000 olmayan maçları varsa bir IP bulmak için satır satır dosyayı tarayarak bir ağrı gibi görünüyor

Dosya tek bir dosyaya kısıtlı mı? örneğin Bu liste IP'leri yasaklandı ve sadece tek bir listede "in" olup olmadığını görmek istiyorum söylüyorlar sağlar.

Ne birden fazla dosya içeren bir DIR yaptıysanız:

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

Her dosya sadece bu sayı ile başlayan IP adreslerini içerir.

Hatta dağılımı için şanslı olsaydı ... 256 dosya olurdu, ancak her biri sadece ~ 37 girdileri olurdu.

Test etmek istediğiniz zaman böylece: 232.0.17.1 Eğer 232.ips dosyasına bakmak ve bunun için tarayın.

Dosya mağazalarında yana IP adresleri sıralı düzende zaten hızlı bir ikili arama kullanarak zamandan O belirli bir IP adresi (log (n)) bulabilirsiniz.

Bunu hızlandırmak istiyorsanız o zaman arama bitirmek için okumak gerekir dosyanın hangi bölümü biliyorum, hatta daha bellekte örneğin her 100 satır önbelleğe ve ilk kez bir bellek ikili arama kullanın.

131KB gerçekten bu kadar değil, yani basit ve hızlı bir çözüm daha fazla bellek satın almak ve bir karma tablo bellekte tüm dosya önbelleğe olduğunu söyledi.

Şey şu tip o dilde mümkün olup olmadığını EDIT I php etiketi fark etmedi, ben bilmiyorum. Ama ben yine de fikir için bırakacağım.

Bir IPv4 adresi 32 bitlik bir sayı olarak gösterilebilir, bu yüzden sadece aşağıdaki Python-ish psuedocode ile 'ints `içine adreslerini tercüme, int32 bir dizi yapmak istiyorum:

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

Sonra, giriş adresi alabilirsiniz bir int aynı şekilde dönüştürmek ve dizide ikili arama yapın.

~ 10 k hatları için, dizi ~ 40 Kbyte'ı alacaktır.

Hızlı olmayabilir, ama ben bu denemek istiyorum: IP adresi dosyası çok değişmezse (belki Memcache) bir diziye dosyasını okuyun ve önbelleğe ve her istek üzerine oradan araştırın.

etiketler