[QUIZ] IP to Country (#139)

ruby-talk
1

I am extremely pleased with my solution this week:

ruby IPToCountry.rb 121.121.121.121

MY
0.000000 0.000000 0.000000 ( 0.000000)

Wrapping the code in 100.times {...}

ruby IPToCountry.rb 121.121.121.121

MY
MY
...
MY
MY
0.062000 0.000000 0.062000 ( 0.078000)

Hmmmm...clearly I'm using a supercomputer. :stuck_out_tongue:

My solution uses no initialization run. Instead, it uses a binary search, making good use of IO#seek and IO#pos. It's a little atypical though - it uses different numbers to compare less than and greater than, and looking at a position really means looking at the first two numbers on the next line.

Here's the code:

require 'benchmark'
puts Benchmark.measure { 100.times {

dot_dec_ip = ARGV[0].chomp

dec_ip = dot_dec_ip[0..2].to_i << 24
dot_dec_ip = dot_dec_ip[(dot_dec_ip.index(?.)+1)..-1]
dec_ip += dot_dec_ip[0..2].to_i << 16
dec_ip += dot_dec_ip[dot_dec_ip.index(?.)+1,3].to_i << 8
#Last 8 bits are all in the same country; they don't matter

dec_ip = dec_ip

dataf = File.new("IPToCountry.csv")

###Begin binary search, finding high and low

#Hardcoded character offset of where to start. This should be the index of
#a character on the last line of comments

···

#
#Earlier versions used 0 or calculated this each iteration.
#The former yielded bad results (for obvious reasons);
#the latter doubled the time needed.
low = 6603

dataf.seek(0,IO::SEEK_END)
flen = dataf.pos

high = flen

while true
  if low == high - 1
    puts "IP not assigned"
    break
  end
  mid = (low + high) >> 1
  dataf.seek(mid,IO::SEEK_SET)
  dataf.gets
  dataf.getc
  range_start = dataf.gets('"')
  range_start.slice!(-1)
  range_start = range_start.to_i
  cmpno = dec_ip <=> range_start
  if cmpno == -1
    high = mid
    next
  else
    dataf.read(2)
    range_end = dataf.gets('"')
    range_end.slice!(-1)
    range_end = range_end.to_i
    if (dec_ip <=> range_end) == 1
      low = mid
      next
    else
      puts dataf.gets.match(/"(\w\w)"/)[1]
      break
    end
  end
end
}}

----- Original Message ----
From: Ruby Quiz <james@grayproductions.net>
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Sent: Friday, September 14, 2007 7:31:41 AM
Subject: [QUIZ] IP to Country (#139)

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

This week's Ruby Quiz is to write a simple utility. Your program should accept
an IP address as a command-line argument and print out the two letter code for
the country that IP is assigned in. You can find a database for the matching
at:

    software77.net

To keep the problem interesting though, let's write our programs with a focus on
speed and memory efficiency.

    $ time ruby ip_to_country.rb 68.97.89.187
    US
    
    real 0m0.314s
    user 0m0.259s
    sys 0m0.053s

____________________________________________________________________________________
Be a better Globetrotter. Get better travel answers from someone who knows. Yahoo! Answers - Check it out.
http://answers.yahoo.com/dir/?link=list&sid=396545469