多次迭代的性能

想知道做一次迭代对多次迭代的性能影响。我使用Python工作 - 我不确定这是否会影响答案。多次迭代的性能

考虑尝试对列表中的每个项目执行一系列数据转换。

def one_pass(my_list): 
    for i in xrange(0, len(my_list)): 
     my_list[i] = first_transformation(my_list[i]) 
     my_list[i] = second_transformation(my_list[i]) 
     my_list[i] = third_transformation(my_list[i]) 
    return my_list 

def multi_pass(my_list): 
    range_end = len(my_list) 
    for i in xrange(0, range_end): 
     my_list[i] = first_transformation(my_list[i]) 

    for i in xrange(0, range_end): 
     my_list[i] = second_transformation(my_list[i]) 

    for i in xrange(0, range_end): 
     my_list[i] = third_transformation(my_list[i]) 

    return my_list

现在，除了可读性方面的问题，严格来说，在性能方面，对multi_pass来说one_pass是否有真正的优势？假设大多数工作发生在转换函数本身中，那么multi_pass中的每次迭代只需要大约1/3的时间呢？

来源

2012-11-15 Clay Wardell

如果大部分工作都发生在转换函数中，那么您已经回答了您自己的问题 - 单通方法没有效率优势。顺便说一句，如果有疑问，衡量！ – user4815162342

顺便说一句，它可能应该是'xrange（len（my_list））'，而不是减一。 'xrange'默认会产生关闭间隔。 – user4815162342

@ user4815162342 - 你对xrange（）是正确的。进行了更正。 –

不同之处在于您读取的值和代码在CPU's cache中的频率。

如果my_list的元素很大，但适合CPU缓存，则第一个版本可能会有所帮助。另一方面，如果转换的（字节）代码很大，那么缓存操作可能比高速缓存数据更好。

两个版本可能比慢的方式更具可读性：

def simple(my_list): 
    return [third_transformation(second_transformation(first_transformation(e))) 
      for e in my_list]

Timing it产量：

one_pass: 0.839533090591 
multi_pass: 0.840938806534 
simple: 0.569097995758

来源

2012-11-15 22:11:41 phihag

与其他版本相比，您可能会减少任一版本中的缓存未命中次数。这取决于这些转换函数实际执行的操作。

如果这些函数有很多代码，并且对不同的数据集（除了输入和输出之外）进行操作，多路径可能会更好。否则，单遍可能会更好，因为当前列表元素可能会保持缓存，并且循环操作只会执行一次而不是三次。

这是一个比较实际运行时间的情况，会非常有用。

来源

2012-11-15 22:05:31

就个人而言，我毫无疑问更喜欢one_pass选项。它绝对表现更好。你可能是对的，差异不会很大。 Python已经很好地优化了xrange迭代器，但是你仍然要做比所需要的多3倍的迭代。

来源

2012-11-15 22:06:37 ajon

假设你正在考虑一个程序，它可以很容易地一个循环使用多个操作，或多个循环每个执行一个操作，那么它不会改变计算复杂度（例如，O（n）算法仍然是O（n））。

单通道方法的一个优点是您可以节省循环的“簿记”。无论迭代机制是递增还是比较计数器，还是检索“下一个”指针并检查是否为空，或者无论如何，当你一次完成所有事情时，你做得更少。假设你的操作完成了大量的工作（并且你的循环机制简单明了，不需要循环昂贵的发生器或其他东西），那么这个“簿记”工作就会被你的实际工作拖垮操作，这绝对是一个微型优化，除非你知道你的程序太慢，并且你已经耗尽了所有更重要的可用优化，否则你不应该这样做。

另一个优点是，在进入下一个元素之前，将所有操作应用于迭代的每个元素都会从CPU缓存中获得更好的收益，因为每个项目仍可能在后续操作中位于缓存中同样的项目，而使用多个传递几乎不可能（除非你的整个集合适合缓存）。通过字典，Python具有如此多的间接性，尽管对于每个单独的操作来说，通过读取散布在整个内存空间上的散列桶来溢出缓存可能并不困难。所以这仍然是一个微观优化，但是这个分析给了它更多的机会（尽管仍然没有确定性）做出重大改变。

多遍的一个优点可能是如果您需要在循环迭代之间保持状态，单遍方法会强制您保持所有操作的状态。这可能会伤害CPU缓存（可能每个操作的状态分别适合整个传递的缓存，但不是所有操作的状态放在一起）。在极端情况下，这种影响在理论上可以使程序在内存中的拟合与否（我曾经在咀嚼大量数据的程序中遇到过这种情况）之间的差异。但是在极端的情况下，你需要将知道分解，而非极端情况又是微不足道的优化，事先并不值得。因此，表现通常倾向于单次传球的数量微不足道，但在某些情况下可以有利于单次传球或多次传球。您可以从中得出的结论与适用于所有编程的一般建议相同：首先以最清晰和可维护的方式编写代码，并且仍然充分地解决您的程序问题。只有当你有一个大部分完成的程序，并且如果原来是“不够快”，那么测量代码的各个部分的性能影响，以找出它值得花费你的时间。

出于性能原因而担心是否编写单通道或多通道算法的时间几乎总是被浪费掉了。因此，除非您有无限制的开发时间，否则您可以通过不担心此前期操作并根据需要进行处理，从您的总体开发工作（最好包括性能）中获得“最佳”结果。

来源

2012-11-15 23:30:51 Ben

多次迭代的性能

回答

相关问题