In [67]:
## define the function p() that outputs debugging messages if DEBUG flag is True.
#DEBUG = True
DEBUG = False
def p(msg):
if DEBUG:
print(".. {}".format(msg))
In [1]:
from pprint import pprint
from bisect import *
## You may find many similarity between this class and the file operation (in C/Java).
class InvertedList:
def __init__(self, l):
self.data = l[:] # make a copy
self.cur = 0 # the cursor
def get_list(self):
return self.data
def eol(self):
# we use cur == len(list) to indicate EOL
return False if self.cur < len(self.data) else True
def next(self, val = 1):
# does not allow cur to be out-of-range, but use len(list) to indicate EOL
self.cur = min(self.cur + val, len(self.data))
def elem(self):
if self.eol():
return None
else:
return self.data[self.cur]
def peek(self, pos):
# look at the element under the current cursor, but does not advance the cursor.
if pos < len(self.data):
return self.data[pos]
else:
return None
def reset(self):
self.cur = 0
def dump(self):
print("* {} : {} (cur = {})".format(self.data[:self.cur], self.data[self.cur:], self.cur))
def skip_to(self, val):
##!! This is a naive and inefficient implementation.
##!! Once you have implemented gallop_to(), you can just call it here instead.
# move the cursor to the first element no smaller than `val`
while not self.eol() and self.elem() < val:
self.next()
def gallop_to(self, val):
##!! Not implemented yet.
pass
In [69]:
a = InvertedList([2, 4, 6, 8, 10, 12, 14, 16, 18])
b = InvertedList([1, 2, 4, 8, 16, 32])
while not a.eol():
e = a.elem()
a.next()
print(e)
a.dump()
If you have implemented the gallop_to() correctly, you should pass the following test. You may change the call to skip_to() for now to see how it should work.
In [70]:
def test_gallop(l, val):
print("=> gallop_to({})".format(val))
l.reset()
l.gallop_to(val)
l.dump()
In [71]:
test_a = [val - 1 for val in a.get_list()]
test_a.append(a.get_list()[-1] + 100)
DEBUG = False # to show the overview
a.dump()
for t_a in test_a:
test_gallop(a, t_a)
In [72]:
DEBUG = True # to show the details. Your detailed debugging info may vary.
test_gallop(a, test_a[-2])
As you can see above, the galloping search algorithm quickly skip over the list to reposition the cursor. In the additional note, it is proved that its complexity is $O(\log x)$, where $x$ is the difference between the correct cursor position and the initial cursor position.
In [73]:
def intersection_naive(a, b):
# just in case these lists have been traversed.
a.reset()
b.reset()
ret = []
while not a.eol() and not b.eol():
if a.elem() < b.elem():
p("move a")
a.next()
elif a.elem() > b.elem():
p("move b")
b.next()
else:
p("found one")
ret.append(a.elem())
a.next()
b.next()
return ret
Test
In [74]:
intersection_naive(a, b)
Out[74]:
In [75]:
def intersection_galloping(a, b):
# just in case these lists have been traversed.
a.reset()
b.reset()
ret = []
while not a.eol() and not b.eol():
if a.elem() == b.elem():
p("found one")
ret.append(a.elem())
a.next()
else:
if a.elem() < b.elem():
a.gallop_to(b.elem())
else:
b.gallop_to(a.elem())
# end_while
return ret
In [76]:
intersection_galloping(a, b)
Out[76]:
You need to correctly implement gallop_to using the galloping search algorithm, and then play with the intersection algorithm to appreciate how efficient it works in action. Note that the implementation is not hard, but you do need to take care of a few corner cases. That's why the test_gallop() evaluates almost all possible situation.
In [ ]:
In [ ]:
In [ ]:
In [ ]: