Using a Difference table to find the next element in a sequence

Question

Recently I implemented a python code that predicts the next number of a sequence using a difference table (a little more on the subject here)

def s(d,p=0):
 if (len(d) > 1):
 return s([i[0]-i[1] for i in zip(d[1:], d[:-1])],p+d[-1])
 return p+d[-1]
print(s(list(map(int, input().split(",")))))

This code takes the input(by stdin), the sequence separated by comas, like: 1,2,3 and outputs what it thinks is the next digit 4

Is there any way to make this code better or simplify it even more by python means? Any comments, answers, or opinions would be greatly appreciated

Answer 1

The other answer already mentioned to use descriptive names. It's the most important point to make it easier to understand the code.

It's recommended to add more spaces around operators. Tools like PyCharm would format the posted code like this:

def s(d, p=0):
 if (len(d) > 1):
 return s([i[0] - i[1] for i in zip(d[1:], d[:-1])], p + d[-1])
 return p + d[-1]

The parentheses in the if condition are unnecessary, drop them.

Instead of checking if the sequence has a single element, you can make that condition based on if the sequence is empty, which would make the code a bit simpler:

def s(d, p=0):
 if d:
 return s([i[0] - i[1] for i in zip(d[1:], d[:-1])], p + d[-1])
 return p

Be careful with recursive logic, if there are too many items in the input sequence, the call stack may become too deep and overflow. Consider writing in iterative style, especially when it's possible with little effort, and without sacrificing readability.

Here's an alternative using iterative style (with the nice renames from the other answer):

def predict(seq, prev=0):
 while seq:
 prev += seq[-1]
 seq = [b - a for a, b in zip(seq[:-1], seq[1:])]
 return prev

As @AJNeufeld pointed out in a comment, this can still be significantly better.

The prev argument is not really meant to be used by callers, it was necessary in the recursive version to track the cumulative sum of differences, but in the iterative version it can be a local variable.

It's also important to note that while zip(seq[:-1], seq[1:]) is elegantly written, it incurs the cost of list slicing (array copies). From Python 3.10, a more efficient and even more elegant solution is to use itertools.pairwise.

Putting these tips together:

def predict(seq):
 prev = 0
 while seq:
 prev += seq[-1]
 seq = [b - a for a, b in itertools.pairwise(seq)]
 return prev

• Peilonrayz: "From Python 3.10, a more efficient and even more elegant solution is to use itertools.pairwise." Might be worth changing the word "efficient" to say "memory efficient". When people read the word "efficient" are likely to think of speed. And speed is likely to be unchanged, perhaps slightly worse.

Answer 2

In terms of style, it'd be very helpful to give meaningful names. Right now it's basically impossible to get an idea of what your code is doing at first look. I'm not sure about any particular terminology here, but I think that predict for s, seq for d, and prev for p would make it more clear.

It'd also probably be better to unpack the tuple (as well as making the first term first) rather than indexing both items of i.

I'd also prefer the breakout condition to be first in a recursive function of this form.

Here's my version with these changes.

def predict(seq, prev=0):
 if len(seq) == 1:
 return prev + seq[-1] # Predict next in sequence as last value + difference
 return predict([b - a for a, b in zip(seq[:-1], seq[1:])], prev + seq[-1]) # Find prediction for next difference

This is already pretty simple, so I don't think there's much to do to make it simpler, but one basic optimization (although speed probably isn't an issue) is to check for the number of unique elements rather than the number of total elements, since if all the elements are the same, the differences will all be 0 and have no effect. This can be done simply by casting to a set.

if len(set(seq)) == 1:
 return prev + seq[-1]