Matthias Wätcher made a classic mistake this week. He sent in his first
ever
quiz solution and told us not to expect anything special out of it. We
later
learned that it was a lot faster than all of the other solutions, thanks
to more
effort from Matthias. His code taught me some new tricks and I want to
share
those with you.
But first, let’s talk speed.
Most of the solutions are quite quick, relatively speaking. What’s the
shared
secret of speed? Binary search. The records are in sorted order, so
it’s
possible to perform a simple
cut-the-possible-matches-in-half-at-each-step
lookup. That favored algorithm makes short work of what could otherwise
be a
lengthy search.
Now you can do a binary search on the database file as is and several
solutions
did. This is a little trickier, because the records are not of a
standard size.
You have to be super careful not to accidently skip records. While the
solutions handled the challenge very well, you can make things quite a
bit
easier if you are willing to preprocess the file.
You can also speed things up with some clever preprocessing. That was
the other
trick Matthias used to find answers so quickly.
Matthias realized that while the actual records contain quite a bit of
data, we
only really care about the start of a range, the end of a range, and the
country
code. You can fit all of that in just ten bytes with four for each
address and
two for the country.
The file also contains some consecutive ranges that can be collapsed for
the
purposes of our search. Such ranges may differ in some attributes, but
as long
as their country codes are the same we can treat them as a single unit.
Now that you know the goal, let’s take a look at the packing code
Matthias sent
in:
#!/usr/bin/ruby
comment
last_start=nil
last_end=nil
last_country=nil
File.open(“packed-ip.dat”,“wb”) do |wfile|
IO.foreach(“geo-ip.csv”) do |line|
next if !(line =~ /^"/ )
s,e,d1,d2,co=line.delete!(""").split(",")
s,e = s.to_i,e.to_i
if !last_start
initialize with first entry
last_start,last_end,last_country = s,e,co
else
if s==last_end+1 and co==last_country
squeeze if successive ranges have zero gap
last_end=e
else
append last entry, remember new one
wfile << [last_start,last_end,last_country].pack("NNa2")
last_start,last_end,last_country = s,e,co
end
end
end
print last entry
if last_start
wfile << [last_start,last_end,last_country].pack("NNa2")
end
end
The three variables declared up front are for tracking the ranges.
These will
be used to collapse consecutive ranges.
The next bit of code creates the binary database we will write into and
parses
the CSV formated data. Though the data is in the CSV format, the actual
content
is trivial and you don’t need a proper parser to get at it. As you can
see,
Matthias just checks for lines starting with a quote, pulls out all
quote
characters, and split()s on commas. This is faster than using a parser.
The if/else chain in the middle of the code does most of the work.
First, it
stores the initial range in the tracking variables. For all other
ranges it
tests to see if it is consecutive with the last one recorded and has the
same
country code. When it does, the endpoint of the last range is just
bumped to
include them both. When it doesn’t, the last range is written to the
file and
the code starts tracking the new range. The final if statement ensures
that we
write out the final range before exiting.
This really isn’t too much work and it runs in under two seconds on my
box.
That’s a small price to pay for a speed gain every time we look up an
address.
Let’s dive into the search code now. Here’s how it begins:
#!/usr/bin/ruby
take command line or stdin – the latter has performance advantage
for long lists
if ARGV[0]
arr=ARGV
else
arr=$stdin
end
…
As the comment tells us, Matthias added another way to feed the program
addresses. Where I said we should take one from the command-line
arguments,
this code actually handles any number of addresses from command-line
arguments
or STDIN.
This next bit of code opens up our database:
…
the binary table file is looked up with each request
File.open(“packed-ip.dat”,“rb”) do |rfile|
rfile.seek(0,IO::SEEK_END)
record_max=rfile.pos/10-1
# ...
The seek() and pos() calls here are used to find the end of the file.
You need
to know both ends of a data set to perform a binary search. Note that
dividing
by ten gives us the count of records since they are a fixed width and
Matthias
subtracts one because we will never need to seek() to the end of the
last record
again.
Now there’s a touch more preparation for each address we want to find:
# ...
arr.each { |argv|
# build a 4-char string representation of IP address
# in network byte order so it can be a string compare below
ipstr= argv.split(".").map {|x| x.to_i.chr}.join
# ...
In order to avoid a bunch of to_i() calls on each range extracted from
the
database, Matthias just encodes the address we are hunting for into the
character encoding used in the database. This way simple String
comparisons can
determine if the address it in the range.
We’re now ready for the actual search code:
# ...
# low/high water marks initialized
low,high=0,record_max
while true
mid=(low+high)/2 # binary search median
rfile.seek(10*mid) # one record is 10 byte, seek to position
str=rfile.read(8) # for range matching, we need only 8
bytes
# at comparison, values are big endian, i.e. packed(“N”)
if ipstr>=str[0,4] # is this IP not below the current range?
if ipstr<=str[4,4] # is this IP not above the current range?
puts rfile.read(2) # a perfect match, voila!
break
else
low=mid+1 # binary search: raise lower limit
end
else
high=mid-1 # binary search: reduce upper limit
end
if low>high # no entries left? nothing found
puts “no country”
break
end
end
}
end
This is a pretty textbook binary search. You always begin by going to
the
middle of the current low and high. In this case that’s a seek() call
and we
have to remember to multiply the midpoint by our record size of ten.
Once we are at the right record, the code read()s the first eight bytes
and
compares the address against the low and high for the range. When it is
in the
range, the final two bytes are read and printed. If the address is
below the
current range, we drop the high to below the current range. If it’s
above, we
raise the low to above the current range. A final check is added to
catch the
cases where no match was found, in which case our low will bypass the
high.
Remember that a second goal of the quiz described search was to be
memory
friendly. This code does terrific on that front since only one record
needs to
be in memory at a time. Once the checks are done, it can be replaced by
the
next record.
My thanks to all who showed so many great examples of this classic
algorithm.
Tomorrow we will write programs that can help me to better understand my
wardrobe…