function giving different result with @functool.cache - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: Homework (https://python-forum.io/forum-9.html) +--- Thread: function giving different result with @functool.cache (/thread-31100.html) |
function giving different result with @functool.cache - naughtysensei - Nov-23-2020 I wrote this code to give first 'n' rows for pascal's triangle: def pascal_re(n): def nextrow(prerow): '''gives next row of pascal's triangle from previous row''' for i in range(len(prerow) - 1): prerow[i] += prerow[i+1] return [1] + prerow if n == 1: return [[1]] return pascal_re(n - 1) + [nextrow(pascal_re(n - 1)[-1])] print(pascal_re(5)) but the output was quite slow (say for n=25) compared to my iterative version for same:def pascal_it(n): listo = [] for i in range(n): lst = [1] for j in range(i-1): lst.append(listo[i-1][j] + listo[i-1][j+1]) if i: lst.append(1) listo.append(lst) return listoso I used @functools.cache: import timeit @functools.cache def pascal_re(n): def nextrow(prerow): '''gives next row of pascal's triangle from previous row''' for i in range(len(prerow) - 1): prerow[i] += prerow[i+1] return [1] + prerow if n == 1: return [[1]] return pascal_re(n - 1) + [nextrow(pascal_re(n - 1)[-1])] print(pascal_re(5)) the output is different from before, what is going on here, how can I make my recursive version faster and right?
RE: function giving different result with @functool.cache - deanhystad - Nov-23-2020 The problem is that nextrow() modifies prerow. The problem happens here. return pascal_re(n - 1) + [nextrow(pascal_re(n - 1)[-1])] # ^ a ^ bWithout the cache, a and b are different lists, so changing b[-1] does not affect a. With the cache, a and b are the same list, so changing b[-1] changes a[-1]. To fix the problem you need to make all your modifications in nextrow happen to a different list. @functools.cache def pascal_re(n): def nextrow(prerow): '''gives next row of pascal's triangle from previous row''' prerow = [1].append(prerow) # Makes a new list. Fixes shared list problem. for i in range(1, len(prerow) - 1): prerow[i] += prerow[i+1] return prerow if n == 1: return [[1]] return pascal_re(n - 1) + [nextrow(pascal_re(n - 1)[-1])] RE: function giving different result with @functool.cache - deanhystad - Nov-23-2020 You can also make recursion a lot faster by using less of it. def pascal_re(n): def nextrow(r): '''gives next row of pascal's triangle from previous row''' prerow = [1].append(prerow) # Makes a new list. Fixes shared list problem. for i in range(1, len(prerow) - 1): prerow[i] += prerow[i+1] return prerow if n == 1: return [[1]] tmp = pascal_re(n - 1) # Compute once and use twice return tmp + [nextrow(tmp[-1])] print(pascal_re(25)) RE: function giving different result with @functool.cache - naughtysensei - Nov-25-2020 (Nov-23-2020, 04:52 PM)deanhystad Wrote:you mean this:prerow = [1].append(prerow) # Makes a new list. Fixes shared list problem. for i in range(1, len(prerow) - 1): prerow[i] += prerow[i+1] return prerow one = [1] one.extend(prerow) prerow = one for i in range(1, len(prerow)-1): prerow[i] += prerow[i+1] return prerowor even better I guess: prerow = prerow.copy() for i in range(len(prerow)-1): prerow[i] += prerow[i+1] return [1] + prerowIt is now obvious where I fucked up. thx. "Make a new list" this helped. |