Skip to content

Instantly share code, notes, and snippets.

@CTimmerman
Created September 13, 2017 12:06
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save CTimmerman/34b7b9d7b161442a5c5da7b4afbba163 to your computer and use it in GitHub Desktop.
Save CTimmerman/34b7b9d7b161442a5c5da7b4afbba163 to your computer and use it in GitHub Desktop.
Proving that simple for loops are faster for both man and machine.
""" SICP section 2.2.3, page 160.
We can rearrange the pieces and use them in computing the product of the squares of the odd integers in a sequence:
(define (product-of-squares-of-odd-elements sequence) (accumulate * 1 (map square (filter odd? sequence))))
(product-of-squares-of-odd-elements (list 1 2 3 4 5))
225
2017-09-13 v1.0 Translated & benchmarked by Cees Timmerman
"""
from __future__ import print_function # For Python 2.
def product_of_squares_of_odd_elements(sequence):
r = 1
for e in sequence: r *= e * e if e % 2 else 1
return r
def product_of_squares_of_odd_elements_r(sequence):
from functools import reduce # For Python 3; https://stackoverflow.com/a/13638960/819417
def lamb(x, y): return x * y * y if y % 2 else x
return reduce(lamb, sequence, 1)
def product_of_squares_of_odd_elements_rf(sequence):
from functools import reduce
def lamb(x, y): return x * (y * y) # 25% faster than **2; https://stackoverflow.com/questions/1019740/speed-of-calculating-powers-in-python
return reduce(lamb, filter(lambda x: x % 2, sequence), 1)
def product_of_squares_of_odd_elements_rfm(sequence):
from functools import reduce
return reduce(lambda x, y: x * y, map(lambda x: x * x, filter(lambda x: x % 2, sequence)), 1)
def benchmark():
from timeit import timeit
times = int(1e5)
s = (3, 2, 3, 4, 5)
for f in ('', '_r', '_rf', '_rfm'):
fun = 'product_of_squares_of_odd_elements' + f
code = fun + '({})'.format(s)
print(f, eval(code))
print(timeit(code, number=times, setup='from __main__ import %s' % fun))
"""
1e5 times on rather busy 1,6 GHz Intel Core i5:
Python 2.7.13 [GCC 4.2.1 Compatible Apple LLVM 8.1.0 (clang-802.0.38)] on darwin:
0.25 for
0.40 reduce
0.45 reduce + filter
0.60 reduce + filter + map
Python 3.6.1 [GCC 4.2.1 Compatible Apple LLVM 8.1.0 (clang-802.0.38)] on darwin:
0.10 for
0.30 reduce
0.40 reduce + filter
0.50 reduce + filter + map
"""
if __name__ == '__main__':
benchmark()
@CTimmerman
Copy link
Author

And here's another list-related solution that's best in Python: https://rosettacode.org/wiki/Amb#List_Comprehension

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment