与通过循环调用函数相比，地图或列表理解实现的性能提升从何而来? [英] Where does the performance boost of map or list comprehension implementations over calling a function over a loop come from?

问题描述

我知道在 map 的实现中使用内存可能比在循环中执行它的方式更有效.但是，我发现使用 map 函数而不是调用在循环上迭代的函数也可以提高速度.

I understand that you could be more efficient with memory in the implementation of map than in how you might do it over a loop. However, I see that using a map function over calling a function iterating over a loop has a speed boost as well.

这是否来自于存储内存的一些优化?我的意思的一个例子是以连续的方式放置内存.我也可以看到，如果操作并行运行，那么速度也会提高，但我认为情况并非如此.非常欢迎来自任何语言/包的地图实现的任何已知优化示例！

Is this coming from some optimization in where to store the memory? One example of what I mean by this is placement of memory done in such a way that it is contiguous. Also I can see that if the operations were being in run in parallel then there would also be a speed boost, but I don't think this is the case. Examples from any known optimizations for map implementations from any language/package are very welcome!

-- 我觉得我之前的例子好像没有很好地说明我的问题.

-- I feel as if the example I had previously did not illustrate my question very well.

可能不是完全公平的比较.例如，我测试了循环实现、列表理解和映射函数.你有什么想法可以让一个比另一个更快吗?不一定是 Python；这更多是关于实现更有效的算法以将函数应用于可迭代对象的问题.一个有效的答案可能是通常对于每种地图/列表理解风格的代码，您都可以比这更快地实现循环".或者在某些情况下，列表理解更快，但这与实现细节有关，而这正是我感兴趣的.

MAY NOT BE COMPLETELY FAIR COMPARISON. For example, I test the a loop implementation, list comprehension, and the map function. Would you have any ideas of what would make one faster than the other? NOT NECESSARILY PYTHON; this is more a question about implementation of more efficient algorithms for applying a function over an iterable object. A valid answer might be that "typically for every map/list comprehension style of code, you would be able to make a loop implementation faster than that". Or for some case, the list comprehension is faster, but this relates to the implementation details and that is what I am interested in.

import time
import numpy as np


def square2(x):
return x*x


def main():
    foobar = np.linspace(1, 300, 300)

    start_time = time.time()
    res = [0] * len(foobar)
    for i, foo in enumerate(foobar):
        res[i] = square2(foo)
    print("{} {} runtime seconds {}".format("-"*8, time.time()-start_time, "-"*8))

    res = [0] * len(foobar)
    start_time = time.time()
    res = [square2(foo) for foo in foobar]
    print("{} {} runtime seconds {}".format("-"*8, time.time()-start_time, "-"*8))

    start_time = time.time()
    res = list(map(square2, foobar))
    print("{} {} runtime seconds {}".format("-"*8, time.time()-start_time, "-"*8))

输出为:

-------- 6.175041198730469e-05 runtime seconds --------
-------- 5.984306335449219e-05 runtime seconds --------
-------- 5.316734313964844e-05 runtime seconds --------

推荐答案

因此，在 Python 等动态语言中，循环中函数调用的问题在于解释器每次都必须评估引用，即成本高昂，尤其是对于全局变量.但是，请注意将内容本地化时会发生什么:

So, the issue with function-calls in loops, in a dynamic language like Python, is that the interpreter has to evalute the refernces each time, and that is costly, especially for global variables. However, notice what happens when you make things local:

import time
def square(x):
    return x*x

def test_loop(x):
    res = []
    for i in x:
        res.append(square(i))
    return res


def test_map(x):
    return  list(map(square,x))

def test_map_local(x, square=square):
    return  list(map(square,x))


def test_loop_local(x, square=square):
    res = []
    for i in x:
        res.append(square(i))
    return res

def test_loop_local_local(x, square=square):
    res = []
    append = res.append
    for i in x:
        append(square(i))
    return res

def test_comprehension(x):
    return [square(i) for i in x]

def test_comprehension_local(x, square=square):
    return [square(i) for i in x]

x = range(1,10000000)

start = time.time()
test_loop(x)
stop = time.time()
print("Loop:", stop - start,"seconds")

start = time.time()
test_loop_local(x)
stop = time.time()
print("Loop-local:", stop - start, "seconds")

start = time.time()
test_loop_local_local(x)
stop = time.time()
print("Loop-local-local:", stop - start, "seconds")

start = time.time()
test_map(x)
stop = time.time()
print("Map:", stop - start, "seconds")

start = time.time()
test_map_local(x)
stop = time.time()
print("Map-local:", stop - start, "seconds")

start = time.time()
test_comprehension(x)
stop = time.time()
print("Comprehesion:", stop - start, "seconds")

start = time.time()
test_comprehension_local(x)
stop = time.time()
print("Comprehesion-local:", stop - start, "seconds")

结果:

Loop: 3.9749317169189453 seconds
Loop-local: 3.686530828475952 seconds
Loop-local-local: 3.006138563156128 seconds
Map: 3.1068732738494873 seconds
Map-local: 3.1318843364715576 seconds
Comprehesion: 2.973804235458374 seconds
Comprehesion-local: 2.7370445728302 seconds

因此，在 map local 中进行函数查找并没有真正的帮助，正如我所期望的那样，因为 map 在开始时只进行了一次查找.真正让我感到惊讶的是，理解和具有本地化功能的理解之间似乎存在不可忽视的差异.不过，不确定这是否只是噪音.

So, making the function look-up in map local doesn't really help, as I would expect because map does a single look-up at the beginning. What really surprised me is that there seems to be a non-negligible difference between a comprehension and a comprehension with the function made local. Not sure if this is just noise, however.

这篇关于与通过循环调用函数相比，地图或列表理解实现的性能提升从何而来?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！