2

現在、1 x H のサイズのセル C を使用しています。ここで、H は非常に大きな数です。このセルは主に、O(1) 時間で非常にまばらなインデックスにいくつかの値をすばやく格納してインクリメントするために使用されます。例えば、

H = 10000000;
C = cell(1, H);
...
for i = 1:last

    % all values of someIndex(i) are values from 1 to H, unsorted, and contains repeating values.

    C{ someIndex(i) } = C{ someIndex(i) } + someValues(i);

end
...

セル C の小さなインデックスのみが使用されます。ほとんどの場合、全体の約 1 ～ 10% です。最初は、実装は小さなサイズのデータ​​ベースで問題ありませんが、H がほぼ指数関数的に成長する大きなデータベースを使用する予定です。したがって、この素朴な実装は機能しなくなります。

また、セルを使用する代わりに、配列を使用して各インデックスと値を次のように格納することも考えていました。

新しいインデックスを検出したとします。

IndexArray(size(IndexArray, 2) + 1) = someIndex(i);
ValueArray(size(ValueArray, 2) + 1) = someValue(i);

古いインデックスを検出したとします: (確かに、IndexArray 全体をスイープして、そのような古いインデックスが存在するかどうかを確認する必要があります)

ValueArray( detectOldIndex(i) ) = ValueArray( detectOldIndex(i) ) + someValue(i);

ただし、これにも問題があります。インデックスが大きくなるにつれて、IndexArray 全体をスイープするには、より多くの時間がかかります。これがO(N)です。

もちろん、このような場合は間違いなく Tree を使用したいと考えていますが、Matlab には有効な Tree 構造がありません。ネストされたセルでネストされたセルを使用することを考えることができました。しかし、実装は非常に醜い可能性があります。

では、Matlab でこのようなことを行う場合、より速い選択肢は何ですか?

4

2 に答える 2

1

あなたが本当に大きくなりたいのなら、それはデータベースを使う価値があるかもしれません。完全なデータをメモリに保持する必要がないという追加のボーナスがあります。

mksqliteまたはmymとmysqlは簡単に使用できます。

于 2013-01-11T11:17:26.580 に答える
1

の使用を検討しましたMap containerか?

はMap container基本的にハッシュ テーブルです。したがって、「アクティブな」インデックスの小さなセットを巨大なドメインにマッピングするのはかなり効率的です。

于 2013-01-11T09:48:34.990 に答える