c++ - 对动态大小的对象进行排序

Question

问题

假设我有一个包含一些数据的大字节数组(最多 4GB)。这些字节以这样的方式对应于不同的对象，即每 s 个字节(认为 s 最多 32 个)将构成一个对象。一个重要的事实是，这个 size s 对于所有对象都是相同的，而不是存储在对象本身中，并且在编译时是未知的。

目前，这些对象只是逻辑实体，而不是编程语言中的对象。我对这些对象进行了比较，其中包括对大多数对象数据的字典序比较，以及使用剩余数据打破联系的一些不同功能。现在我想有效地对这些对象进行排序(这真的会成为应用程序的瓶颈)。

到目前为止的想法

我已经想到了几种可能的方法来实现这一点，但它们中的每一个似乎都有一些相当不幸的后果。您不必阅读所有这些内容。 我试图用粗体打印每种方法的中心问题。 如果您打算建议其中一种方法，那么您的答案也应该对相关问题做出回应。

1. C 快速排序

当然，C 快速排序算法也可用于 C++ 应用程序。它的签名几乎完全符合我的要求。但是，使用该函数将禁止内联比较函数的事实意味着每次比较都会带来函数调用开销。我曾希望有一种方法可以避免这种情况。 任何关于如何 C qsort_r 的经验在性能方面与 STL 相比将非常受欢迎。

2. 使用指向数据的对象间接

编写一堆包含指向其各自数据的指针的对象会很容易。然后可以对这些进行排序。这里有两个方面需要考虑。一方面，仅仅移动指针而不是所有数据就意味着更少的内存操作。另一方面，不移动对象可能会破坏内存局部性并因此缓存性能。更深层次的快速排序递归实际上可以从几个缓存页面访问所有数据的可能性几乎完全消失。相反，每个缓存的内存页面在被替换之前只会产生很少的可用数据项。 如果有人能提供一些关于复制和内存局部性之间权衡的经验，我会很高兴。

3. 自定义迭代器、引用和值对象

我写了一个类作为内存范围内的迭代器。取消引用这个迭代器产生的不是一个引用，而是一个新构造的对象来保存指向数据的指针和在构造迭代器时给出的大小 s。所以这些对象是可以比较的，我什至有一个 std::swap 的实现对于这些。不幸的是，似乎std::swap不够std::sort .在该过程的某些部分，我的 gcc 实现使用插入排序(如文件 __insertion_sort 中的文件 stl_alog.h 中实现)将值移出序列，将数字项移出一步，然后将第一个值移回进入适当位置的序列:

          typename iterator_traits<_RandomAccessIterator>::value_type
            __val = _GLIBCXX_MOVE(*__i);
          _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
          *__first = _GLIBCXX_MOVE(__val);

您是否知道不需要值类型但可以单独使用交换操作的标准排序实现？

所以我不仅需要我的类作为引用，而且我还需要一个类来保存临时值。由于我的对象的大小是动态的，我必须在堆上分配它，这意味着在 recusrion 树的叶子上分配内存。也许另一种选择是具有静态大小的 vaue 类型，该类型应该足够大以容纳我目前打算支持的大小的对象。但这意味着 reference_type 之间的关系会更加骇人听闻。和 value_type迭代器类。这意味着我必须为我的应用程序更新该大小以支持更大的对象。丑陋的。

如果您能想到一种干净的方法来让上述代码操作我的数据而无需动态分配内存，那将是一个很好的解决方案。 我已经在使用 C++11 特性，所以使用移动语义或类似的不会有问题。

4.自定义排序

我什至考虑过重新实现所有的快速排序。也许我可以利用这样一个事实，即我的比较主要是按字典顺序进行比较，即我可以按第一个字节对序列进行排序，并且只有在所有元素的第一个字节都相同时才切换到下一个字节。我还没有弄清楚这方面的细节，但是 如果有人可以建议将引用、实现甚至规范名称用作这种逐字节词典排序的关键字，我会很高兴。 我仍然不相信通过我的合理努力，我可以击败 STL 模板实现的性能。

5.完全不同的算法

我知道有很多种排序算法。其中一些可能更适合我的问题。我首先想到的是基数排序，但我还没有真正考虑过这个问题。 如果您可以建议更适合我的问题的排序算法，请这样做。最好有实现，但即使没有。

题

所以基本上我的问题是这样的:
“如何有效地对堆内存中的动态大小对象进行排序？”

这个问题的任何回答都适用于我的情况，无论是否与我自己的想法有关。对以粗体标记的个别问题的答案，或任何其他可能帮助我在备选方案之间做出决定的见解，也会很有用，特别是如果没有对单一方法的明确答案。

Answer 1

由于只有 31 个不同的对象变体(1 到 32 个字节)，您可以轻松地为每个对象创建一个对象类型并选择对 std::sort 的调用。基于 switch 语句。每个调用都将被内联并高度优化。

某些对象大小可能需要自定义迭代器，因为编译器会坚持填充 native 对象以对齐地址边界。在其他情况下，指针可以用作迭代器，因为指针具有迭代器的所有属性。