gpt4 book ai didi

c++ - 提高从数组向链表插入元素的性能

转载 作者:太空狗 更新时间:2023-10-29 20:23:17 25 4
gpt4 key购买 nike

我想将一个数组的元素插入到链表中。以下是我正在使用的代码片段:

for (int i = 0; i<MAXSIZE; i++)
{
Node* n1 = new Node();
n1->SetData(randArray[i]);
n1->SetIndex(i);
n1->SetNext(NULL);

//checks if NULL
if (start == NULL) {
start = n1;
start->SetNext(NULL);
}
else {
//inserts the values to the end of the node
Node *p = start;
while (p->GetNext() != NULL) {
p = p->GetNext();
}
p->SetNext(n1);
}
}

这里 randArray[i] 由元素组成,比如 100000 个元素。

现在我希望这个过程执行得更快。目前50000个元素耗时13秒。

有人可以帮忙吗?

最佳答案

你现在每次插入一个新节点时都在寻找最后一个节点......但是你已经知道最后一个节点在哪里,因为你只是在最后一次迭代中插入它 - 如果你没有抛出那个信息远。只需将指向它的指针存储在一个变量中,该变量在迭代结束时不会被销毁。另一种方法——对于单链表来说更典型一些——是只在列表的前面插入。如果您希望元素的顺序与数组中的顺序相同,则以相反的顺序迭代数组。

摆脱对结束的线性搜索可将算法的运行时复杂度从 O(n^2) 降低到 O(n)。

另一个对性能影响较小但会使您的代码更简单的优化:使用仅在前面插入的方法并使用哨兵节点实现您的列表。这样你就不需要在每次迭代中都有一个分支。也就是说,由于很容易预测,该分支可能影响不大。您也可以使用记住最后一个节点的方法来摆脱分支,方法是将测试移到循环之外,但这不会简化您的代码。

编辑:毕竟不需要哨兵节点,即使它确实简化了一些其他列表算法。我很无聊,所以我实现了 insert-in-front-only 方法:

Node* head = nullptr;
for (size_t i = MAXSIZE; i --> 0;) {
Node* n = new Node();
n->SetData(randArray[i]);
n->SetIndex(i); // †
n->SetNext(head);
head = n;
}

† 如果您真的想将索引存储在节点中,您可能需要重新考虑。当稍后从尾部以外的任何其他地方插入或删除节点时更新它会非常慢。

关于c++ - 提高从数组向链表插入元素的性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33821710/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com