Сортировка по блокам элементов с помощью std :: sort ()

Question

У меня есть массив ребер, который определяется как массив двойных чисел в стиле 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() выводит размер блока по типу указателя.

По соображениям производительности (как для использования памяти, так и для процессора) предположим, что нежелательно создавать новые массивы или каким-либо образом преобразовывать массив. Снова из соображений производительности, скажем, мы хотим использовать std::sort() вместо qsort().

Можно ли вызвать std::sort(), не тратя один цикл ЦП на преобразование данных?

Возможный подход:

Очевидный подход - попытаться принудительно привести указатель:

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

Но как мне убедиться, что данные выровнены правильно? Кроме того, как мне убедиться, что он всегда будет правильно выровнен на всех платформах и архитектурах?

Или я могу использовать typedef double[4] Edge;?

Answer 1

Как насчет вектора переупорядочения? Вы инициализируете вектор с 1..N / L, передаете std :: sort компаратор, который сравнивает элементы i1 * L..i1 * L + L с i2 * L..i2 * L + L, и когда ваш вектор правильно отсортирован переупорядочить массив C в соответствии с новым порядком.

В ответ на комментарий: да, все усложняется, но это может быть просто хорошим осложнением! Взгляните здесь .

Answer 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 );

Реализация адаптера итератора самостоятельно (со всеми операторами), вероятно, не очень хорошая идея. Как отметил Матье, вы можете безопасно печатать на клавиатуре, если используете, например, инструменты Boost * итератор .

Edit: Я только что понял, что это не делает то, что вы хотели, так как std :: sort будет обмениваться только первым элементом каждого блока. Я не думаю, что есть простое и портативное решение для этого. Проблема, которую я вижу, состоит в том, что обмен «элементами» (вашими блоками) нельзя (легко) настроить при использовании std :: sort. Возможно, вы могли бы написать свой итератор для возврата специального ссылочного типа с помощью специальной функции подкачки, но я не уверен, гарантирует ли стандарт C ++, что std :: sort будет использовать функцию подкачки это ищется через ADL. Ваша реализация может ограничить его до std :: swap.

Полагаю, лучший ответ по-прежнему: «Просто используйте qsort».

Answer 3

Для нового вопроса нам нужно передать sort() своего рода итератор, который не только позволит нам сравнивать правильные вещи (т. Е. Будет проходить 4 шага через наш double[] каждый раз вместо 1) но также поменяйте местами нужные вещи (т.е. поменяйте местами 4 double с вместо одного).

Мы можем достичь того и другого, просто переосмыслив наш двойной массив, как если бы он был массивом из 4 двойных. Делаем это:

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");

Answer 4

Он не является частью какого-либо стандарта 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, вы можете использовать пакет 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(), накладные расходы очень значительны.

Answer 5

Я точно не помню, как это сделать, но если вы можете подделать анонимные функции, вы можете создать функцию comp (L), которая возвращает версию comp для массивов длины L ... таким образом, L параметр, а не глобальный, и вы можете использовать qsort. Как уже упоминалось, за исключением случая, когда ваш массив уже отсортирован, или в обратном направлении, или что-то в этом роде, qsort будет работать почти так же быстро, как и любой другой алгоритм. (есть причина, по которой это называется быстрой сортировкой ...)

Answer 6

Многие из этих ответов кажутся излишними. Если вам действительно нужно сделать это в стиле 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]);

Это не должно быть более сложным.

Answer 7

Аркадий имеет правильную идею. Вы можете отсортировать на месте, если вы создаете массив указателей и сортируете это:

#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;
}

Выход:

3555
3666
4444
4333
2222
2000
1111
----
1111
2000
2222
3555
3666
4333
4444

Answer 8

Я не уверен, что вы сможете достичь того же результата без лишней работы. std::sort() сделано для сортировки последовательностей элементов, определенных двумя итераторами произвольного доступа. К сожалению, он определяет тип элемента от итератора. Например:

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

отсортирует все элементы array. Проблема заключается в том, что предполагается, что подписывающий, инкрементный, декрементный и другие индексирующие операторы итератора перешагивают через элементы последовательности. Я считаю, что единственный способ, которым вы можете сортировать фрагменты массива (я думаю, что это то, что вам нужно), это написать итератор, который индексирует на основе L. Это то, что Sellibitze сделал в ответе stride_iterator .

Answer 9

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 iirc) есть неприятный укус: шаблон 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

Answer 10

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() );