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

Question

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

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

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

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

Answer 1

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

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