Please Forward: Ruby Quiz Submission

ruby-talk
1

From: "Luis Parravicini" <lparravi@gmail.com>
Date: September 15, 2007 8:11:03 AM CDT
To: submission@rubyquiz.com
Subject: Please Forward: Ruby Quiz Submission

I'm sending my solution to the ip-to-country Ruby Quiz. I've done two
scripts, one to read IpToCountry.csv and create another file for quick
access and another to search for the country the ip is in.

The script to search which country a ip is in (ip.rb), uses a binary
file created by the second script (pre-ip.rb) and performs a binary
search on it.
----------------------------------------------------------------------------------------------
require 'readbytes'

# reads the ip range for the record at position pos
def read_ips(f, pos)
  f.pos = pos * 10
  buf = f.readbytes(8)
  [ buf[0, 4], buf[4, 8] ].map { |b| b.unpack('N')[0] }
end

# gets the country for the record at position pos
def get_country(f, pos)
  f.pos = pos * 10 + 8
  f.readbytes(2)
end

# binary search of the ip (based on the binary search at
# http://eigenclass.org/hiki.rb?simple+full+text+search+engine#l20 )
def binary_search(f, ip, from, to)
  while from < to
    middle = (from + to) / 2
    pivot = read_ips(f, middle)

    if ip < pivot[0]
      to = middle
      next
    elsif ip > pivot[1]
      from = middle+1
      next
    end

    if ip >= pivot[0] && ip <= pivot[1]
      return get_country(f, middle)
    else
      return nil
    end
  end
end

# converts the ip in a.b.c.d form to network order
def to_network(ip)
  aux = ip.split('.').map { |x| x.to_i }

  aux[3] + (aux[2] << 8) + (aux[1] << 16) + (aux[0] << 24)
end

ip = ARGV[0]
if ip.nil?
  puts "usage: #{__FILE__} ip_address"
  exit 1
end
ip = to_network(ip)

File.open('ip_country', 'r') do |f|
  f.seek(0, IO::SEEK_END)
  records = f.tell / 10

  country = binary_search(f, ip, 0, records)
  country = 'not found' if country.nil?
  puts country
end
----------------------------------------------------------------------------------------------

This is the script which needs to be run just once before ip.rb can be
used. It reads IpToCountry.csv and creates a binary file of records of
10 bytes each. Each record has an ip range (from, to) and the country
that range belongs to.
----------------------------------------------------------------------------------------------
File.open('ip_country', 'w') do |out|
  File.open('IpToCountry.csv', 'r') do |csv|
    while line = csv.gets do
      next unless line =~ /^"(\d+)","(\d+)"(?:,"[^"]+"){2},"([A-Z]+)"/

      out.write([$1.to_i].pack('N')) # from
      out.write([$2.to_i].pack('N')) # to
      out.write($3[0,2]) # country
    end
  end
end
----------------------------------------------------------------------------------------------

And the times (on a 1.5Ghz Pentium M) are:

$ time ruby ip.rb 190.16.89.91
AR

real 0m0.017s
user 0m0.010s
sys 0m0.000s

The time it takes pre-ip.rb to create the file ip_country:

$ time ruby pre-ip.rb

real 0m2.810s
user 0m2.590s
sys 0m0.020s

--
Luis Parravicini
http://ktulu.com.ar/blog/

ยทยทยท

Begin forwarded message: