特殊的排序算法和通用签名 [英] special sorting algorithm and generic signature

问题描述

我有一个强大的用例来定义自己的排序算法，该算法比stl中最快的算法要快，并且通过利用基础数据的一些不错的属性，我基本上可以在 O(n).

I have a strong use-case to define my own sorting algorithm, which is faster than the fastest in stl and by exploiting some nice properties of the underlying data I basically can sort in O(n).

到目前为止，到目前为止，问题是我想提供一个通用接口，该接口适合任何类型的容器，例如 T * 或 std :: vector< T> 等，只要适用几个关键概念，例如

So far so good, now the problem is that I would like to offer a generic interface which will fit any type of container e.g. T* or std::vector<T> etc, as long as couple of key concepts apply e.g.

• 有一个有效的运算符[]可用于访问集合的元素
• 集合中的元素支持小于"可比概念.

要想出主意，我转到了头文件< std_algo.h> ，并找到了下面的函数接口，除了一个细节外，它与我要查找的内容完全匹配，我不知道如何遍历底层的 _RandomAccessIterator 会被编译器自动向量化，而不考虑容器类型，这是我的问题...有什么办法可以全部实现?自动向量化+通用接口无视基础集合类型?

To get ideas I went to the header file <std_algo.h> and found the function interface below which matches exactly what I'm looking for except one detail, I don't see how looping through the underlying _RandomAccessIterator will be auto-vectorized by the compiler disregard of the container type and this is my question ... is there a way I can have it all? auto-vectorization + generic interface disregard of the underlying collection type?

我认为下面的代码不会自动矢量化，这是由于 while(__last-__first> int(_S_threshold))和 if(__depth_limit == 0)，但是我的算法不需要这最后一个.因此，我看到非规范类型的循环会阻止自动矢量化.

I think the code below won't auto-vectorize due to the "non-canonical" loop pattern while (__last - __first > int(_S_threshold)) and conditions like if (__depth_limit == 0) but this last I won't need in my algorithm. So I see the auto-vectorization would be prevented by the non-canonical type of loop.

template<typename _RandomAccessIterator, typename _Compare> 
inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
    _ValueType;

    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    _RandomAccessIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
    _ValueType>)
    __glibcxx_requires_valid_range(__first, __last);

    if (__first != __last)
    {
        std::__introsort_loop(__first, __last,
        std::__lg(__last - __first) * 2, __comp);
        std::__final_insertion_sort(__first, __last, __comp);
    }
}

有问题的循环看起来像这样:

The loop in question looks like this:

// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare> 
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
{
    while (__last - __first > int(_S_threshold))
    {
        if (__depth_limit == 0)
        {
            _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
            return;
        }
        --__depth_limit;
        _RandomAccessIterator __cut =
        std::__unguarded_partition_pivot(__first, __last, __comp);
        std::__introsort_loop(__cut, __last, __depth_limit, __comp);
        __last = __cut;
    }
}

推荐答案

标准C ++库在标准算法(例如sort())中使用迭代器.这允许算法实现忽略基础容器的确切详细信息.另外，这种方法不允许使用 operator []()进行索引.

The Standard C++ Library uses iterators in standard algorithms, such as sort(). This allows the algorithm implementation to ignore the exact details of the underlying container. Also, this approach doesn't allow for indexing with operator[]().

考虑到这一点，我有两个建议供您考虑:

With that in mind, I have two suggestions for you to consider:

1)修改您的专用排序以使用迭代器，而不是使用 operator []()来访问容器中的元素.如果可以保持所需的O(n)速度，那么这可能是最理想的灵活性方法.

1) Revise your specialized sort to use iterators, rather than operator[]() to access elements in the container. If it is possible to maintain your desired O(n) speed, then this is probably the most desirable method for flexibility.

2)使用模板化的容器类实现您的排序.像

2) Implement your sort with the container class templatized. Something like

template <class Container, class Compare>
void sort(Container cont, Compare comp);

应该可以解决问题.

这篇关于特殊的排序算法和通用签名的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！