我有一个包含 1000-2000 个元素的数组，它们是指向对象的指针。我想让我的数组保持排序，显然我想尽快做到这一点。它们按成员排序，并且不是连续分配的，因此每当我访问排序成员时，都会假设缓存未命中。
目前，我是按需排序而不是添加排序，但由于缓存未命中和[大概]成员访问的非内联，我的快速排序的内部循环很慢。
我现在正在做测试并尝试一些事情（看看实际的瓶颈是什么），但是任何人都可以推荐一个好的替代方案来加快速度吗？
我应该进行插入排序而不是按需快速排序，还是应该尝试更改我的模型以使元素连续并减少缓存未命中？
或者，是否有一种我没有遇到过的排序算法对于将要缓存未命中的数据有好处？
编辑：也许我的措辞是错误的:)，我实际上并不需要一直对我的数组进行排序（我不会按顺序迭代它们以进行任何操作）我只需要在进行二进制切割时对其进行排序以查找匹配对象，并且当时（当我想要搜索时）执行快速排序目前是我的瓶颈，因为缓存未命中和跳转（我在我的对象上使用
简单的方法：对每个插入进行插入排序。由于您的元素在内存中未对齐，我猜测是链表。如果是这样，那么您可以将其转换为一个链接列表，并跳转到第 10 个元素、第 100 个元素，依此类推。这与下一个建议有点相似。
或者，您将容器结构重新组织为二叉树（或者您喜欢的每棵树，B、B*、红黑……）并插入元素，就像将它们插入搜索树一样。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
