veer66

(Posted on 2022-03-22)

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.