I translated my function in Lisp to Python.
def get_the_longest_prefix(a, b, ans):
if len(a) == 0 or len(b) == 0:
return "".join(ans)
if a[0] == b[0]:
return get_the_longest_prefix(a[1:], b[1:], ans + [a[0]])
if a[0] == '-':
return get_the_longest_prefix(a[1:], b, ans + ['-'])
if b[0] == '-':
return get_the_longest_prefix(a, b[1:], ans + ['-'])
return "".join(ans)
And it has too many "return" statements. Anyway, I suppose Python doesn’t prefer a recursion. So this isn’t the case when we code in the Python way.
The code above concatenate Python's lists instead of creating a linked list like in Lisp.
So I made this experiment.
import time
n = 100
# Concatinating vectors
v = []
t1 = time.time_ns()
for i in range(n):
v = [i] + v
t2 = time.time_ns()
# Creating cons cells for a singly link list
l = None
t3 = time.time_ns()
for i in range(n):
l = (i, l) # Creating a cons cell
t4 = time.time_ns()
print((t2-t1)/(t4-t3))
At n = 100, concatenating vectors require 2 times of running time compared to creating cons cells for a linked list. So I keep using linked lists.
Top comments (0)