James Gray
9/16/2007 3:27:00 PM
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