这两个程序的性能是否相同？

Question

例如你有一个链表 1->2->3->4->5->6->NULL 并且你想计算该链表的偶数索引的总数（假设第一个索引从1开始，链表的大小是偶数)

第一种方法

int total = 0;
int count = 0;
Node *ptr = head;
while(ptr != NULL)
{
    if(count % 2 == 0)
     {
       total += ptr->data;
     }
     count++;
     ptr = ptr->next;
}

第二种方法

int total = 0;
Node *ptr = head;
while(ptr != NULL)
{  
    total += ptr->data;
     ptr = ptr->next->next;
}

所以我做了这两种方法后，它们的性能是否相同？

Answer 1

我又看了一遍你的问题，我会回答可能第二种方法稍微快一些。

现在，评论部分立即强调它也更危险。您实际上已经指定假设列表中的节点数是偶数。如果这是一个有保证且可执行的先决条件，那么从技术上讲，这样做是可以的。

即使是一个聪明的优化编译器也无法知道这个偶数列表长度的先决条件，所以它可能实现的最好结果是认识到 count 仅用于控制是否 total 已更新，因此循环可以展开如下：

// Possible automatic compiler optimization of First Approach
while (ptr)
{
    total += ptr->data;
    ptr = ptr->next;

    // Skip over every second node
    if (ptr) ptr = ptr->next;
}

从根本上讲，我们现在拥有的是比您的第二种方法多一个每次循环迭代的指针测试（分支）。这会导致更多指令（特别是分支指令），因此代码在技术上会（稍微）慢一些。

当然，这个实际影响很可能很小。您的主要瓶颈是指针间接和从内存中获取，而不是指针测试本身。如果每个节点使用的内存大多不是连续的，您将运行陷入大型列表的缓存问题（实际上这会影响性能大约 100 倍）。

以上所有我的意思是，您基于偶数列表长度的前提条件进行特殊优化的好处正在减少 returns。

鉴于它本质上是不安全的，除非在代码中有很好的记录 and/or 受列表“均匀性”测试保护（如果您将节点计数存储在某处），我建议使用您的代码进行防御性编码第一种方法或使用我的等效和（可以说）更整洁的版本。

这两个程序的性能是否相同？

Are the Performances of these two programs the same?

c++

performance

linked-list

singly-linked-list

第一种方法

第二种方法