> The second optimization one could make is that since f(r, i) == f(r, i-1) + f(r, i) then to calculate f(r, i) you only need to calculate up to the i'th element of each row.
You actually only need to calculate up to the i'th element of the row you want.
The Wikipedia page about Pascal's triangle [1] teaches us that it's possible to calculate a row directly (without any knowledge of other rows).
Therefore we can do this:
#!/usr/bin/python
for row in xrange(200):
curr = [1]
vc = 1
for c in xrange(1, row/2+1):
vc = int(vc * (row+1-c)/float(c))
curr.append(vc)
curr.extend(curr[::-1])
print curr
(And of course since each line is symmetrical we only need to compute half of it).
This version is only a little faster than the last one provided by the author, but for some reason it's much more consistent, time-wise. For 200 rows it stays between 250-330ms between runs, whereas the author's last version is between 300-550ms.
And with a little modification, this version will let us compute any row much more efficiently than starting at the first row every time.
PS: There may be a more efficient way to calculate vc (Cell Value) than using int() and float(), but I don't really know Python so that's the best I can do ;-)
You actually only need to calculate up to the i'th element of the row you want.
The Wikipedia page about Pascal's triangle [1] teaches us that it's possible to calculate a row directly (without any knowledge of other rows).
Therefore we can do this:
(And of course since each line is symmetrical we only need to compute half of it).This version is only a little faster than the last one provided by the author, but for some reason it's much more consistent, time-wise. For 200 rows it stays between 250-330ms between runs, whereas the author's last version is between 300-550ms.
And with a little modification, this version will let us compute any row much more efficiently than starting at the first row every time.
[1]: http://en.wikipedia.org/wiki/Pascals_triangle
PS: There may be a more efficient way to calculate vc (Cell Value) than using int() and float(), but I don't really know Python so that's the best I can do ;-)