Created
September 13, 2017 12:06
-
-
Save CTimmerman/34b7b9d7b161442a5c5da7b4afbba163 to your computer and use it in GitHub Desktop.
Proving that simple for loops are faster for both man and machine.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" 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() |
Here's an actual program in a Lisp: https://gist.github.com/CTimmerman/275278abeea166a74fd3cf759a239b7e
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
@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.