Begin forwarded message: > From: "Jesse Brown" <jesse.r.brown / gmail.com> > Date: September 16, 2007 9:34:38 AM CDT > To: submission / rubyquiz.com > Subject: [QUIZ] IP to Country (139) > > Here is my solution. > I took the approach of pre-processing the file to make the search > fast. > Basically, I sort the file based on ip ranges then do a binary search > on the file itself. > The preprocess work can take 2-3 seconds, but once that is complete > subsequent searches are much faster. > Some results: > To build the sorted file: > [02:52]:[0]:139 > time ruby sort_file.rb ip.csv > > real 0m2.664s > user 0m2.519s > sys 0m0.114s > > To run the search: > [02:52]:[0]:139 > time ruby ip2country.rb 68.97.89.187 > UNITED STATES > > real 0m0.013s > user 0m0.006s > sys 0m0.006s > > > ====== Begin File: sort_file.rb ======== > #!/usr/bin/env ruby > # > # Jesse Brown > > (puts "Usage: #$0 ip_file" ; exit 1) unless ARGV.length == 1 > > out = File.open("sorted.ip", "w") or fail "open 'sorted.ip' failed" > ips = [] > > File.open(ARGV.shift).each do |line| > > # ignore commented and empty lines > next if line =~ /^\s*$/ > next if line =~ /^#/ > > # we are only interested in the range of ips and the country name > start, stop, w, x, y, z, place = line.strip.split(',') > ips << "%10s:%10s:%50s" % [start.gsub(/"/,''), stop.gsub(/"/,''), > place.gsub(/"/,'')] > > end > > # Sorting allows us to do a binary search on the file itself > out.puts ips.sort.join("\n") > out.close > ====== End File: sort_file.rb ======== > > ====== Begin File: ip2country.rb ======== > #!/usr/bin/env ruby > # > # Jesse Brown > > (puts "Usage: #$0 <ip_address>" ; exit 1) if ARGV.length != 1 > (puts "Run sort_file.rb first" ; exit 2) unless test(?f, "sorted.ip") > > LINE_SZ = 73 # "%10d:%10d:%50s\n" > LINES = File.stat("sorted.ip").size / LINE_SZ > > # Binary search on a file > def bin_search(file, target, front, back) > > return "Not Found" if front > back > > mid = (back - front)/2 > file.pos = (front + mid) * LINE_SZ > > start, stop, place = file.read(LINE_SZ).strip.split(':') > > # if within the current range, report... > return place.lstrip if target >= start.to_i and target <= stop.to_i > > # else recursively search the apropriate half > if target < start.to_i > bin_search(file, target, front, back - mid - 1) > else > bin_search(file, target, front + mid + 1, back) > end > > end > > # Grab and convert the IP. Search > file = File.open("sorted.ip", "r") > a, b, c, d = ARGV.shift.split('.') > target = a.to_i*256**3 + b.to_i*256**2 + c.to_i*256 + d.to_i > puts bin_search(file, target, 0, LINES) > ====== End File: ip2country.rb ======== > > > -- > Jesse Brown