logo标签列表

`std::list<>::sort()` - 为什么突然转向自顶向下的策略？

c++algorithmsortinglinked-listmergesort
54
更新 - Visual Studio 2022 切换到了一种高效的自底向上归并排序的递归实现，并重新使用指针而非迭代器。合并逻辑在可能的情况下改进为一次拼接多个节点。这些变化保留了对于VS2015更改的无内存分配和异常安全修复的原因。
我记得自古以来，实现std::list<>::sort()最流行的方法是经典的自底向上的归并排序算法（参见bottom-up fashion）。
我记得有人巧妙地将这种策略称为"洋葱链"方法。
至少在GCC的C++标准库实现中是这样的（例如，参见here）。在旧版Dimkumware的MSVC标准库中，以及所有版本的MSVC直到VS2013，都是这样实现的。
然而，随着VS2015提供的标准库突然不再遵循这种排序策略。VS2015附带的库使用了一个相当直接的递归实现的自上而下的归并排序。这让我感到奇怪，因为自上而下的方法需要访问列表的中点以将其分成两半。由于std::list<>不支持随机访问，找到中点的唯一方法就是逐字迭代列表的一半。此外，在开始时需要知道列表中元素的总数（在C++11之前这不一定是O(1)的操作）。
尽管如此，VS2015中的std::list<>::sort()确实做到了这一点。以下是该实现中定位中点并执行递归调用的摘录。
...
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<>基本上需要存储其元素计数，这使得上述过程稍微更高效，因为我们总是提前知道元素计数。但这似乎还不足以证明在每个递归层级上进行顺序扫描的合理性。
（诚然，我还没有尝试将这些实现相互比较。也许会有一些意外之处。）
3
“在C++11之前，这不一定是O(1)操作”是不相关的。 他们正在为自己的实现编写代码，其 size（） 是 O（1）。 - T.C.
1
@T.C.：是的，但O(1)的size()在这里并没有太大的区别。它只有在递归的最顶层才有用。仅有O(1)的size()还不足以证明这个算法的优越性。我对此的主要问题是每个递归层级都需要O(n)的std::next，这与顶层的O(1) size()并没有真正的关系。 - AnT stands with Russia
1
@cmaster：你的说法是错误的。请注意，找到中点的理论价格是O（N），而我们在O（log N）深度上执行它，因此总成本为O（N log N）。排序始终是O（N log N），因此理论界限不会改变。对于实际性能，您需要考虑真实的硬件。 - MSalters
2
@mSalters 复杂度并没有改变，我也从未这么说过。然而，通过在列表的中点处扫描两次，算法失去了一个常数因子的时间，使得算法变得次优。如果我们仅考虑复杂度，我们将不得不始终使用直接基数排序，因为它是O(n)，比快速排序和其他算法实现的O(log(n))更好。尽管如此，直接基数排序具有如此高的常数项，以至于在所有相关情况下都比快速排序慢，使直接基数排序无用。永远不要忘记常数！ - cmaster - reinstate monica
9
直接引用原话："我这么做是为了避免内存分配和默认构造分配器。" - Stephan T. Lavavej (来自权威人士口中) - sbi
显示剩余16条评论
2个回答
24
更新 - Visual Studio 2022 切换到了一种高效的自底向上归并排序的递归实现，并重新使用指针而非迭代器。合并逻辑在可能的情况下改进为一次性拼接多个节点。这些变化保留了为VS2015更改提供的无内存分配和异常安全修复的原因。
    template <class _Pr2>
    static _Nodeptr _Sort(_Nodeptr& _First, const size_type _Size, _Pr2 _Pred) {
        // order [_First, _First + _Size), return _First + _Size
        switch (_Size) {
        case 0:
            return _First;
        case 1:
            return _First->_Next;
        default:
            break;
        }

        auto _Mid        = _Sort(_First, _Size / 2, _Pred);
        const auto _Last = _Sort(_Mid, _Size - _Size / 2, _Pred);
        _First           = _Merge_same(_First, _Mid, _Last, _Pred);
        return _Last;
    }
// ...
    void sort() { // order sequence
        sort(less<>{});
    }

    template <class _Pr2>
    void sort(_Pr2 _Pred) { // order sequence
        auto& _My_data = _Mypair._Myval2;
        _Scary_val::_Sort(_My_data._Myhead->_Next, _My_data._Mysize, _Pass_fn(_Pred));
    }

