Сортировка multi_array в Boost с использованием функции сортировки и рекурсивного компаратора
Я работаю с большими данными и программ на C++. Например, мне нужно создать 4-мерные массивы размером [7 x 128^3 x 5 x 5] и т. Д. Мне нужно будет создать еще много массивов в качестве промежуточных структур данных для различных свойств. После долгих исследований я, наконец, выбрал метод multi_array boost для реализации своих структур данных. Я выбрал multi_array по двум причинам: (1) он обрабатывает исключения, такие как индекс массива вне границ, что очень важно для отладки. (2) Он обрабатывает массивы более высоких измерений (другие опции, такие как многомерные массивы stl, имеют много проблем с массивами 3 и более измерений)
Пример проблемы.
Это становится легко, если я объясню проблему на примере. Скажем, у меня есть следующий трехмерный массив.
[(1,2,3), (4,5,6), (7,8,9)]
[(1,2,3), (1,3,3), (4,1,1)]
[(8,9,9), (6,9,7), (17,2,3)]
[(1,2,3), (1,3,2), (2,8,1)]
[(1,2,3), (1,3,3), (4,2,1)]
Я хочу отсортировать эти строки таким образом, чтобы сортировка происходила на основе column_1, затем column_2, а затем column_3. После сортировки у меня будет
[(1,2,3), (1,3,2), (2,8,1)]
[(1,2,3), (1,3,3), (4,1,1)]
[(1,2,3), (1,3,3), (4,2,1)]
[(1,2,3), (4,5,6), (7,8,9)]
[(8,9,9), (6,9,7), (17,2,3)]
Вы видите, что column_1 отсортировано. Для каждых двух строк, имеющих одинаковый column_1, затем сортируется column_2 и так далее.
Что я пробовал
Я смог решить эту проблему с помощью обычного трехмерного массива и написания рекурсивного компаратора и вызова функции сортировки библиотеки (которая использует компаратор). Но после того, как я переключился на boost multi_array, я не смог решить проблему. Я много искал для повышения документации, я не мог найти никакого решения. Я не знаю, как написать рекурсивный компаратор для сортировки наддува multi_array.
Вопрос.
Может кто-нибудь дать мне точный рабочий синтаксис рекурсивного компаратора для boost multi_array для сортировки multi_array? Код не должен использовать API, которые зависят от конкретного компилятора / операционной системы. Предположим, что размеры multi_array A равны n1 x n2 x ... x nd.
Благодарю.
Ответить Якку.
рекурсивный компаратор выглядит так:
struct comparebyID
{
bool operator()(celltuple const &t, celltuple const &u)
{
return comparator(0, t, u);
}
bool comparator(int i, celltuple const &t, celltuple const &u)
{
if (i == (levels - 1))
return t.childIDs[i] < u.childIDs[i];
if (t.childIDs[i] == u.childIDs[i])
return comparator(i + 1, t, u);
else
return t.childIDs[i] < u.childIDs[i];
}
};
Функция сортировки, которая использует рекурсивный компаратор, выглядит следующим образом:
sort(cellset, cellset + count, comparebyID());
многомерный массив выглядит так:
struct celltuple
{
cell c[MAX_SIZE];
unsigned long long IDs[MAX_IDS];
int childIDs[MAX_IDS];
int prevChildIDs[MAX_IDS];
unsigned long long prevIDs[MAX_IDS];
}cellset[MAX_CELLTUPLES];
Я не включил много других деталей того, что представляет каждый параметр, потому что он становится беспорядочным (поскольку он пытается сделать много других вещей), но основная идея - как объяснено в примере.
Я хочу написать рекурсивный компаратор для multi_array, как определено ниже.
boost::multi_array<int, 3> cell_tuple;
Я не могу просто написать компаратор, например, CompareByID, поскольку я не умею передавать аргументы в функцию компаратора, когда объект является multi_array.
Это помогает?
Ответить сехе.
Отличное решение. Благодаря тонну. Кажется, вы гений в использовании boost и C++. Это полностью сработало. Идея, которую вы использовали для функций свопинга и компаратора, удивительна. Я понятия не имел, что эти вызовы функций (такие как lexicographic_compare() и т. Д.) Вообще существуют. Огромное спасибо.
У меня есть два связанных вопроса:
(1) Скажем, мы сортируем multi_array A для всех измерений. Мы хотим применить идентичные операции замены / обмена / преобразования к multi_array B. Можем ли мы сделать это с идеей, которую вы дали?
Я понимаю, что мы можем решить эту проблему, написав отдельный пользовательский сортировщик (когда мы меняем местами, мы можем поменять местами компоненты как в A, так и в B). Но мне любопытно, можно ли решить эту проблему с помощью концепции компаратора, потому что компаратор ничего не знает о multi_array B, когда мы используем его для сортировки A. Как решить эту проблему?
(2) Действительно ли необходимо, чтобы в my_comp было несколько перегруженных функций? Разве у нас не может быть одной полностью универсальной функции для этой цели? (Извините, я новичок в понятиях multi_array, sub_array).
1 ответ
Вам нужен не только компаратор, но и другие концепции, необходимые для std::sort работать так же. В частности:
RandomItдолжны соответствовать требованиямValueSwappableа такжеRandomAccessIterator,
Поэтому я взломал общий swap реализация. Обратите внимание, что он использует детали реализации:
namespace boost { namespace detail { namespace multi_array {
template <typename T, size_t dims>
static void swap(sub_array<T, dims> a, sub_array<T, dims> b) {
using std::swap;
for (auto ai = a.begin(), bi = b.begin(); ai != a.end() && bi != b.end(); ++ai, ++bi) {
swap(*ai, *bi);
}
}
} } }
Компаратор может быть таким же простым и выглядит так:
struct my_comp {
template <typename T, size_t dims>
bool operator()(sub_array<T, dims> const& a, sub_array<T, dims> const& b) const {
return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
}
// ... some technical overloads omitted
template <typename T>
bool operator()(T a, T b) const {
return std::less<T>()(a,b);
}
};
Во всех случаях мы просто обращаемся к стандартному библиотечному алгоритму, чтобы выполнить работу, рекурсивно передавая *this как компаратор!
Full Live Demo: Live On Coliru
#include <boost/multi_array.hpp>
#include <iostream>
namespace ba = boost::multi_array_types;
using Arr = boost::multi_array<int, 3>;
static std::ostream& operator<<(std::ostream& os, Arr const& arr) {
for(auto const& row : arr) {
for (auto const& col : row) {
for (auto const& cell : col) os << cell << " ";
os << ";";
}
os << "\n";
}
return os;
}
struct my_comp {
// short hand only:
template <typename T, size_t dims> using sub_array = boost::detail::multi_array::sub_array<T, dims>;
template <typename T, size_t dims>
bool operator()(sub_array<T, dims> const& a, sub_array<T, dims> const& b) const {
return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
}
template <typename T, size_t dims>
bool operator()(boost::multi_array<T, dims> const& a, sub_array<T, dims> const& b) const {
return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
}
template <typename T, size_t dims>
bool operator()(sub_array<T, dims> const& a, boost::multi_array<T, dims> const& b) const {
return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
}
template <typename T>
bool operator()(T a, T b) const {
return std::less<T>()(a,b);
}
};
namespace boost { namespace detail { namespace multi_array {
template <typename T, size_t dims>
static void swap(sub_array<T, dims> a, sub_array<T, dims> b) {
using std::swap;
for (auto ai = a.begin(), bi = b.begin(); ai != a.end() && bi != b.end(); ++ai, ++bi) {
swap(*ai, *bi);
}
}
} } }
using boost::detail::multi_array::swap;
#include <boost/range/algorithm.hpp>
int main() {
Arr arr(boost::extents[5][3][3]);
auto initial = {
1,2,3, 4,5,6, 7,8,9,
1,2,3, 1,3,3, 4,1,1,
8,9,9, 6,9,7, 17,2,3,
1,2,3, 1,3,2, 2,8,1,
1,2,3, 1,3,3, 4,2,1,
};
boost::copy(initial, arr.origin());
std::cout << arr;
std::sort(arr.begin(), arr.end(), my_comp{});
std::cout << "After sort\n" << arr;
}
Печать:
1 2 3 ;4 5 6 ;7 8 9 ;
1 2 3 ;1 3 3 ;4 1 1 ;
8 9 9 ;6 9 7 ;17 2 3 ;
1 2 3 ;1 3 2 ;2 8 1 ;
1 2 3 ;1 3 3 ;4 2 1 ;
After sort
1 2 3 ;1 3 2 ;2 8 1 ;
1 2 3 ;1 3 3 ;4 1 1 ;
1 2 3 ;1 3 3 ;4 2 1 ;
1 2 3 ;4 5 6 ;7 8 9 ;
8 9 9 ;6 9 7 ;17 2 3 ;