问题标签 [sparse-array]

在 C++ 中表示稀疏张量的合适数据结构是什么？想到的第一个选项是 aboost::unordered_map因为它允许快速设置和检索 an 元素等操作，如下所示：

但是，我也希望能够对单个索引进行收缩，这将涉及对其中一个索引的求和

用 a 实现这个运算符有多容易boost::unordered_map？有没有更合适的数据结构？

我需要以某种方式在磁盘上存储一个 512^3 数组，我目前正在使用 HDF5。由于阵列稀疏，因此浪费了大量磁盘空间。

HDF5 是否提供对稀疏数组的任何支持？

我在javascript中有一个对象数组。我使用jQuery。

如何获取数组中的第一个元素？我不能使用数组索引 - 因为我在将对象添加到数组时分配了每个元素索引。所以索引不是 0、1、2 等。

只需要获取数组的第一个元素？

只是为了好玩，我想计算一个单词（来自自然语言）出现在文本中的条件概率，这取决于最后一个单词和最后一个单词。即我会拿一大堆例如英文文本并计算每个组合n(i|jk)和n(jk)出现的频率（j,k,i连续词在哪里）。

天真的方法是使用 3-D 数组 (for n(i|jk))，使用单词到 3 维位置的映射。可以使用 s 有效地完成位置查找trie（至少这是我最好的猜测），但是对于 O(1000) 个单词，我会遇到内存限制。但我猜这个数组只会被稀疏填充，大多数条目为零，因此我会浪费大量内存。所以没有3-D阵列。

哪种数据结构更适合这样的用例，并且仍然可以有效地进行很多小的更新，就像我在计算单词的出现时所做的那样？（也许有一种完全不同的方式来做到这一点？）

（当然我也需要 count n(jk)，但这很容易，因为它只是 2-D :) 我猜选择的语言是 C++。

我想预先计算一些一元函数的值数组f。

我知道我只需要f(x)wherex形式为的值a*b，其中a和b都是 range 中的整数0..N。

显而易见的时间优化选择只是制作一个大小数组，N*N并仅预先计算我稍后将要阅读的元素。对于f(a*b)，我只需检查并设置tab[a*b]. 这是可能的最快方法 - 但是，这将占用大量空间，因为该数组中有很多索引（以 开头N+1）永远不会被触及。

另一种解决方案是制作一个简单的树形图......但这会通过引入大量分支来大大减慢查找本身的速度。不。

我想知道 - 是否有任何解决方案可以使这样的数组不那么稀疏和更小，但在查找中仍然快速无分支 O(1)？

编辑

我可以听到很多关于哈希映射的评论......我将继续对一个人的行为进行基准测试（我预计由于分支而导致正常查找的性能显着下降；低于树，但仍然......让我们看看我是否是对的！）。

我想强调一下：我最喜欢一种分析解决方案，它会使用一些聪明的方法（？）来利用仅采用“类产品”索引这一事实。我觉得这个事实可能会被利用来获得比普通的通用哈希映射函数更好的结果，但我自己没有想法。

编辑

按照您的建议，我std::unordered_map从 gcc 4.5 开始尝试。这比简单的数组查找要慢一点，但确实比基于树的查找要快得多std::map——最终我对这个解决方案感到满意。我现在明白为什么不能按照我最初的意图去做了；感谢您的解释！

我只是不确定哈希映射是否真的节省了任何内存！:) 正如@Keith Randall 所描述的，我无法使内存占用低于N*N/4，而@Sjoerd 描述的三角矩阵方法给了我N*N/2。我认为N*N/2如果元素大小很小（取决于容器开销），哈希映射完全有可能使用更多空间 - 这将使最快的方法也是最有效的内存！我会试着检查一下。

我希望我能接受2个答案...

我正在寻找一个专门的（和快速的）Int32/UInt32 排序映射（最好比 System.Collections.Generic.SortedDictionary 更快，其中 K 是 Int32 或 UInt32）。

它将被用作稀疏数组，.NET 是否有任何实现？

任何人都可以建议一种快速、有效的方法来存储和访问稀疏八叉树吗？

最好是可以在 HLSL 中轻松实现的东西。（我正在使用光线投射/体素应用程序）

在这种情况下，可以预先计算树，所以我主要关心大小和搜索时间。

更新

对于任何想要这样做的人，更有效的解决方案可能是将节点存储为使用 Z 阶曲线/莫顿树生成的线性八叉树。这样做消除了内部节点的存储，但可能需要使用第二个“数据纹理”交叉引用线性树阵列，其中包含有关单个体素的信息。

我正在尝试加载我之前保存的稀疏数组。保存稀疏数组很容易。尝试阅读它虽然是一种痛苦。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 的建议，甚至有人提到了实现链表。我认为我不需要实现链表，因为我不经常添加或删除元素。

如果我创建一个 NSMutableArray 最多可能有 2^16 个元素，但大部分都是空的，我会浪费空间还是将 NSMutableArray 实现为稀疏数组？