It may be better to ask a question, but I would like to add it as needed, and I feel like I will lose something if it is a question, so I will write it as an article (self-centered).
Originally using Scheme, for various reasons Description of higher-order functions often expressed in Scheme because Python is used as an alternative language. I'm looking for a way to replace Anyway, in Scheme, map + lambda etc. are used a lot, and it is possible to write as it is in Python, but there are still subtle differences, and list comprehension etc. is recommended from the viewpoint of readability and processing speed. Since it seems that there is, I would like to do something that can be expressed by comprehension.
In this article, I will expose the description expressed in the (?) Comprehension notation and use it as a memorandum and information exchange material. The Scheme processing system is Gauche, and the Python processing system is Python3. programming-online /) is assumed.
map → inclusion notation)Description example in Scheme:
(display (map + '(0 1 2 3 4) '(5 6 7 8 9)))
; => (5 7 9 11 13)
Description example using Python's map and lambda:
+ cannot be passed directly.from operator import add
print(tuple(map(add, (0,1,2,3,4), (5,6,7,8,9))))
# => (5, 7, 9, 11, 13)
Or
print(tuple(map((lambda x, y: x + y), (0,1,2,3,4), (5,6,7,8,9))))
# => (5, 7, 9, 11, 13)
Description example using Python comprehension:
print(tuple(x + y for x, y in zip((0,1,2,3,4), (5,6,7,8,9))))
# => (5, 7, 9, 11, 13)
The processing speed is ... Oh, is map + ʻadd` the fastest? I wonder if I made a mistake (bearish).
python
from time import time
from operator import add
R1 = range(9999999,-1,-1)
R2 = range(0,10000000)
start = time()
a = tuple(map(add, R1, R2))
print(" map + add: ", time() - start)
start = time()
b = tuple(map((lambda x,y: x + y), R1, R2))
print(" map + lambda: ", time() - start)
start = time()
c = tuple(x + y for x,y in zip(R1, R2))
print("comprehension + zip: ", time() - start)
# map + add: 2.8753578662872314
# map + lambda: 4.222743034362793
# comprehension + zip: 3.9112401008605957
fold / reduce)Description example in Scheme:
(display (fold * 1 '(1 2 3 4 5 6 7 8 9 10)))
; => 3628800
Description example using Python's reduce and lambda:
* cannot be passed directly, the following is omitted.from functools import reduce
from operator import mul
print(reduce(mul, (1,2,3,4,5,6,7,8,9,10)))
# => 3628800
Or
print(reduce(lambda x, y: x * y, (1,2,3,4,5,6,7,8,9,10)))
# => 3628800
Is there a description example using Python's comprehension? In the first place, the value to be sought is not a sequence type, so there is no set inclusion (it immediately deviates from the purpose of the article). It seems that sum is prepared as standard for addition. Is this something that you should create your own function if necessary (rather, a LISP-like idea)?
def product(l):
r = 1
for i in l: r *= i
return r
print(product((1,2,3,4,5,6,7,8,9,10)))
# => 3628800
And time measurement. It doesn't change much, but it seems that ʻoperator.mul` is about to be a child who doesn't need it.
from functools import reduce
from time import time
from operator import mul
def product(l):
r = 1
for i in l: r *= i
return r
R1 = range(1,100000)
start = time()
a = reduce(mul, R1)
print(" reduce + mul: ", time() - start)
start = time()
a = reduce(lambda x, y: x * y, R1)
print("reduce + lambda: ", time() - start)
start = time()
a = product(R1)
print(" product: ", time() - start)
# reduce + mul: 23.096322059631348
# reduce + lambda: 18.508586406707764
# product: 19.82227087020874
Here, conversely, consider expressing the following description expressed in Python list comprehension with a higher-order function.
python
tuple((x, y) for x in (1,2,3) for y in (7,8,9) if x + y < 11)
# => ((1, 7), (1, 8), (1, 9), (2, 7), (2, 8), (3, 7))
Regarding Scheme, there is a list comprehension notation list-ce in the extended proposal specification SRFI 42, and it can be written as follows.
(use srfi-42)
(display (list-ec (: x '(1 2 3)) (: y '(7 8 9)) (if (< (+ x y) 11)) (list x y)))
; => ((1 7) (1 8) (1 9) (2 7) (2 8) (3 7))
If you try to do this with just a lambda expression or map, it will be rather complicated.
(display
(filter (lambda (p) (< (+ (car p) (cadr p)) 11))
(fold append '()
(reverse
(map (lambda (x)
(map (lambda (y) (list x y))
'(7 8 9)))
'(1 2 3))))))
; => ((1 7) (1 8) (1 9) (2 7) (2 8) (3 7))
The main reason is that the selection by the conditional expression is performed by filter separately after generating the unconditional list once. In addition, nesting map also nests the returning list, so ʻappend needs to be flattened by fold ( reduce) (and ʻappend is added to the top of the list in sequence. Therefore, it is necessary to reverse the list elements with reverse before ʻappend). The latter is a little easier if you can use SRFI 1's ʻappend-map.
(display
(filter (lambda (p) (< (+ (car p) (cadr p)) 11))
(append-map (lambda (x)
(map (lambda (y) (list x y))
'(7 8 9)))
'(1 2 3))))
; => ((1 7) (1 8) (1 9) (2 7) (2 8) (3 7))
In that sense, if list comprehension notation cannot be used, map ＋ fold ( reduce) ＋ filter will be required as a set (ʻappendandreverse` are both list operations. When functional programming was introduced in languages where procedural programming was the main language, these may have been regarded as typical higher-order functions. And, in such a description, the set inclusion is easier to understand and is omitted below.
In Python3, reduce is one of the external libraries functools, but since the basic function sum also supports lists, you can write as follows even without reduce. Possible.
print(
tuple(filter(lambda p: p[0] + p[1] < 11,
sum(tuple(map(lambda x:
tuple(map(lambda y: (x, y),
(7,8,9))),
(1,2,3))),
()))))
# => ((1, 7), (1, 8), (1, 9), (2, 7), (2, 8), (3, 7))
When using reduce of functools, it is as follows.
from functools import reduce
print(
tuple(filter(lambda p: p[0] + p[1] < 11,
reduce(lambda x, y: x + y,
tuple(map(lambda x:
tuple(map(lambda y: (x, y),
(7,8,9))),
(1,2,3))),
()))))
# => ((1, 7), (1, 8), (1, 9), (2, 7), (2, 8), (3, 7))
Needless to compare the processing speed. The map is generating tuple many times on the way.
from time import time
from functools import reduce
N = 2000
R1 = range(1,N)
start = time()
a = tuple((x, y) for x in R1 for y in R1 if x + y < N)
print(" comprehension: ", time() - start)
start = time()
a = tuple(filter(lambda p: p[0] + p[1] < N,
sum(tuple(map(lambda x:
tuple(map(lambda y: (x, y),
R1)),
R1)),
())))
print(" map + sum + filter: ", time() - start)
start = time()
a = tuple(filter(lambda p: p[0] + p[1] < N,
reduce(lambda x, y: x + y,
tuple(map(lambda x:
tuple(map(lambda y: (x, y),
R1)),
R1)),
())))
print("map + reduce + filter: ", time() - start)
# comprehension: 0.5814449787139893
# map + sum + filter: 27.217236757278442
# map + reduce + filter: 28.032208919525146
From the conclusion, it seems that there is not much difference between list comprehension notation and filter + lambda descriptively. List comprehension is much better in the sense that it is faster because it is built-in and implemented.
from time import time
D = range(996, -1, -1)
start = time()
def qsort1(L):
if not L: return []
else:
LL = qsort1([x for x in L[1:] if x < L[0]])
LR = qsort1([x for x in L[1:] if x >= L[0]])
return LL + [L[0]] + LR
a = list(qsort1(D))
print(" comprehension: ", time() - start)
start = time()
def qsort2(L):
if not L: return []
else:
LL = qsort2(list(filter(lambda x: x < L[0], L[1:])))
LR = qsort2(list(filter(lambda x: x >= L[0], L[1:])))
return LL + [L[0]] + LR
a = list(qsort2(D))
print("filter + lambda: ", time() - start)
# comprehension: 0.1841585636138916
# filter + lambda: 0.3261446952819824
Recommended Posts