MvG*_*MvG 12 c++ sorting stl g++ stl-algorithm
假设我有一个包含一些数据的大量字节(最多4GB).这些字节对应于这样的方式,每一个不同的对象小号字节(认为小号最多32个)将构成一个对象.一个重要的事实是,对于所有对象,此大小s是相同的,不存储在对象本身内,并且在编译时不知道.
目前,这些对象只是逻辑实体,而不是编程语言中的对象.我对这些对象进行了比较,其中包括对大多数对象数据的字典对比,以及使用剩余数据打破关系的一些不同功能.现在我想将这些对象进行排序效率(这是真的要成为应用的瓶颈).
我想到了几种可能的方法来实现这一目标,但是每一种方法似乎都有一些相当不幸的后果.您不一定非必须阅读所有这些内容.我试图用粗体打印每种方法的核心问题. 如果您打算提出其中一种方法,那么您的答案也应该回答相关问题.
当然,C快速排序算法也可用于C++应用程序.它的标志几乎完美符合我的要求.但是使用该函数将禁止内联比较函数的事实将意味着每个比较都带有函数调用开销.我曾希望有办法避免这种情况.任何关于C qsort_r在性能方面与STL相比的经验都是非常受欢迎的.
编写一堆包含指向各自数据的指针的对象会很容易.那么人们就可以对它们进 这里有两个方面需要考虑.一方面,仅仅移动指针而不是所有数据意味着更少的内存操作.另一方面,不移动对象可能会破坏内存局部性,从而破坏缓存性能.有可能实际上从一些缓存页面访问所有数据的更快的快速排序递归水平几乎完全消失.相反,每个缓存的内存页面在被替换之前只会产生非常少的可用数据项.如果有人能提供一些关于复制和记忆位置之间权衡的经验,我会很高兴.
我写了一个类作为内存范围的迭代器.取消引用此迭代器不会产生引用,而是产生一个新构造的对象来保存指向数据的指针和在构造迭代器时给出的大小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功能了,所以使用移动语义或类似功能不会有问题.
我甚至考虑重新实现所有的快速排序.也许我可以利用这样一个事实,即我的比较主要是字典比较,即我可以按第一个字节对序列进行排序,只有当所有元素的firt字节相同时才切换到下一个字节.我还没有弄清楚这方面的细节,但是如果有人可以建议一个引用,一个实现,甚至一个规范的名称作为这样一个按字节顺序排列的词典排序的关键字,我会非常高兴.我仍然不相信通过合理的努力,我可以击败STL模板实现的性能.
我知道那里有很多种排序算法.其中一些可能更适合我的问题.我首先想到了基数排序,但我还没有想到这一点.如果您可以建议更适合我的问题的排序算法,请执行此操作.优选实施,但即使没有.
所以基本上我的问题是:
"你如何有效地在堆内存中对动态大小的对象进行排序？"
任何适用于我的情况的问题的答案都是好的,无论它是否与我自己的想法有关.以粗体标记的个别问题的答案,或任何其他可能帮助我在我的选择之间做出决定的见解也是有用的,特别是如果没有对单一方法的明确答案出现.
由于只有 31 种不同的对象变体（1 到 32 字节），因此您可以轻松地为每种对象创建一个对象类型，并std::sort根据 switch 语句选择调用。每个调用都将被内联并高度优化。
某些对象大小可能需要自定义迭代器，因为编译器将坚持填充本机对象以与地址边界对齐。在其他情况下，指针可以用作迭代器，因为指针具有迭代器的所有属性。