这可以稍微改进一下（大约快4%），通过在sort()中检查(_My_data._Mysize < 2)，然后只需要在_Sort()中检查(_Size == 1)。
    template <class _Pr2>
    static _Nodeptr _Sort(_Nodeptr& _First, const size_type _Size, _Pr2 _Pred) {
        // order [_First, _First + _Size), return _First + _Size
        if (_Size == 1)
            return _First->_Next;
        auto _Mid        = _Sort(_First, _Size / 2, _Pred);
        const auto _Last = _Sort(_Mid, _Size - _Size / 2, _Pred);
        _First           = _Merge_same(_First, _Mid, _Last, _Pred);
        return _Last;
    }
// ...
    void sort() { // order sequence
        sort(less<>{});
    }

    template <class _Pr2>
    void sort(_Pr2 _Pred) { // order sequence
        auto& _My_data = _Mypair._Myval2;
        if (_My_data._Mysize < 2)
            return;
        _Scary_val::_Sort(_My_data._Myhead->_Next, _My_data._Mysize, _Pass_fn(_Pred));
    }
这个答案的剩余部分是历史性的，主要是关于我使用迭代器实现的自底向上归并排序，以替代Visual Studio 2015至2019中的自顶向下归并排序。
起初我以为微软在切换到使用迭代器时不会采用效率较低的自上而下的归并排序，除非有必要，所以我在寻找替代方案。直到我试图分析这些问题（出于好奇），我才意识到原始的自下而上的归并排序可以修改为与迭代器一起使用。
在@sbi的评论中，他问自上而下方法的作者Stephan T. Lavavej为什么要改用迭代器。Stephan的回答是“为了避免内存分配和默认构造分配器”。VS2015引入了非默认可构造和有状态的分配器，这在使用先前版本的列表数组时会出现问题，因为每个列表实例都会分配一个虚拟节点，需要进行更改以处理没有默认分配器的情况。
Lavavej的解决方案是使用迭代器来跟踪原始列表中的运行边界，而不是使用内部列表数组。合并逻辑被改为使用3个迭代器参数，第一个参数是左运行的起始迭代器，第二个参数是左运行的结束迭代器（等于右运行的起始迭代器），第三个参数是右运行的结束迭代器。合并过程使用std::list::splice在合并操作期间在原始列表中移动节点。这样做的额外好处是可以确保异常安全。如果调用者的比较函数抛出异常，列表将被重新排序，但不会丢失数据（假设splice不会失败）。在之前的方案中，如果发生异常，一些（或大部分）数据将位于内部列表数组中，并且原始列表中的数据将丢失。
我将自底向上的归并排序改为使用迭代器数组而不是链表数组，其中array[i]是一个指向具有2^i个节点的已排序运行的起始位置的迭代器，或者它是空的（使用std::list::end表示空，因为迭代器不能为null）。与自顶向下的方法类似，迭代器数组仅用于在原始链表中跟踪已排序运行的边界，并使用与自顶向下相同的合并逻辑，使用std::list::splice在原始链表中移动节点。
对列表进行单次扫描，根据数组中的已排序运行边界，在当前scan.next位置的左侧构建已排序运行，直到所有节点都合并到已排序运行中。然后合并已排序运行，得到一个排序后的列表。
例如，对于一个包含7个节点的列表，在扫描之后：
2                       1           0          array index
run0->run0->run0->run0->run1->run1->run2->end

然后通过merge（left，right）从右到左合并3个已排序的运行，以保证排序的稳定性。
如果链表很大且节点分散，会有很多缓存未命中，从上到下的排序速度会比从下到上慢40%到50%，具体取决于处理器。然而，如果有足够的内存，通常将链表转移到数组或向量中，对数组或向量进行排序，然后从排序后的数组或向量创建新的链表会更快。
示例C++代码：
template <typename T>
typename std::list<T>::iterator Merge(std::list<T> &ll,
                    typename std::list<T>::iterator li,
                    typename std::list<T>::iterator ri,
                    typename std::list<T>::iterator ei);

// iterator array size
#define ASZ 32

template <typename T>
void SortList(std::list<T> &ll)
{
    if (ll.size() < 2)                  // return if nothing to do
        return;
    typename std::list<T>::iterator ai[ASZ]; // array of iterator (bgn lft)
    typename std::list<T>::iterator ri;      // right    iterator (end lft, bgn rgt)
    typename std::list<T>::iterator ei;      // end      iterator (end rgt)
    size_t i;
    for (i = 0; i < ASZ; i++)           // "clear" array
        ai[i] = ll.end();
    // merge nodes into array of runs
    for (ei = ll.begin(); ei != ll.end();) {
        ri = ei++;
        for (i = 0; (i < ASZ) && ai[i] != ll.end(); i++) {
            ri = Merge(ll, ai[i], ri, ei);
            ai[i] = ll.end();
        }
        if(i == ASZ)
            i--;
        ai[i] = ri;
    }
    // merge array of runs into single sorted list
    // ei = ll.end();                              
    for(i = 0; (i < ASZ) && ai[i] == ei; i++);
    ri = ai[i++];
    while(1){
        for( ; (i < ASZ) && ai[i] == ei; i++);
        if (i == ASZ)
            break;
        ri = Merge(ll, ai[i++], ri, ei);
    }
}

template <typename T>
typename std::list<T>::iterator Merge(std::list<T> &ll,
                             typename std::list<T>::iterator li,
                             typename std::list<T>::iterator ri,
                             typename std::list<T>::iterator ei)
{
    typename std::list<T>::iterator ni;
    (*ri < *li) ? ni = ri : ni = li;
    while(1){
        if(*ri < *li){
            ll.splice(li, ll, ri++);
            if(ri == ei)
                return ni;
        } else {
            if(++li == ri)
                return ni;
        }
    }
}

这是一个用于VS2019的std::list::sort()的示例替换代码，包含在list的头文件中。合并逻辑已经被拆分为一个单独的内部函数，因为它现在在两个地方使用。在std::list::sort()中调用_Sort的代码是_Sort(begin(), end(), _Pred, this->_Mysize());，其中_Pred是指向比较函数的指针（默认为std::less()）。

private:
    template <class _Pr2>
    iterator _Merge(_Pr2 _Pred, iterator _First, iterator _Mid, iterator _Last){
        iterator _Newfirst = _First;
        for (bool _Initial_loop = true;;
            _Initial_loop       = false) { // [_First, _Mid) and [_Mid, _Last) are sorted and non-empty
            if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First)) { // consume _Mid
                if (_Initial_loop) {
                    _Newfirst = _Mid; // update return value
                }
                splice(_First, *this, _Mid++);
                if (_Mid == _Last) {
                    return _Newfirst; // exhausted [_Mid, _Last); done
                }
            }
            else { // consume _First
                ++_First;
                if (_First == _Mid) {
                    return _Newfirst; // exhausted [_First, _Mid); done
                }
            }
        }
    }

    template <class _Pr2>
    void _Sort(iterator _First, iterator _Last, _Pr2 _Pred,
        size_type _Size) { // order [_First, _Last), using _Pred, return new first
                           // _Size must be distance from _First to _Last
        if (_Size < 2) {
            return;        // nothing to do
        }
        const size_t _ASZ = 32;         // array size
        iterator _Ai[_ASZ];             // array of   iterator to run (bgn lft)
        iterator _Mi;                   // middle     iterator to run (end lft, bgn rgt)
        iterator _Li;                   // last (end) iterator to run (end rgt)
        size_t _I;                      // index to _Ai
        for (_I = 0; _I < _ASZ; _I++)   // "empty" array
            _Ai[_I] = _Last;            //   _Ai[] == _Last => empty entry
        // merge nodes into array of runs
        for (_Li = _First; _Li != _Last;) {
            _Mi = _Li++;
            for (_I = 0; (_I < _ASZ) && _Ai[_I] != _Last; _I++) {
                _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I], _Mi, _Li);
                _Ai[_I] = _Last;
            }
            if (_I == _ASZ)
                _I--;
            _Ai[_I] = _Mi;
        }
        // merge array of runs into single sorted list
        for (_I = 0; _I < _ASZ && _Ai[_I] == _Last; _I++);
        _Mi = _Ai[_I++];
        while (1) {
            for (; _I < _ASZ && _Ai[_I] == _Last; _I++);
            if (_I == _ASZ)
                break;
            _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I++], _Mi, _Last);
        }
    }
我注意到这个变化是在2016年7月，然后在2016年8月1日给P.J. Plauger发了一封邮件询问这个变化。他的回复摘录如下：

Interestingly enough, our change log doesn't reflect this change. That probably means it was "suggested" by one of our larger customers and got by me on the code review. All I know now is that the change came in around the autumn of 2015. When I reviewed the code, the first thing that struck me was the line:

    iterator _Mid = _STD next(_First, _Size / 2);

which, of course, can take a very long time for a large list.

The code looks a bit more elegant than what I wrote in early 1995(!), but definitely has worse time complexity. That version was modeled after the approach by Stepanov, Lee, and Musser in the original STL. They are seldom found to be wrong in their choice of algorithms.

I'm now reverting to our latest known good version of the original code.

