2

私はビッグデータに取り組んでおり、C++ でプログラミングしています。たとえば、[7 x 128^3 x 5 x 5] などのサイズの 4 次元配列を作成する必要があります。さまざまなプロパティの中間データ構造として、さらに多くの配列を作成する必要があります。多くの調査を行った後、最終的にデータ構造を実装するためにブーストの multi_array を選択しました。multi_array を選択した理由は 2 つあります。(1) 配列インデックスが範囲外などの例外を処理します。これは、デバッグにとって非常に重要です。(2) 高次元の配列を処理します (stl の多次元配列などの他のオプションには、3 次元以上の配列で多くの問題があります)。

問題例。

例を使って問題を説明すると簡単になります。たとえば、次の 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 を持つ 2 つの行ごとに、column_2 が並べ替えられます。

私が試したこと。

この問題は、通常の 3 次元配列で再帰的なコンパレーターを作成し、ライブラリーのソート関数 (コンパレーターを使用) を呼び出すことで解決できました。しかし、ブーストの multi_array に変更した後、問題を解決できませんでした。解決策を見つけることができなかったブーストのドキュメントをたくさん検索しました。ブースト multi_array をソートするための再帰的コンパレーターの書き方がわかりません。

質問。

multi_array をソートするための boost 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 関数は次のようになります。

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;

オブジェクトが multi_array の場合にコンパレータ関数に引数を渡す方法がわからないため、compareByID のようにコンパレータを単純に記述することはできません。

これは役に立ちますか？

sehe に返信します。

優れたソリューション。ありがとうございます。あなたはブーストと c++ の使い方が天才のようですね。それは完全に機能しました。スワップとコンパレータ機能に使用したアイデアは素晴らしいです。これらの関数呼び出し (lexicographical_compare() など) が存在することすら知りませんでした。どうもありがとう。

関連する質問が 2 つあります。

(1) たとえば、multi_array A をすべての次元で並べ替えます。同じスワップ/交換/変換を multi_array B に適用したいのですが、あなたが与えたアイデアでこれを行うことができますか?

別のカスタム ソーターを作成することで、この問題を解決できることを理解しています (スワップすると、A と B の両方でコンポーネントをスワップできます)。しかし、A をソートするために multi_array B を使用している場合、コンパレーターは multi_array B について何も知らないため、この問題をコンパレーターの概念で解決できるかどうか興味があります。この問題を解決するにはどうすればよいですか?

(2) my_comp にいくつかのオーバーロードされた関数が必要ですか? その目的のために、完全に汎用的な関数を 1 つ持つことはできませんか? (申し訳ありませんが、私は multi_array、sub_array の概念が初めてです)。

4

1 に答える 1

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、コンパレータとして再帰的に渡します。

フルライブデモ: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 ;
于 2016-03-20T21:00:40.913 に答える