论坛首页 → 编程语言技术论坛 →

IPParse： IP 地址查询

浏览 32787 次
锁定老帖子 主题：IPParse： IP 地址查询
该帖已经被评为良好帖
作者 正文
  • wosmvp
  • 等级: 二星会员
  • 性别:
  • 文章: 180
  • 积分: 270
  • 来自: 青岛
   发表时间：2009-02-19  
orange0513 写道
二分查找代码return dichotomizing(arg[0...cen],ip)           if size != 1 && (arg[cen] > ip + '1')
这块好像有bug
IPParse.parse('59.1.32.220')到最后就死循环


这个版本早过时了 
返回顶楼
          回帖地址
0 请登录后投票
  • QuakeWang
  • 等级: 五钻会员
  • 性别:
  • 文章: 854
  • 积分: 2516
  • 来自: 上海
   发表时间：2009-02-19  
JavaEye的IP解析也是用纯真IP数据库查询算法写的，它比较快，而且数据格式比较小，小于10M，可以一次性全部加载到内存。
wosmvp可以谈你一下你的算法吗？做一个2者对比性能测试看看。
返回顶楼
          回帖地址
0 请登录后投票
  • wosmvp
  • 等级: 二星会员
  • 性别:
  • 文章: 180
  • 积分: 270
  • 来自: 青岛
   发表时间：2009-02-19   最后修改：2009-02-19
欢迎一切符合自己应用的修改，
纯真版代码太长，这个版本30行代码都不到，也挺快挺好用
返回顶楼
          回帖地址
0 请登录后投票
  • wosmvp
  • 等级: 二星会员
  • 性别:
  • 文章: 180
  • 积分: 270
  • 来自: 青岛
   发表时间：2009-02-19  
QuakeWang 写道
JavaEye的IP解析也是用纯真IP数据库查询算法写的，它比较快，而且数据格式比较小，小于10M，可以一次性全部加载到内存。
wosmvp可以谈你一下你的算法吗？做一个2者对比性能测试看看。


用的二分
全部代码 
class IPParse
  @@data ||= []
 
  def self.parse(ip)
    return false unless ip.to_s =~ /(\d+\.){3}\d+/ # 简单判断IP格式合法性（当然这样不能保证格式完全正确,实用中传入非法格式的可能性比较少，先这样吧）
    ip,addr = format(ip) , '' #格式化IP地址， 例： 1.4.45.123 格式化为 001.004.045.123
 
    [ip[0,3].to_i,0].each do |f| # 先从IP首位命名的文件中查找，没有则从0.txt文件中查找， IP文件命名格式为 data/123.txt ...

      file = "#{File.dirname(__FILE__)}/../data/#{f.to_s}.txt"
      @@data[f] ||= File.exist?(file) ? File.new(file).to_a : false  # 如果存在文件，缓存取出的文件
 
      if @@data[f]
        addr = dichotomizing(@@data[f],ip) # 二分法查找
        return addr if addr # 找到则返回此值
      end
    end
 
    return "UNKNOW"
  end
 
  protected
  def self.dichotomizing(arg,ip)
    cen = arg.size/2  # 长度取中 center
    cur = arg[cen]    # 中值 current，
       #格式类似 005.149.000.000 005.255.255.255 IANA
    
    #当只有一个元素时，(005.149.000.000..005.255.255.255) 是否包含IP
    return (cur[0,15]..cur[16,15]).include?(ip) ? cur[32...-1] : false if cen == 0
    # 005.149.000.000（前面的IP） > IP 时取前一半
    return dichotomizing(arg[0...cen],ip) if cur[0,15] > ip
    # 005.255.255.255（前面的IP） < IP 时取后一半
    return dichotomizing(arg[cen..-1],ip) if cur[16,15] < ip
    # 如果 此值的前IP < IP < 此值的后IP，则返回此值
    return arg[cen][32...-1]
  end
 
  def self.format(ip)
    ip.to_s.split('.').inject([]) do |s,x|
      s << x.rjust(3,'0')
    end.join('.')
  end
end


速度过会上。
返回顶楼
          回帖地址
0 请登录后投票
  • wosmvp
  • 等级: 二星会员
  • 性别:
  • 文章: 180
  • 积分: 270
  • 来自: 青岛
   发表时间：2009-02-19  
上测试：

纯真IP查询 使用了 orlaa 朋友的
http://gist.github.com/66248

