I saw someone posted a code snippet about Pascal’s triangle, so I tried.
def my_pascals_triangle(n): d = [0, 1, 0] yield filter(None, d) for i in range(3, n + 2): # i == len(d) d = [d[j - 1] + d[j % i] for j in range(i + 1)] yield filter(None, d)
The performance is better in Python 2.5/2.6. The code in that post took 0.62 seconds for n=1000, mine took 0.43 including converting to list. I made another version from his code, so it could also using generator way:
def pascals_triangle_1(n): x = [1] yield x for i in range(n-1): x = [sum(i) for i in zip([0]+x,x+[0])] yield x
The performance is same, around 0.62 seconds including converting to list.
However, if I use Python 3.1, mine got pretty bad performance, 1+ seconds. His even gets better, 0.45 seconds.
I bet some Python list comprehensionist might be able to write it in one-liner without using additional defined function and with standard Python libraries if necessary. If you are the one, show off, please!
This is awesome enough to me!
ReplyDeleteI have thought about `_` variable when I tried to create a one-liner and I know I will need it, but I have no idea how to refer to in when doing in list comprehension. Thanks for the tip!
I am far from comprehensionist, but I couldn't resist:
ReplyDeletefilter(None, [[1 if c == 0 else int(globals()['_[2]'][-1] * ((r - c) / float(c))) for c in xrange(r)] for r in xrange(n + 1)])
Using two tricks:
- The Python interpreter uses an internal variable, which is only available while creating the list. This variable is a reference to the list: locals()['_[1]'] (as stated here (and I'm sure elsewhere))
- calculating individual rows/columns of Pascal's triangle using this formula.
I'm sure someone better skilled can improve my one line. I had fun doing it :)