AnT*_*AnT 46 c++ sorting algorithm mergesort list
我记得,从一开始,最流行的实现方法std::list<>::sort()是以自下而上的方式实现的经典Merge Sort算法(另请参阅是什么让gcc std :: list排序实现如此之快？).
我记得有人恰如其分地将这种策略称为"洋葱链"方法.
至少这是GCC实现C++标准库的方式(例如,参见这里).这就是旧版Dimkumware在标准库的MSVC版本中的STL,以及所有版本的MSVC到VS2013的情况.
但是,随VS2015提供的标准库突然不再遵循此排序策略.VS2015附带的库使用自上而下的 Merge Sort 的相当简单的递归实现.这让我感到很奇怪,因为自上而下的方法需要访问列表的中点才能将其分成两半.由于std::list<>不支持随机访问,找到该中间点的唯一方法是逐字遍历列表的一半.此外,在最开始时,有必要知道列表中的元素总数(在C++ 11之前不一定是O(1)操作).
尽管如此,std::list<>::sort()在VS2015确实如此.以下是该实现的摘录,它定位中点并执行递归调用
...
iterator _Mid = _STD next(_First, _Size / 2);
_First = _Sort(_First, _Mid, _Pred, _Size / 2);
_Mid = _Sort(_Mid, _Last, _Pred, _Size - _Size / 2);
...
正如您所看到的,他们只是无意中使用std::next了遍历列表的前半部分并到达_Mid迭代器.
我想知道这种转变背后的原因是什么？我所看到的是std::next在每个递归级别上重复调用看似明显的低效率.天真的逻辑说这是慢的.如果他们愿意支付这种价格,他们可能希望获得回报.那他们得到了什么？我没有立即将此算法视为具有更好的缓存行为(与原始自下而上方法相比).我没有立即看到它在预先排序的序列上表现得更好.
当然,由于C++ 11 std::list<>基本上需要存储其元素数,这使得上面的效率略高,因为我们总是提前知道元素数.但这仍然不足以证明每个递归级别的顺序扫描是正确的.
(不可否认,我没有试图相互竞争实施.也许有一些惊喜.)
rcg*_*ldr 21
更新 - VS2015引入了非默认可构造和有状态分配器,这在使用本地列表时会出现问题,就像之前的自下而上方法一样.我能够通过使用节点指针而不是列表(见下文)来处理这个问题,以实现自下而上的方法.
在@ sbi的评论中,他向作者提出了自上而下的批评,Stephan T. Lavavej,为什么要做出改变.Stephan的回答是"避免内存分配和默认构建分配器".新的自顶向下方法比旧的自底向上方法慢,但它只使用迭代器(递归地存储在堆栈上),不使用任何本地列表并避免与非默认可构造或有状态分配器相关的问题.@ TC的回答详细介绍了这一点.
至于性能,如果有足够的内存,将列表移动到数组或向量,排序,然后将已排序的数组或向量移回列表通常会更快.
基于@IgorTandetnik的演示,我能够重现这个问题(旧的编译无法编译,新的编译工作):
#include <iostream>
#include <list>
#include <memory>
template <typename T>
class MyAlloc : public std::allocator<T> {
public:
MyAlloc(T) {} // suppress default constructor
template <typename U>
MyAlloc(const MyAlloc<U>& other) : std::allocator<T>(other) {}
template< class U > struct rebind { typedef MyAlloc<U> other; };
};
int main()
{
std::list<int, MyAlloc<int>> l(MyAlloc<int>(0));
l.push_back(3);
l.push_back(0);
l.push_back(2);
l.push_back(1);
l.sort();
return 0;
}
我在2016年7月发现了这一变化,并于2016年8月1日通过电子邮件向PJ Plauger发送了关于此更改的电子邮件.他回复的片段:
有趣的是,我们的更改日志并未反映此更改.这可能意味着它是由我们的一个大客户"建议"并由我在代码审查中得到的.我现在所知道的是,这个变化发生在2015年秋天左右.当我查看代码时,第一件令我印象深刻的是这条线:
Run Code Online (Sandbox Code Playgroud)iterator _Mid = _STD next(_First, _Size / 2);当然,对于大型清单来说,这可能需要很长时间.
代码看起来比我在1995年初写的更优雅(!),但肯定有更糟糕的时间复杂性.该版本是在Stepanov,Lee和Musser在原始STL中采用的方法之后建模的.他们在选择算法时很少被发现是错误的.
我现在正在恢复原始代码的最新已知良好版本.
我不知道PJ Plauger对原始代码的回归是否涉及新的分配器问题,或者微软是否或如何与Dinkumware交互.
为了比较自顶向下和自底向上的方法,我创建了一个包含400万个元素的链表,每个元素由一个64位无符号整数组成,假设我最终会得到几乎顺序排列的节点的双向链表(即使它们是将被动态分配),用随机数填充它们,然后对它们进行排序.节点不移动,只更改链接,但现在遍历列表以随机顺序访问节点.然后我用另一组随机数填充那些随机排序的节点并再次对它们进行排序.我将2015年自上而下的方法与之前自下而上的方法进行了比较,修改后的方法与2015年的其他更改相匹配(sort()现在使用谓词比较函数调用sort(),而不是使用两个单独的函数).这些是结果.更新 - 我添加了一个基于节点指针的版本,还注意到从列表中创建向量,排序向量,复制回来的时间.
sequential nodes: 2015 version 1.6 seconds, prior version 1.5 seconds
random nodes: 2015 version 4.0 seconds, prior version 2.8 seconds
random nodes: node pointer based version 2.6 seconds
random nodes: create vector from list, sort, copy back 1.25 seconds
对于顺序节点,先前版本仅稍微快一点,但对于随机节点,先前版本快30%,节点指针版本快35%,并从列表创建向量,对向量进行排序,然后复制回来比69%快.
下面是std :: list :: sort()的第一个替换代码我用来比较先前的自下而上与小数组(_BinList [])方法与VS2015的自上而下方法我希望比较是公平的,所以我修改了一个<list>的副本.
void sort()
{ // order sequence, using operator<
sort(less<>());
}
template<class _Pr2>
void sort(_Pr2 _Pred)
{ // order sequence, using _Pred
if (2 > this->_Mysize())
return;
const size_t _MAXBINS = 25;
_Myt _Templist, _Binlist[_MAXBINS];
while (!empty())
{
// _Templist = next element
_Templist._Splice_same(_Templist.begin(), *this, begin(),
++begin(), 1);
// merge with array of ever larger bins
size_t _Bin;
for (_Bin = 0; _Bin < _MAXBINS && !_Binlist[_Bin].empty();
++_Bin)
_Templist.merge(_Binlist[_Bin], _Pred);
// don't go past end of array
if (_Bin == _MAXBINS)
_Bin--;
// update bin with merged list, empty _Templist
_Binlist[_Bin].swap(_Templist);
}
// merge bins back into caller's list
for (size_t _Bin = 0; _Bin < _MAXBINS; _Bin++)
if(!_Binlist[_Bin].empty())
this->merge(_Binlist[_Bin], _Pred);
}
我做了一些小改动.原始代码跟踪名为_Maxbin的变量中的实际最大bin,但最终合并中的开销足够小,以至于我删除了与_Maxbin关联的代码.在数组构建期间,原始代码的内部循环合并到_Binlist []元素中,然后交换到_Templist,这似乎毫无意义.我将内部循环更改为仅合并到_Templist,只有在找到空的_Binlist []元素时才进行交换.
下面是一个基于节点指针的替换std :: list :: sort()我用于另一个比较.这消除了分配相关的问题.如果可能发生比较异常,则必须将数组和临时列表(pNode)中的所有节点追加回原始列表,或者可能将比较异常视为小于比较.
void sort()
{ // order sequence, using operator<
sort(less<>());
}
template<class _Pr2>
void sort(_Pr2 _Pred)
{ // order sequence, using _Pred
const size_t _NUMBINS = 25;
_Nodeptr aList[_NUMBINS]; // array of lists
_Nodeptr pNode;
_Nodeptr pNext;
_Nodeptr pPrev;
if (this->size() < 2) // return if nothing to do
return;
this->_Myhead()->_Prev->_Next = 0; // set last node ->_Next = 0
pNode = this->_Myhead()->_Next; // set ptr to start of list
size_t i;
for (i = 0; i < _NUMBINS; i++) // zero array
aList[i] = 0;
while (pNode != 0) // merge nodes into array
{
pNext = pNode->_Next;
pNode->_Next = 0;
for (i = 0; (i < _NUMBINS) && (aList[i] != 0); i++)
{
pNode = _MergeN(_Pred, aList[i], pNode);
aList[i] = 0;
}
if (i == _NUMBINS)
i--;
aList[i] = pNode;
pNode = pNext;
}
pNode = 0; // merge array into one list
for (i = 0; i < _NUMBINS; i++)
pNode = _MergeN(_Pred, aList[i], pNode);
this->_Myhead()->_Next = pNode; // update sentinel node links
pPrev = this->_Myhead(); // and _Prev pointers
while (pNode)
{
pNode->_Prev = pPrev;
pPrev = pNode;
pNode = pNode->_Next;
}
pPrev->_Next = this->_Myhead();
this->_Myhead()->_Prev = pPrev;
}
template<class _Pr2>
_Nodeptr _MergeN(_Pr2 &_Pred, _Nodeptr pSrc1, _Nodeptr pSrc2)
{
_Nodeptr pDst = 0; // destination head ptr
_Nodeptr *ppDst = &pDst; // ptr to head or prev->_Next
if (pSrc1 == 0)
return pSrc2;
if (pSrc2 == 0)
return pSrc1;
while (1)
{
if (_DEBUG_LT_PRED(_Pred, pSrc2->_Myval, pSrc1->_Myval))
{
*ppDst = pSrc2;
pSrc2 = *(ppDst = &pSrc2->_Next);
if (pSrc2 == 0)
{
*ppDst = pSrc1;
break;
}
}
else
{
*ppDst = pSrc1;
pSrc1 = *(ppDst = &pSrc1->_Next);
if (pSrc1 == 0)
{
*ppDst = pSrc2;
break;
}
}
}
return pDst;
}
作为新VS2015 std :: list :: sort()的替代,您可以使用此独立版本.
template <typename T>
void listsort(std::list <T> &dll)
{
const size_t NUMLISTS = 32;
std::list <T> al[NUMLISTS]; // array of lists
std::list <T> tl; // temp list
while (!dll.empty()){
// t1 = next element from dll
tl.splice(tl.begin(), dll, dll.begin(), std::next(dll.begin()));
// merge element into array
size_t i;
for (i = 0; i < NUMLISTS && !al[i].empty(); i++){
tl.merge(al[i], std::less<T>());
}
if(i == NUMLISTS) // don't go past end of array
i -= 1;
al[i].swap(tl); // update array list, empty tl
}
// merge array back into original list
for(size_t i = 0; i < NUMLISTS; i++)
dll.merge(al[i], std::less<T>());
}
或使用类似的gcc算法.
@sbi问 MSVC的标准图书馆维护者Stephan T. Lavavej,他回答说:
我这样做是为了避免内存分配和默认构造分配器.
为此,我将添加"免费基本异常安全".
详细说明:VS2015之前的实现存在以下缺陷:
_Myt _Templist, _Binlist[_MAXBINS];创建了一堆中间lists(_Myt对于当前实例化而言只是一个typedef list;对于那个更不容易混淆的拼写list),在排序期间保持节点,但是这些list是默认构造的,这导致了许多问题:
list将尝试默认构造其分配器.this->get_allocator(),这意味着后面的splices和merges在技术上是未定义的行为,并且可能在调试构建中中断.("技术上",因为节点都在最后合并回来,所以如果函数成功完成,你实际上不会使用错误的分配器解除分配.)list使用动态分配的Sentinel节点,这意味着上面将执行_MAXBINS + 1动态分配.我怀疑很多人都希望sort有可能抛出bad_alloc.如果分配器是有状态的,那么这些前哨节点可能甚至不能从正确的位置分配(参见#2).lists中存在元素时抛出,则list在堆栈展开期间使用s 简单地销毁这些元素.当然,sort如果sort抛出异常,用户不希望对列表进行排序,但他们可能也不希望元素丢失.
lists 的析构函数将解除分配,并使用错误的分配器销毁拼接到它们中的节点.这些缺陷是否可以修复？大概.可以通过传递get_allocator()给lists 的构造函数来修复#1和#2 :
_Myt _Templist(get_allocator());
_Myt _Binlist[_MAXBINS] = { _Myt(get_allocator()), _Myt(get_allocator()),
_Myt(get_allocator()), /* ... repeat _MAXBINS times */ };
如果抛出异常,可以通过围绕循环来修复异常安全问题,该循环try-catch将中间lists 中的所有节点拼接回来*this而不考虑顺序.
修复#3更难,因为这意味着根本不使用list节点的持有者,这可能需要大量的重构,但它是可行的.
问题是:是否值得跳过所有这些环节以改善设计性能降低的容器的性能？毕竟,真正关心性能的人可能不会list在第一时间使用.
| 归档时间： |
|
| 查看次数： |
1418 次 |
| 最近记录： |