問題タブ [sparse-array]

C++ でスパース tesnor を表す適切なデータ構造は何ですか? 頭に浮かぶ最初のオプションは a ですboost::unordered_map。これにより、次のような an 要素の高速な設定や取得などの操作が可能になります。

ただし、単一のインデックスに対して短縮を実行できるようにしたいと考えています。これには、インデックスの 1 つに対する合計が含まれます。

この演算子を で実装するのはどれくらい簡単でしょうboost::unordered_mapか? より適切なデータ構造はありますか?

何らかの方法で 512^3 配列をディスクに格納する必要があり、現在 HDF5 を使用しています。配列がまばらであるため、多くのディスク領域が無駄になります。

HDF5 はスパース配列をサポートしていますか?

javascriptにオブジェクトの配列があります。私はjqueryを使用しています。

配列の最初の要素を取得するにはどうすればよいですか？オブジェクトを配列に追加するときに各要素にインデックスを割り当てるため、配列インデックスを使用できません。したがって、インデックスは0、1、2などになります。

配列の最初の要素を取得する必要がありますか？

楽しみのために、最後の単語と最後の単語の次の単語に応じて、（自然言語からの）単語がテキストに表示される条件付き確率を数えたいと思います。つまり、たとえば英語のテキストを大量に取得し、各組み合わせが出現する頻度を数えn(i|jk)ますn(jk)（j,k,i連続する単語はどこにありますか）。

n(i|jk)素朴なアプローチは、3次元での位置への単語のマッピングを使用して、（の）3D配列を使用することです。位置検索はsを使用して効率的に実行できますがtrie（少なくともそれが私の最善の推測です）、すでにO（1000）ワードの場合、メモリの制約に遭遇します。しかし、この配列はまばらにしか埋められず、ほとんどのエントリはゼロであるため、大量のメモリを浪費すると思います。したがって、3D配列はありません。

どのようなデータ構造がそのようなユースケースに適していて、単語の出現を数えるときに行うように、多くの小さな更新を効率的に行うことができますか？（多分これを行うための完全に異なる方法がありますか？）

（もちろん、私も数える必要がありますn(jk)が、それは2Dしかないので、簡単です:)選択する言語はC++だと思います。

単項関数の値の配列を事前に計算したいと思いますf。

f(x)wherexは の形式の値のみが必要であることはわかっています。ここで、とはa*b両方ともrange 内の整数です。ab0..N

明らかな時間最適化の選択は、サイズの配列を作成し、N*N後で読み取る要素だけを事前に計算することです。についてf(a*b)は、チェックして設定するだけtab[a*b]です。これは可能な限り最速の方法ですが、この配列には ( で始まるN+1) 決して触れない多数のインデックスがあるため、これは多くのスペースを必要とします。

もう 1 つの解決策は、単純なツリー マップを作成することです。しかし、これは多くの分岐を導入することで、ルックアップ自体を非常に遅くします。いいえ。

私は疑問に思います-そのような配列をスパースでなく小さくする解決策はありますか?

編集

ハッシュマップについて多くのコメントを聞くことができます...どのように動作するかのベンチマークに進みます(分岐により、通常のルックアップよりも大幅なパフォーマンス低下が予想されます;ツリーよりも少ないですが、それでも...そうです！） .

強調したいのは、「製品のような」インデックスのみが取得されるという事実を利用するために、何らかの巧妙な方法 (?) を使用する分析ソリューションを最も高く評価することです。この事実を悪用して、平均的な一般的なハッシュ マップ関数よりも優れた結果が得られる可能性があると思いますが、私自身はアイデアがありません。

編集

std::unordered_mapあなたのアドバイスに従って、 gcc 4.5から試しました。これは、単純な配列ルックアップよりも少し遅くなりましたが、実際にはツリーベースよりもはるかに高速std::mapでした.最終的には、このソリューションで問題ありません. 当初意図していたことができない理由がわかりました。説明をありがとう！

ハッシュマップが実際にメモリを節約するかどうかはわかりません! :) @Keith Randall が説明したように、メモリ フットプリントを よりも低くすることはできず、N*N/4@Sjoerd によって説明された三角行列アプローチではN*N/2. N*N/2要素のサイズが小さい場合 (コンテナーのオーバーヘッドによって異なります) 、ハッシュ マップがスペース以上のものを使用する可能性は十分にあると思います。それを確認してみます。

2つの答えを受け入れることができればいいのに...

スパースオクツリーを格納およびアクセスするための高速で効率的な方法を提案できる人はいますか?

HLSL で簡単に実装できるものが望ましいです。(レイキャスティング/ボクセル アプリを使用しています)

この例では、ツリーを事前に計算できるので、サイズと検索時間に主に関心があります。

アップデート

これを行おうとしている人にとって、より効率的な解決策は、Z 次曲線/モートン ツリーで生成された線形 octree としてノードを格納することです。そうすることで、内部ノードの格納が不要になりますが、線形ツリー配列と、個々のボクセルに関する情報を含む 2 番目の「データ テクスチャ」との相互参照が必要になる場合があります。

以前に保存したスパース配列を読み込もうとしています。スパース配列の保存は簡単でした。それを読もうとするのは苦痛ですが。scipy.loadは、スパース配列の周りに0d配列を返します。

スパース行列を取得するには、0d配列をフラット化するか、sp.asarray（A）を使用する必要があります。これは物事を行うのに本当に難しい方法のようです。Scipyは、スパース配列をロードしたことを理解するのに十分賢いですか？スパース配列をロードするためのより良い方法はありますか？

次の状況があります。

両方の配列のすべての要素がオブジェクトです。

小さな配列には、大きな配列に関連する情報が含まれていますが、 のすべての要素がlarge関連する要素を必要とするわけではないsmallので、 に設定しnullます。ただし、次のようなことができるように、インデックスを同じに保つ必要がありますlarge[16].id + ': ' + small[16].description。ほとんどが値の配列を持っているという事実は、nullメモリ使用量の増加につながりますか?

私の質問は、のようなことをしたりsmall = [a2,b2,c2,i2]、プロパティにインデックスを設定したりする方が良いかどうかa2.index = 0; b2.index = 1です。

また、代わりに undefined を使用するという提案に出くわし、誰かがリンクされたリストの実装について言及したことさえありました。要素を頻繁に追加または削除するわけではないので、リンクされたリストを実装する必要はないと思います。

最大 2^16 の要素を持つ可能性のある NSMutableArray を作成するが、ほとんどが空になる場合、スペースを浪費することになりますか、それとも NSMutableArray はスパース配列として実装されますか?