56

私は、巨大な行列の操作、特にコピュラ計算のためのピラミッド型の合計を必要とするプロジェクトに取り組んでいます。

要するに、マトリックス（多次元配列）のゼロの海で比較的少数の値（通常は1の値、まれに1を超える値）を追跡する必要があります。

スパース配列を使用すると、ユーザーは少数の値を格納し、未定義のすべてのレコードをプリセット値と見なすことができます。すべての値をメモリに格納することは物理的に可能ではないため、ゼロ以外のいくつかの要素のみを格納する必要があります。これは数百万のエントリになる可能性があります。

速度は非常に優先されます。また、実行時にクラス内の変数の数を動的に選択したいと思います。

私は現在、二分探索木（b-tree）を使用してエントリを格納するシステムで作業しています。より良いシステムを知っている人はいますか？

4

11 に答える 11

29

C++ の場合、マップは適切に機能します。数百万のオブジェクトは問題になりません。私のコンピューターでは、1000 万個のアイテムに約 4.4 秒、約 57 メガかかりました。

私のテストアプリケーションは次のとおりです。

#include <stdio.h>
#include <stdlib.h>
#include <map>

class triple {
public:
    int x;
    int y;
    int z;
    bool operator<(const triple &other) const {
        if (x < other.x) return true;
        if (other.x < x) return false;
        if (y < other.y) return true;
        if (other.y < y) return false;
        return z < other.z;
    }
};

int main(int, char**)
{
    std::map<triple,int> data;
    triple point;
    int i;

    for (i = 0; i < 10000000; ++i) {
        point.x = rand();
        point.y = rand();
        point.z = rand();
        //printf("%d %d %d %d\n", i, point.x, point.y, point.z);
        data[point] = i;
    }
    return 0;
}

変数の数を動的に選択するための最も簡単な解決策は、index を string として表し、 stringをマップのキーとして使用することです。たとえば、[23][55] にあるアイテムは、"23,55" 文字列で表すことができます。このソリューションを高次元に拡張することもできます。たとえば、3 次元の場合、任意のインデックスは "34,45,56" のようになります。この手法の簡単な実装は次のとおりです。

std::map data<string,int> data;
char ix[100];

sprintf(ix, "%d,%d", x, y); // 2 vars
data[ix] = i;

sprintf(ix, "%d,%d,%d", x, y, z); // 3 vars
data[ix] = i;
于 2008-08-07T02:33:16.973 に答える
23

受け入れられた答えは、文字列を使用して多次元インデックスを表すことを推奨しています。

ただし、文字列を構築することは、これには不必要に無駄です。コンパイル時にサイズがわからない (したがってstd::tuple機能しない) 場合はstd::vector、ハッシュ マップと順序付けられたツリーの両方で、インデックスとして適切に機能します。の場合std::map、これはほとんど自明です。

#include <vector>
#include <map>

using index_type = std::vector<int>;

template <typename T>
using sparse_array = std::map<index_type, T>;

std::unordered_map（または同様のハッシュテーブルベースの辞書）の場合、特殊化されていないため、少し手間がかかりstd::vectorますstd::hash：

#include <vector>
#include <unordered_map>
#include <numeric>

using index_type = std::vector<int>;

struct index_hash {
    std::size_t operator()(index_type const& i) const noexcept {
        // Like boost::hash_combine; there might be some caveats, see
        // <https://stackoverflow.com/a/50978188/1968>
        auto const hash_combine = [](auto seed, auto x) {
            return std::hash<int>()(x) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        };
        return std::accumulate(i.begin() + 1, i.end(), i[0], hash_combine);
    }
};

template <typename T>
using sparse_array = std::unordered_map<index_type, T, index_hash>;

どちらの方法でも、使用方法は同じです。

int main() {
    using i = index_type;

    auto x = sparse_array<int>();
    x[i{1, 2, 3}] = 42;
    x[i{4, 3, 2}] = 23;

    std::cout << x[i{1, 2, 3}] + x[i{4, 3, 2}] << '\n'; // 65
}
于 2008-09-02T08:53:39.763 に答える
13

Boost には、疎行列を含む uBLAS と呼ばれる BLAS のテンプレート化された実装があります。

https://www.boost.org/doc/libs/release/libs/numeric/ublas/doc/index.htm

于 2008-08-21T23:45:29.017 に答える
4

インデックス比較の細部。それ以外の場合は、辞書式の比較を行う必要があります。

a= (1, 2, 1); b= (2, 1, 2);
(a<b) == (b<a) is true, but b!=a

編集：したがって、比較はおそらく次のようになります。

return lhs.x<rhs.x
    ? true 
    : lhs.x==rhs.x 
        ? lhs.y<rhs.y 
            ? true 
            : lhs.y==rhs.y
                ? lhs.z<rhs.z
                : false
        : false
于 2008-08-19T21:59:23.207 に答える
3

ハッシュ テーブルの挿入と検索は高速です。キーとして整数ペアのみを扱うことがわかっているため、単純なハッシュ関数を作成できます。

于 2008-08-07T03:13:15.457 に答える
1

スパース行列を実装する最善の方法は、それらを実装しないことです-少なくとも自分では実装しないでください。本当に巨大な行列を処理できるBLAS（LAPACKの一部だと思います）に提案します。

于 2008-08-08T06:11:20.107 に答える
0

[a][b][c]...[w][x][y][z] を持つ値のみが重要であるため、ほぼどこにでもある値 1 ではなく、インデックス自体のみを保存します - 常に同じ+ハッシュする方法はありません。次元の呪いが存在することに注意して、確立されたツールNISTまたはBoostを使用することを提案し、少なくともそのソースを読んで不必要な失敗を回避してください.

未知のデータ セットの時間依存分布とパラメトリック傾向を把握する必要がある場合、単一値のルートを持つマップまたは B ツリーはおそらく実用的ではありません。すべての 1 の値について、実行時の時間領域の縮小に順序付け (プレゼンテーションの感度) が従属することができる場合、ハッシュされたインデックス自体のみを格納できます。1 以外のゼロ以外の値はほとんどないため、それらの明白な候補は、すぐに見つけて理解できるデータ構造です。データセットが本当に広大な宇宙サイズである場合は、必要に応じてデータの一部をスコープに移動して、ファイル/ディスク/persistent-io を自分で管理するスライド ウィンドウのようなものをお勧めします。(理解できるコードを書く) ワーキンググループに実際の解決策を提供することを約束している場合は、

于 2009-09-27T17:52:45.867 に答える