On 7/13/2015 3:07 PM, Marko Rauhamaa wrote:
Or, translated into (non-idiomatic) Python code:
========================================================================
def common_prefix_length(bytes_a, bytes_b):
def loop(list_a, list_b, common_length):
if not list_a:
return common_length
if not list_b:
return common_length
if list_a[0] == list_b[0]:
return loop(list_a[1:], list_b[1:], common_length + 8)
return common_length + \
bit_match[8 - integer_length(list_a[0] ^ list_b[0])]
return loop(bytes_a, bytes_b, 0)
========================================================================
This is an interesting challenge for conversion. The straightforward
while loop conversion is (untested, obviously, without the auxiliary
functions):
def common_prefix_length(bytes_a, bytes_b):
length = 0
while bytes_a and bytes_b and bytes_a[0] == bytes_b[0]:
length += 8
bytes_a, bytes_b = bytes_a[1:], bytes_b[1:]
if not bytes_a or not bytes_b:
return length
else:
return common_length + bit_match[
8 - integer_length(bytes_a[0] ^ bytes_b[0])]
Using a for loop and zip to do the parallel iteration for us and avoid
the list slicing, which is O(n) versus the O(1) lisp (cdr bytes), I
believe the following is equivalent.
def common_prefix_length(bytes_a, bytes_b):
length = 0
for a, b in zip(bytes_a, bytes_b):
if a == b:
length += 8
else:
return length + bit_match[8 - integer_length(a ^ b)]
else:
# short bytes is prefix of longer bytes
return length
I think this is much clearer than either recursion or while loop. It is
also more general, as the only requirement on bytes_a and bytes_b is
that they be iterables of bytes with a finite common_prefix, and not
necessarily sequences with slicing or even indexing.
--
Terry Jan Reedy
--
https://mail.python.org/mailman/listinfo/python-list
