From: "Simon Kröger" <SimonKroeger@...>
Date: 2007-09-16T22:15:06+09:00
Subject: [SOLUTION] [QUIZ] IP to Country (#139)

Hi,

one of the (without a doubt) many binary search solutions. This one reads a 1K
chunk of the file around the current position and uses a regexp to extract
valid lines (and values) from this chunk.

The reasoning behind that is that data from disk is read in blocks anyway (in
most cases even larger than 1K) and the last 2 or 3 iterations of the algorithm
can be avoided. (max depth encountered so far was 14)

Using the regexp frees us from 'manually' looking for newlines (it will find
about 10 valid sets of data in each iteration).

I tried a lot of stuff like biasing the median towards the side where the
solution will be most likely found, using 'static' buffers for the File#read
calls or unrolling the recursion but nothing proofed realy usefull so i decided
to go with the short and fast enough(tm) solution.

------------------------------------------------------------------------------
require 'ipaddr'

class IPAddr
  def country_code()
    open('IpToCountry.csv'){|file| code(file, to_i, 0, file.stat.size)}
  end

  private
  def code(file, ip, min, max)
    median = (min + max) / 2
    file.seek(median - 512)
    ary = file.read(1024).scan(/^"(\d*)","(\d*)","(?:\w*)","(?:\d*)","(\w*)"/)
    return code(file, ip, median, max) if ary.empty? || ary.last[1].to_i < ip
    return code(file, ip, min, median) if ary.first[0].to_i > ip
    ary.find{|l| l[1].to_i >= ip}[2]
  end
end

ARGV.each{|arg| puts IPAddr.new(arg).country_code} if $0 == __FILE__
------------------------------------------------------------------------------

timings:

$ time ruby quiz139.rb 0.0.0.0 68.97.89.187 84.191.4.10 80.79.64.128
210.185.128.123 202.10.4.222 192.189.119.1 255.255.255.255
ZZ
US
DE
RU
JP
AU
EU
ZZ

real    0m0.062s
user    0m0.046s
sys     0m0.030s

cheers

Simon