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 0 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()
@glathoud
Copy link

glathoud commented Jul 6, 2018

@CTimmerman You might like this: http://glat.info/transfun/
(sorry, only JavaScript at the moment, no Python - but still the idea could be interesting for you).

@CTimmerman
Copy link
Author

CTimmerman commented Jul 19, 2018

@glathoud Nice to see that someone automated for-loop creation in JS. I suppose that chaining confusing methods removes confusing variable names. Apparently even the compiler isn't sure that optimization always works, or people never got around to implementing it.

@CTimmerman
Copy link
Author

@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