测试环境：
Linux myhost 2.6.28.2 #1 SMP PREEMPT Fri Jan 30 16:03:57 CST 2009 i686 AMD Turion(tm) 64 Mobile Technology MK-38（2.2GHz） AuthenticAMD GNU/Linux,1.5G内存


代码如下 
require 'rubygems'
require 'ipparse'

def search_ip_cz(ip)
  #IP数据文件路径
  #ip='202.38.64.10'
  dat_path = "/home/mvp/Desktop/QQWry.Dat"
   
  #检查IP地址
  # if not ip~=/^d{1,3}.d{1,3}.d{1,3}.d{1,3}$/
  #    return 'IP Address Error'
  # end
  fd = File.open(dat_path, "rb")
   
  ips = ip.split('.')
  ip_num = ips[0].to_i * 16777216 + ips[1].to_i * 65536 + ips[2].to_i * 256 + ips[3].to_i
  data_begin = fd.read(4)
  data_end = fd.read(4)
   
  ipbegin= data_begin.unpack('L').join('').to_i
   
  if ipbegin < 0
    ipbegin += 2**32
  end
   
  ipend= data_end.unpack('L').join('').to_i
   
  if ipend < 0
    ipend += 2**32
  end
   
  ip_allnum = (ipend - ipbegin) / 7 + 1
  begin_num = 0
  end_num = ip_allnum
  ip1_num=0
  ip2_num=0
  ip_addr1=""
  ip_addr2=""
  #使用二分查找法从索引记录中搜索匹配的IP记录
  while ip1_num>ip_num or ip2_num<ip_num
    middle= ((end_num + begin_num) / 2).to_i
     
    #偏移指针到索引位置读取4个字节
    fd.seek(ipbegin + 7 * middle)
    ip_data1 = fd.read(4)
    if ip_data1.length < 4
      fd.close
      return 'System Error'
    end
     
    #提取出来的数据转换成长整形，如果数据是负数则加上2的32次幂
    ip1_num = ip_data1.unpack('L').join('').to_i
    if ip1_num < 0
      ip1_num += 2**32
    end
     
    #提取的长整型数大于我们IP地址则修改结束位置进行下一次循环
    if ip1_num > ip_num
      end_num = middle
      redo
    end
     
     
    #取完上一个索引后取下一个索引
    data_seek = fd.read(3)
    if data_seek.length < 3
      fd.close
      return 'System Error';
    end
     
    data_seek = (data_seek+0.chr).unpack('L').join('').to_i #data_seek = implode('', unpack('L', $data_seek.chr(0)));
     
    fd.seek(data_seek)
     
    ip_data2 = fd.read(4)
     
    if ip_data2.length<4
      fd.close
      return 'System Error'
    end
     
    ip2_num = ip_data2.unpack('L').join('').to_i
    if ip2_num < 0
      ip2_num += 2**32
    end
     
    #没找到提示未知
    if ip2_num < ip_num
    end
     
    if middle == begin_num
      fd.close
      return 'Unknown'
       
    end
     
    begin_num = middle
  end
    
  ip_flag = fd.read(1)
  if ip_flag == 1.chr
    ip_seek = fd.read(3)
    if ip_seek.length < 3
      fd.close
      return 'System Error'
    end
    ip_seek = (ip_seek+0.chr).unpack('L').join('').to_i #implode('', unpack('L', $ip_seek.chr(0)));
    fd.seek(ip_seek)
    ip_flag = fd.read(1)
  end
   
  if ip_flag == 2.chr
    addr_seek = fd.read(3)
    if addr_seek.length < 3
      fd.close
      return 'System Error'
    end
    ip_flag = fd.read(1)
    if ip_flag == 2.chr
      addr_seek2 = fd.read(3)
      if addr_seek2.length< 3
        fd.close
        return 'System Error'
      end
      addr_seek2 =(addr_seek2+0.chr).unpack('L').join('').to_i# implode('', unpack('L', $addr_seek2.chr(0)));
      fd.seek(addr_seek2)
    else
      fd.seek(-1, IO::SEEK_CUR)
    end
     
    while (char = fd.read(1)) != 0.chr
      ip_addr2 += char# ip_addr2 .= char
    end
     
    addr_seek =(addr_seek+0.chr).unpack('L').join('').to_i#$addr_seek = implode('', unpack('L', $addr_seek.chr(0)));
    fd.seek(addr_seek)
     
    while (char = fd.read(1)) != 0.chr
      ip_addr1 += char#$ip_addr1 .= $char;
    end
  else
    fd.seek(-1, IO::SEEK_CUR)
    while ( char = fd.read(1)) != 0.chr
      ip_addr1 += char#ip_addr1 .= char;
    end
     
    ip_flag = fd.read(1)
    if ip_flag == 2.chr
      addr_seek2 = fd.read(3)
      if addr_seek2.length < 3
        fd.close
        return 'System Error'
      end
      addr_seek2 = (addr_seek2+0.chr).unpack('L').join('').to_i#implode('', unpack('L', $addr_seek2.chr(0)));
      fd.seek(addr_seek2)
    else
      fd.seek(-1, IO::SEEK_CUR)
    end
    while (char = fd.read(1)) != 0.chr
      ip_addr2 += char# ip_addr2 .= char
    end
  end
# fd.close
   
  #最后做相应的替换操作后返回结果
  #if(preg_match('/http/i', $ip_addr2)) {
  # $ip_addr2 = '';
  #}
  if (ip_addr2=~/http(\s|\S)/)!=nil
    ip_addr2 = ''
  end
   
  ip_addr = "#{ip_addr1} #{ip_addr2}"
  ip_addr.gsub!(/(\S|\s)*CZ88.(NET|Net)(\S|\s)*/,'')#$ip_addr = preg_replace('/CZ88.Net/is', '', $ip_addr);
   
  #$ip_addr = preg_replace('/^s*/is', '', $ip_addr);
  #$ip_addr = preg_replace('/s*$/is', '', $ip_addr);
  if (ip_addr=~/http(\s|\S)/)!=nil or ip_addr==""
    ip_addr = 'Unknown'
  end
   
 # print ip_addr
  return ip_addr
end

def randip
  4.times.inject([]) {|s,x| s << rand(255) }.join('.')
end
a = []

10000.times { a << randip }
c = 0
a.map {|x|
  10.times{
    t = Time.now
    # search_ip_cz(x)
    IPParse.parse(x)
    c += Time.now.to_f - t.to_f
  }
}
puts c
返回顶楼
          回帖地址
0 请登录后投票
  • wosmvp
  • 等级: 二星会员
  • 性别:
  • 文章: 180
  • 积分: 270
  • 来自: 青岛
   发表时间：2009-02-19  
结果：
~ $ ruby a.rb  （纯真）
131.656655311584
~ $ ruby a.rb  （IPParse）
28.8699994087219
返回顶楼
          回帖地址
0 请登录后投票
  • wosmvp
  • 等级: 二星会员
  • 性别:
  • 文章: 180
  • 积分: 270
  • 来自: 青岛
   发表时间：2009-02-19  
上面的结果是测试1万个随机IP，每个IP测试10次的结果
返回顶楼
          回帖地址
0 请登录后投票
  • orange0513
  • 等级: 初级会员
  • 性别:
  • 文章: 12
  • 积分: 30
  • 来自: java
   发表时间：2009-02-19   最后修改：2009-02-19
wosmvp 写道
QuakeWang 写道
JavaEye的IP解析也是用纯真IP数据库查询算法写的，它比较快，而且数据格式比较小，小于10M，可以一次性全部加载到内存。
wosmvp可以谈你一下你的算法吗？做一个2者对比性能测试看看。


用的二分
全部代码 
class IPParse
  @@data ||= []
 
  def self.parse(ip)
    return false unless ip.to_s =~ /(\d+\.){3}\d+/ # 简单判断IP格式合法性（当然这样不能保证格式完全正确,实用中传入非法格式的可能性比较少，先这样吧）
    ip,addr = format(ip) , '' #格式化IP地址， 例： 1.4.45.123 格式化为 001.004.045.123
 
    [ip[0,3].to_i,0].each do |f| # 先从IP首位命名的文件中查找，没有则从0.txt文件中查找， IP文件命名格式为 data/123.txt ...

      file = "#{File.dirname(__FILE__)}/../data/#{f.to_s}.txt"
      @@data[f] ||= File.exist?(file) ? File.new(file).to_a : false  # 如果存在文件，缓存取出的文件
 
      if @@data[f]
        addr = dichotomizing(@@data[f],ip) # 二分法查找
        return addr if addr # 找到则返回此值
      end
    end
 
    return "UNKNOW"
  end
 
  protected
  def self.dichotomizing(arg,ip)
    cen = arg.size/2  # 长度取中 center
    cur = arg[cen]    # 中值 current，
       #格式类似 005.149.000.000 005.255.255.255 IANA
    
    #当只有一个元素时，(005.149.000.000..005.255.255.255) 是否包含IP
    return (cur[0,15]..cur[16,15]).include?(ip) ? cur[32...-1] : false if cen == 0
    # 005.149.000.000（前面的IP） > IP 时取前一半
    return dichotomizing(arg[0...cen],ip) if cur[0,15] > ip
    # 005.255.255.255（前面的IP） < IP 时取后一半
    return dichotomizing(arg[cen..-1],ip) if cur[16,15] < ip
    # 如果 此值的前IP < IP < 此值的后IP，则返回此值
    return arg[cen][32...-1]
  end
 
  def self.format(ip)
    ip.to_s.split('.').inject([]) do |s,x|
      s << x.rjust(3,'0')
    end.join('.')
  end
