gpt4 book ai didi

c++ - 对具有许多缓存未命中的 1000-2000 个元素进行排序

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:16:48 27 4
gpt4 key购买 nike

我有一个包含 1000-2000 个元素的数组,这些元素是指向对象的指针。我想让我的数组保持排序,显然我想尽快完成。它们按成员排序而不是连续分配,因此每当我访问按成员排序时都假设缓存未命中。

目前我按需排序而不是添加排序,但是由于缓存未命中和[可能]成员访问的非内联,我的快速排序的内部循环很慢。

我现在正在做测试和尝试,(看看实际的瓶颈是什么)但是有人能推荐一个好的替代方法来加快速度吗?我应该进行插入排序而不是按需快速排序,还是应该尝试更改我的模型以使元素连续并减少缓存未命中?或者,是否有一种我没有遇到过的排序算法,它适用于将要缓存未命中的数据?

编辑:也许我的措辞有误 :),我实际上并不需要一直对我的数组进行排序(我没有按顺序遍历它们)我只需要在进行二元运算时对它进行排序找到一个匹配的对象,并在那个时候(当我想搜索时)进行快速排序是我目前的瓶颈,因为缓存未命中和跳转(我在我的对象上使用 < 运算符,但我希望在发布中内联)

最佳答案

简单方法:对每个插入进行插入排序。由于您的元素在内存中未对齐,我猜是链表。如果是这样,那么您可以将其转换为链表,并跳转到第 10 个元素、第 100 个元素,依此类推。这有点类似于下一个建议。

或者您将容器结构重组为二叉树(或者您喜欢的每棵树,B、B*、红-黑……)并插入元素,就像将它们插入搜索树中一样。

关于c++ - 对具有许多缓存未命中的 1000-2000 个元素进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2952407/

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