Author: Armin Rigo <ar...@tunes.org>
Branch:
Changeset: r78715:4012e89fb82d
Date: 2015-07-29 23:28 +0200
http://bitbucket.org/pypy/pypy/changeset/4012e89fb82d/
Log: Issue #2100: massively improve the performance of map() with more
than one sequence argument
diff --git a/pypy/module/__builtin__/app_functional.py
b/pypy/module/__builtin__/app_functional.py
--- a/pypy/module/__builtin__/app_functional.py
+++ b/pypy/module/__builtin__/app_functional.py
@@ -53,6 +53,33 @@
last = last + x
return last
+
+class _Cons(object):
+ def __init__(self, prev, iter):
+ self.prev = prev
+ self.iter = iter
+
+ def fetch(self):
+ # recursive, loop-less version of the algorithm: works best for a
+ # fixed number of "collections" in the call to map(func, *collections)
+ prev = self.prev
+ if prev is None:
+ args1 = ()
+ stop = True
+ else:
+ args1, stop = prev.fetch()
+ iter = self.iter
+ if iter is None:
+ val = None
+ else:
+ try:
+ val = next(iter)
+ stop = False
+ except StopIteration:
+ self.iter = None
+ val = None
+ return args1 + (val,), stop
+
def map(func, *collections):
"""map(function, sequence[, sequence, ...]) -> list
@@ -69,45 +96,30 @@
if num_collections == 1:
if none_func:
return list(collections[0])
- # Special case for the really common case of a single collection,
- # this can be eliminated if we could unroll that loop that creates
- # `args` based on whether or not len(collections) was constant
+ # Special case for the really common case of a single collection
seq = collections[0]
with _ManagedNewlistHint(operator._length_hint(seq, 0)) as result:
for item in seq:
result.append(func(item))
return result
- # Gather the iterators (pair of (iter, has_finished)) and guess the
+ # Gather the iterators into _Cons objects and guess the
# result length (the max of the input lengths)
- iterators = []
+ c = None
max_hint = 0
for seq in collections:
- iterators.append((iter(seq), False))
+ c = _Cons(c, iter(seq))
max_hint = max(max_hint, operator._length_hint(seq, 0))
with _ManagedNewlistHint(max_hint) as result:
while True:
- cont = False
- args = []
- for idx, (iterator, has_finished) in enumerate(iterators):
- val = None
- if not has_finished:
- try:
- val = next(iterator)
- except StopIteration:
- iterators[idx] = (None, True)
- else:
- cont = True
- args.append(val)
- args = tuple(args)
- if cont:
- if none_func:
- result.append(args)
- else:
- result.append(func(*args))
+ args, stop = c.fetch()
+ if stop:
+ return result
+ if none_func:
+ result.append(args)
else:
- return result
+ result.append(func(*args))
class _ManagedNewlistHint(object):
""" Context manager returning a newlist_hint upon entry.
diff --git a/pypy/module/__builtin__/test/test_functional.py
b/pypy/module/__builtin__/test/test_functional.py
--- a/pypy/module/__builtin__/test/test_functional.py
+++ b/pypy/module/__builtin__/test/test_functional.py
@@ -57,6 +57,11 @@
b = []
assert map(lambda x, y: x, a, b) == a
+ def test_map_second_item(self):
+ a = []
+ b = [1, 2, 3, 4, 5]
+ assert map(lambda x, y: y, a, b) == b
+
def test_map_iterables(self):
class A(object):
def __init__(self, n):
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
