4

想知道进行一次迭代与多次迭代对性能的影响。我在 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

现在，除了可读性问题，严格在性能方面，one_pass 是否比 multi_pass 有真正的优势？假设大部分工作都发生在转换函数本身中，那么 multi_pass 中的每次迭代不会只花费大约 1/3 的时间吗？

4

4 回答 4

5

不同之处在于您读取的值和代码在CPU 缓存中的频率。

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

两个版本都可能比可读性更慢：

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

计时它会产生：

one_pass: 0.839533090591
multi_pass: 0.840938806534
simple: 0.569097995758
于 2012-11-15T22:11:41.673 回答
2

假设您正在考虑一个程序，它可以很容易地成为一个具有多个操作的循环，或者多个循环每个执行一个操作，那么它永远不会改变计算复杂度（例如，O(n) 算法仍然是 O(n) 两种方式）。

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

另一个优点是，在进行下一个迭代之前将所有操作应用于迭代的每个元素往往会更好地从 CPU 缓存中受益，因为在对同一项目的后续操作中，每个项目仍然可以在缓存中，而使用多次传递几乎不可能（除非您的整个集合适合缓存）。Python 通过字典进行了如此多的间接操作，尽管每个单独的操作通过读取散布在内存空间中的哈希桶来溢出缓存可能并不难。所以这仍然是一个微观优化，但这种分析给了它更多的机会（尽管仍然不确定）产生显着的差异。

多通道的一个优点是，如果您需要在循环迭代之间保持状态，单通道方法会迫使您保持所有操作的状态。这可能会损害 CPU 缓存（可能每个操作的状态单独适合整个传递的缓存，但不是所有操作的状态放在一起）。在极端情况下，这种影响理论上可能会在程序适合内存和不适合内存之间产生差异（我曾经在一个正在咀嚼大量数据的程序中遇到过这种情况）。但是在极端情况下你知道你需要把事情分开，非极端情况又是不值得提前做的微优化。

因此，性能通常在微不足道的程度上偏爱单通道，但在某些情况下可能会非常偏爱单通道或多通道。您可以从中得出的结论与适用于所有编程的一般建议相同：首先以最清晰和可维护且仍能充分解决您的程序的任何方式编写代码。仅当您的程序基本完成并且结果“不够快”时，才可以测量代码各个部分的性能影响，以找出值得花时间的地方。

出于性能原因而担心是编写单遍还是多遍算法所花费的时间几乎总是被浪费掉了。因此，除非您有无限的开发时间可供您使用，否则您将从您的全部开发工作（其中最好包括性能）中获得“最佳”结果，无需预先担心这一点，并根据需要解决它。

于 2012-11-15T23:30:51.687 回答
1

与另一个版本相比，您可能会在任一版本中减少缓存未命中。这取决于这些转换函数实际上做了什么。

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

在这种情况下，比较实际运行时间将非常有用。

于 2012-11-15T22:05:31.137 回答
1

就个人而言，我无疑更喜欢 one_pass 选项。它肯定表现更好。您可能是对的，差异不会很大。Python 已经很好地优化了 xrange 迭代器，但是您仍然需要进行 3 倍于所需的迭代。

于 2012-11-15T22:06:37.923 回答