end


速度过会上。

我试了下你的这个puts IPParse.parse('222.222.222.222')怎么找不到。而且我不喜欢打开一个文件不自己关闭它。我改成这样了，用的ruby1.9.1所以有最上面那行。不知道有没有什么BUG! 
Encoding.default_external='UTF-8'

require 'benchmark'

class IPParse
   @@data ||= [] 
   def self.parse(ip)
      raise 'WRONT IP ADDRESS' unless ip.to_s =~ /(\d+\.){3}\d+/
      ip.to_s.split('.').each{|i| raise 'WRONT IP ADDRESS' if i.to_i>255	}

      ip= format(ip)
      [ip[0,3].to_i,0].each do |n|
        file="#{File.dirname(__FILE__)}/../data/#{n.to_s}.txt"
        @@data[n] ||= File.exist?(file) ? File.open(file){|f|f.to_a} : false
        if @@data[n]
          addr=dichotomizing(@@data[n],n == 0 ? ip : ip[4,ip.length])
          return addr.strip if addr
        end
      end
      return "UNKNOW"
   end

 private
  def self.dichotomizing(arg,ip)
    size = arg.size
    cen  = size/2
    x=arg[cen].split(/\s+/,3)
    
    return dichotomizing(arg[0...cen],ip)           if size != 1 && x[0] > ip 
    return dichotomizing(arg[cen...size],ip)        if size != 1 && x[1] < ip
    return x[0] <= ip && x[1] >= ip  ? x[2] : false if size == 1
    return x[2]
  end

  def self.format(ip)
    ip.to_s.split('.').inject([]) do |s,x|
      s <<  x.rjust(3,'0')   
    end.join('.')
  end
end

def randip   
  4.times.inject([]) {|s,x| s << rand(255) }.join('.')   
end 

Benchmark.bm{|x|
  x.report{
    10000.times{
      IPParse.parse(randip)
    }
  }
}

返回顶楼
          回帖地址
0 请登录后投票
  • wosmvp
  • 等级: 二星会员
  • 性别:
  • 文章: 180
  • 积分: 270
  • 来自: 青岛
   发表时间：2009-02-19  
确定找不到？
require 'rubygems'
require 'ipparse'
puts IPParse.parse('222.222.222.222') #=> 河北省石家庄市

另外代码你没有测试吧，试了几个全UNKNOW

self.dichotomizing(arg,ip) 方法中的split影响性能，所以换了

性能测试有点问题，这样测试内容将包含randip这个方法的速度了

谢谢，文件竟然没有关闭……
返回顶楼
          回帖地址
0 请登录后投票
  • QuakeWang
  • 等级: 五钻会员
  • 性别:
  • 文章: 854
  • 积分: 2516
  • 来自: 上海
   发表时间：2009-02-19   最后修改：2009-02-19
看了一下代码，简单易懂，和纯真的ip数据库查找算法比起来，都是采用2分法查找ip范围，不同的是你这个用空间换时间，地址信息是重复记录的，速度自然要快很多。

在github上给你pull request，一个简单的性能改进： 
  def self.format(ip)
    ip.to_s.scan(/\d+/).map{|x| x.rjust(3, '0')}.join('.')
  end


另外你可以试试看将这里的代码分开2次写，2个元素的数组用each感觉没有必要，而且block也会有少许的性能损失。 
    [ip[0,3].to_i,0].each do |f|
      #....
    end
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → 编程语言技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics