使用std::sort()按元素块进行排序

Question

使用std::sort()按元素块进行排序

9

我有一个边缘数组，它被定义为一个C风格的双精度浮点数数组，其中每4个双精度浮点数定义一条边缘，如下所示：

double *p = ...;
printf("edge1: %lf %lf %lf %lf\n", p[0], p[1], p[2], p[3]);
printf("edge2: %lf %lf %lf %lf\n", p[4], p[5], p[6], p[7]);

我想使用std::sort()按边长对其进行排序。如果它是一个struct Edge { double x1, y1, x2, y2; }; Edge *p;，那么我就可以开始了。

但在这种情况下，双精度数组具有指针类型未表示的块大小。 qsort()允许您明确指定块大小，但std::sort()通过指针类型推断块大小。

出于性能原因（内存使用和CPU都是如此），假设创建新数组或以某种方式转换数组是不可取的。再次出于性能原因，我们确实希望使用std::sort()而不是qsort()。

有没有可能调用std::sort()而不浪费任何CPU周期来转换数据？

可能的方法：

一个明显的方法是尝试强制转换指针：

double *p = ...;
struct Edge { double arr[4]; };
Edge *p2 = reinterpret_cast<Edge*>(p);
std::sort(...);

但是，我怎么确保数据对齐正确呢？另外，我怎么保证在所有平台和架构上都正确对齐呢？

还是我可以使用typedef double[4] Edge;吗？

- Alexandru

据经验推测，可能是因为它可以内联比较。然而，值得先对您的应用程序进行分析以确定排序是否值得优化——qsort的效果不错。 - Will

拥有全局变量L并不影响线程安全。事实上，正如您所看到的，qsort接收该参数，但在内部进行了复制。另外，std::sort仅在某些情况下更快，但肯定不适用于普通的C数组。 - Diego Sevilla

2

由于出现了大量错误答案，因此添加了关于“qsort”的说明。 - Kirill V. Lyadvinsky

我想只使用 O(1) 的额外内存。 - Alexandru

@Alexandru 我也有同样的问题，所以我重写了这个问题（希望现在更好了），并添加了赏金。 - sashoalm

显示剩余7条评论

10个回答

2

您可以使用“步长迭代器”来实现这一点。 “步长迭代器”包装另一个迭代器和一个整数步长大小。下面是一个简单的草图：

template<typename Iter>
class stride_iterator
{
    ...

    stride_iterator(Iter it, difference_type step = difference_type(1))
    : it_(it), step_(step) {}

    stride_iterator& operator++() {
        std::advance(it_,step_);
        return *this;
    }

    Iter base() const { return it_; }

    difference_type step() const { return step_; }

    ...

private:
    Iter it_;
    difference_type step_;
};

此外，像这样的辅助函数

template<typename Iter>
stride_iterator<Iter> make_stride_iter(
    Iter it,
    typename iterator_traits<Iter>::difference_type step)
{
    return stride_iterator<Iter>(it,step);
}

template<typename Iter>
stride_iterator<Iter> make_stride_iter(
    stride_iterator<Iter> it,
    typename iterator_traits<Iter>::difference_type step)
{
    return stride_iterator<Iter>(it.base(),it.step() * step);
}

应该能够相当容易地使用步长迭代器：

int array[N*L];
std::sort( make_stride_iter(array,L),
           make_stride_iter(array,L)+N );

将英文翻译成中文：

自己实现迭代器适配器（包括所有运算符）可能不是一个好主意。正如Matthieu所指出的，如果你使用Boost的迭代器适配器工具，可以节省大量的打字时间。

编辑： 我刚刚意识到这并不能做到你想要的，因为std::sort只会交换每个块的第一个元素。我认为这没有一个简单和可移植的解决方案。我看到的问题是，在使用std::sort时，无法（轻松地）自定义“元素”（即块）的交换方式。您可能编写迭代器，返回一个带有特殊交换函数的特殊引用类型，但我不确定C++标准是否保证std::sort将使用通过ADL查找的交换函数。你的实现可能限制它只能使用std::swap。

我想最好的答案仍然是：“只需使用qsort”。

- sellibitze

&&不是C++0x的东西吗？看起来是个不错的解决方案，我会去查一下。 - Alexandru

“&& 不是 C++0x 的东西吗？” - 没错，我的错误。我改了它。 - sellibitze

哎呀，那是代码膨胀。boost::iterator_adaptor: http://www.boost.org/doc/libs/1_40_0/libs/iterator/doc/iterator_adaptor.html - Matthieu M.

是的，使用一些迭代器适配器库似乎是个好主意。就此而言，我认为步进迭代器应该成为std::或至少boost::的一部分。 ;) - sellibitze

2

如何使用重新排序向量？您可以用1..N/L来初始化向量，将std::sort传递一个比较器，比较元素i1*L..i1*L+L和i2*L..i2*L+L，当您的向量被正确排序后，根据新顺序重新排序C数组。

回复评论：是的，事情会变得复杂，但也许这正是需要的！看一下这里。

- user3458

如果你不使用额外的数组（我不会），事情会变得复杂起来。 - Alexandru

1

它不是任何 ANSI、ISO 或 POSIX 标准的一部分，但某些系统提供了 qsort_r() 函数，该函数允许您将额外的上下文参数传递给比较函数。然后，您可以像这样执行：

int comp(void *thunk, const void *a, const void *b)
{
    int L = (int)thunk;
    // compare a and b as you would normally with a qsort comparison function
}

qsort_r(array, N, sizeof(int) * L, (void *)L, comp);

或者，如果您没有qsort_r，您可以使用{{link1：callback(3)}}包从ffcall库中创建运行时闭包。例如：

#include <callback.h>
void comp_base(void *data, va_alist alist)
{
    va_start_int(alist);  // return type will be int

    int L = (int)data;
    const void *a = va_arg_ptr(alist, const void*);
    const void *b = va_arg_ptr(alist, const void*);

    // Now that we know L, compare
    int return_value = comp(a, b, L);

    va_return_int(alist, return_value);  // return return_value
}

...    

// In a function somewhere
typedef int (*compare_func)(const void*, const void*);

// Create some closures with different L values
compare_func comp1 = (compare_func)alloc_callback(&comp_base, (void *)L1);
compare_func comp2 = (compare_func)alloc_callback(&comp_base, (void *)L2);
...
// Use comp1 & comp2, e.g. as parameters to qsort
...
free_callback(comp1);
free_callback(comp2);

请注意，callback库是线程安全的，因为所有参数都通过堆栈或寄存器传递。该库负责分配内存，确保内存可执行，并在必要时刷新指令缓存，以允许在运行时执行动态生成的代码（即闭包）。它据说可以在各种系统上工作，但也很可能由于错误或缺乏实现而无法在您的系统上工作。

还要注意，这会给函数调用增加一点开销。上面每次调用comp_base()都必须从传递的列表中解包其参数（这是高度依赖平台的格式），并将其返回值塞回去。大多数情况下，这种开销微不足道，但对于一个比较函数来说，实际执行的工作非常小，在调用qsort()期间将被调用多次，这种开销非常显著。

- Adam Rosenfield

1

我不太记得怎么做了，但如果你能伪造匿名函数，那么你可以创建一个返回长度为L的数组版本的comp(L)函数...这样L就成为一个参数而不是全局变量，你就可以使用qsort。正如其他人提到的，除非你的数组已经排序，或者反向排序之类的情况，否则qsort几乎和任何其他算法一样快。（毕竟它被称为快速排序的原因...）

- Brian Postow

0

std::array< std::array<int, L>, N > array;
// or std::vector< std::vector<int> > if N*L is not a constant
std::sort( array.begin(), array.end() );

- Kirill V. Lyadvinsky

4

请使用 qsort，使用 std::sort 并不能更快。 - Kirill V. Lyadvinsky

0

namespace
{
    struct NewCompare
    {
        bool operator()( const int a, const int b ) const
        {
            return a < b;
        }

    };
}

std::sort(array+start,array+start+L,NewCompare);

使用 std::stable_sort() 在真实数据集上进行测试 - 对于某些数据混合，它的速度会更快！

在许多编译器（如GCC）中存在一个令人讨厌的问题：std::sort() 模板通过测试比较器两次（一次反转），以确保结果被反转！这将在普通构建中完全破坏中等数据集的性能。解决方案类似于以下内容：

#ifdef NDEBUG
  #define WAS_NDEBUG
  #undef NDEBUG
#endif
#define NDEBUG
#include <algorithm>
#ifdef WAS_NDEBUG
  #undef WAS_NDEBUG
#else
  #undef NDEBUG
#endif

本文内容源自这篇优秀的博客文章：http://www.tilander.org/aurora/2007/12/comparing-stdsort-and-qsort.html

- Will

我不明白。这个程序如何处理数组的块状特性？ - Matt Joiner

0

我不确定你是否可以在不进行更多工作的情况下实现相同的结果。std::sort()是用于对由两个随机访问迭代器定义的元素序列进行排序的。不幸的是，它从迭代器中确定元素的类型。例如：

std::sort(&array[0], &array[N + L]);

将会对array的所有元素进行排序。问题在于它假设迭代器的下标、增量、减量和其他索引运算符遍历序列的元素。我认为你想要对数组的切片进行排序（我认为这就是你想要的），唯一的方法是编写一个基于L索引的迭代器。这就是sellibitze在stride_iterator答案中所做的。

- D.Shawley

0

Arkadiy 的想法是正确的。如果你创建一个指针数组并对其进行排序，就可以原地排序：

#define NN 7
#define LL 4

int array[NN*LL] = {
    3, 5, 5, 5,
    3, 6, 6, 6,
    4, 4, 4, 4,
    4, 3, 3, 3,
    2, 2, 2, 2,
    2, 0, 0, 0,
    1, 1, 1, 1
};

struct IntPtrArrayComp {
    int length;
    IntPtrArrayComp(int len) : length(len) {}
    bool operator()(int* const & a, int* const & b) {
        for (int i = 0; i < length; ++i) {
            if (a[i] < b[i]) return true;
            else if (a[i] > b[i]) return false;
        }
        return false;
    }
};

void sortArrayInPlace(int* array, int number, int length)
{
    int** ptrs = new int*[number];
    int** span = ptrs;
    for (int* a = array; a < array+number*length; a+=length) {
        *span++ = a;
    }
    std::sort(ptrs, ptrs+number, IntPtrArrayComp(length));
    int* buf = new int[number];
    for (int n = 0; n < number; ++n) {
        int offset = (ptrs[n] - array)/length;
        if (offset == n) continue;

        // swap
        int* a_n = array+n*length;
        std::move(a_n, a_n+length, buf);
        std::move(ptrs[n], ptrs[n]+length, a_n);
        std::move(buf, buf+length, ptrs[n]);

        // find what is pointing to a_n and point it 
        // to where the data was move to
        int find = 0;
        for (int i = n+1; i < number; ++i) {
            if (ptrs[i] == a_n) {
                find = i;
                break;
            }
        }
        ptrs[find] = ptrs[n];
    }
    delete[] buf;
    delete[] ptrs;
}

int main()
{
    for (int n = 0; n< NN; ++n) {
        for (int l = 0; l < LL; ++l) {
            std::cout << array[n*LL+l];
        }
        std::cout << std::endl;
    }
    std::cout << "----" << std::endl;
    sortArrayInPlace(array, NN, LL);
    for (int n = 0; n< NN; ++n) {
        for (int l = 0; l < LL; ++l) {
            std::cout << array[n*LL+l];
        }
        std::cout << std::endl;
    }
    return 0;
}

输出：

- jmucchiello

用下面这行代码替换int* buf = new int[number];变成int* buf = new int[length];Arkady的回答是正确的，不过我希望能有一个不使用第二个数组的解决方案。我将接受他的答案作为最佳解决方案，因为他提供了原始的思路。 - Alexandru

0

很多答案似乎都有些过度了。如果你真的必须按照C++的风格来做，可以使用jmucchiello的示例：

template <int Length>
struct Block
{
    int n_[Length];

    bool operator <(Block const &rhs) const
    {
        for (int i(0); i < Length; ++i)
        {
            if (n_[i] < rhs.n_[i])
                return true;
            else if (n_[i] > rhs.n_[i])
                return false;
        }
        return false;
    }
};

然后使用以下方式进行排序：

sort((Block<4> *)&array[0], (Block<4> *)&array[NN]);

它不必再复杂。

- Matt Joiner

这需要在编译时知道长度。 - CB Bailey

不难进行修改，因为我基于的示例已经证明了这一点。 - Matt Joiner

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Barry · Accepted Answer

对于新的问题，我们需要在sort()中传入一种迭代器，它不仅会让我们比较正确的内容（即每次通过我们的double[]走4步而不是1步），还会交换正确的内容（即交换4个double而不是一个）。

我们可以通过将我们的double数组重新解释为一个由4个double组成的数组来实现这两个目标。这样做：

typedef double Edge[4];

这样做是行不通的，因为你不能直接赋值一个数组，swap函数需要这样做。但是可以尝试这样：

typedef std::array<double, 4> Edge;

或者，如果不是C++11：

struct Edge {
    double vals[4];
};

满足两个要求。因此：

void sort(double* begin, double* end) {
    typedef std::array<double, 4> Edge;

    Edge* edge_begin = reinterpret_cast<Edge*>(begin);
    Edge* edge_end = reinterpret_cast<Edge*>(end);

    std::sort(edge_begin, edge_end, compare_edges);
}

bool compare_edges(const Edge& lhs, const Edge& rhs) {
    // to be implemented
}

如果您担心对齐问题，可以始终断言没有额外的填充：

static_assert(sizeof(Edge) == 4 * sizeof(double), "uh oh");