这个实现与GCC一样存在问题：它不能正确处理非默认可构造分配器或有状态的分配器。在Dinkumware的情况下，它还会导致动态分配，因为他们的list有一个动态分配的哨兵节点。当然，这个问题是可以解决的。 - T.C.
_Templist 和 _Binlist 被默认构造。它们不一定是默认可构造的（因为它们的分配器不需要是这样的）。 - T.C.
否则会出现编译时错误。这基本上就是重点...如果分配器没有默认构造函数，旧实现根本无法编译。 - T.C.
你可以始终传递 this->get_allocator()，但那只会解决问题的1 / (3 * (_MAXBINS + 1))。请参见我的回答。 - T.C.
1
“Comparator function defines a strict weak ordering” 是合同的一部分。“Comparator function does not throw” 不是。 - T.C.
显示剩余12条评论
10

@sbi问道MSVC的标准库维护者Stephan T. Lavavej，他回答道：

我这样做是为了避免内存分配和默认构造分配器。

我要补充的是“基本异常安全的释放”。

详细解释：在VS2015之前的实现存在几个缺陷：

  • _Myt _Templist, _Binlist[_MAXBINS]; 创建了一堆中间的list（_Myt只是当前实例化的list的一个typedef，一个不那么令人困惑的拼写方式是list），用于在排序过程中保存节点，但这些list是默认构造的，这导致了许多问题：
    1. 如果使用的分配器不可默认构造（并且没有要求分配器可默认构造），则这将无法编译，因为list的默认构造函数将尝试默认构造其分配器。
    2. 如果使用的分配器具有状态，则默认构造的分配器可能与this->get_allocator()不相等，这意味着稍后的splice和merge在技术上是未定义的行为，并且可能会在调试版本中出现故障。（“技术上”，因为所有节点最终都合并在一起，因此如果函数成功完成，则实际上不会使用错误的分配器进行解除分配。）
    3. Dinkumware的list使用动态分配的哨兵节点，这意味着上述代码将执行_MAXBINS + 1次动态分配。我怀疑有多少人期望sort可能会抛出bad_alloc。如果分配器具有状态，则这些哨兵节点甚至可能不是从正确的位置分配的（请参见#2）。
  • 代码不具备异常安全性。特别是，比较操作允许抛出异常，如果在中间的list中有元素时抛出异常，则这些元素将在堆栈展开期间与list一起被销毁。当然，使用sort的用户不希望在sort抛出异常时对列表进行排序，但他们可能也不希望元素丢失。
    • 这与上述#2非常不匹配，因为现在它不仅是技术上未定义的行为：那些中间list的析构函数将使用错误的分配器解除分配并销毁插入到其中的节点。
这些问题可以修复吗？很可能可以。通过将get_allocator()传递给list的构造函数，可以修复#1和#2：
 _Myt _Templist(get_allocator());
 _Myt _Binlist[_MAXBINS] = { _Myt(get_allocator()), _Myt(get_allocator()), 
                             _Myt(get_allocator()),  /* ... repeat _MAXBINS times */ };

异常安全问题可以通过在循环周围加上一个try-catch来解决，如果抛出异常，则将所有中间的list节点拼接回*this而不考虑顺序。
修复问题#3更难，因为这意味着根本不使用list作为节点的持有者，这可能需要相当多的重构，但是可行的。
问题是：值得跳过所有这些麻烦来改进一个设计上性能降低的容器的性能吗？毕竟，真正关心性能的人可能根本不会首先使用list。
3
是的，没有人说这是不可实施的。问题在于是否值得付出努力。 - T.C.
@rcgldr 自 C++98 以来，list::sort 的规范已经提供了关于异常情况下会发生什么的条款。因此，“STL 的这一部分”非常关注此事。 - T.C.
我更新了我的答案，展示了一个独立的自底向上归并排序版本，它使用了一个小型迭代器数组，应该可以消除分配器和异常问题。 - rcgldr
由于我的答案已经更新，使用了与列表相同的更改来使用迭代器，因此我删除了现在过时的评论。 "值得努力" - 一旦考虑使用迭代器，将先前的自下而上归并排序从列表数组切换为迭代器数组只需要几个小时来分析问题并使其正常工作。我怀疑切换到迭代器和自上而下可能需要同样长的时间或更长时间，除非有现有的示例可以基于VS2015的更改。我认为这不是一个“努力”的问题，而是要认识到自下而上可以改用迭代器。 - rcgldr
继续说，我最初没有考虑迭代器的原因是由于VS2015改变了自顶向下的方式，让我认为尝试将现有的自底向上算法改为使用迭代器存在一些问题。只有当我自己尝试分析切换到迭代器时，我才意识到有一个解决方案。 - rcgldr
显示剩余6条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接