Java中是否有任何用于稀疏位向量的知名库？
（是否有关于稀疏使用它们与java.util.BitSet的有用性的指南？）
问问题
5760 次
7 回答
9
TL;DR go here用 Java 实现高效稀疏位集
我知道这是一个“老”问题，但是我偶然发现了同样的问题。虽然答案很好，但我最终并不满意。在进一步挖掘之后，我想我已经遇到了对 Java 中稀疏 BitSets 问题的“明确”答案。
在本演讲中，作者 Bruce Haddon 博士讨论了他的研究人员为创建标准 Java BitSet 的高效内存和高性能替代品所做的努力。
他的演示文稿的原始链接已失效，但我联系了 Haddon 博士并在此处保留了代码和演示文稿：
https://github.com/brettwooldridge/SparseBitSet
我不建议您更高度地阅读此演示文稿。即使您对稀疏位集不感兴趣，这也是一本引人入胜的读物，它更多地是关于解决问题的真正本质……
于 2011-12-01T02:36:22.627 回答
5
如果它真的很稀疏（例如，小于 1% 的加载），那么使用按位索引索引的哈希表可能会很好；仅表中是否存在索引，您就需要知道该位分别是 1 还是 0。
如果密度超过百分之几，您可以使用按位索引除以 64 索引的哈希表，并将长字存储在包含实际位的哈希表中。如果哈希表包含int(N/64)的值V并且(V>>(N mod 64))&1为真，则设置位N。
这两个答案都假设您要优化对位的随机访问。如果您想按索引优化对位的顺序（或其他访问），那么您可能需要一个稀疏矩阵结构，根据预期密度使用相同类型的低级位向量表示。见稀疏矩阵
于 2010-06-14T21:10:45.710 回答
3
colt 库具有稀疏矩阵（1D、2D 和 3D）。它还有一个高效的 BitVector，每个值 1 位，而不是 8 位boolean[]。
但是，稀疏矩阵不直接支持位 - 仅支持双精度和对象。您可以通过将位索引映射到长索引来包装一维稀疏双精度矩阵，(bitIndex>>6)因为每个长索引都包含 64 位，将检索到的双精度转换为原始长值，并使用位操作来访问检索到的长的位。一点工作，但远不及自己实现稀疏向量。一旦您的包装器工作，您可能会避免将双精度数转换为长整数，并使用双一维稀疏矩阵的可用 Colt 源代码作为起点来实现一个真正的稀疏长一维矩阵。
编辑：更多信息。Colt 向量/矩阵最初不需要内存来存储，假设所有位（长整数）最初都是 0。将值设置为非零会消耗内存。将值设置回 0 会继续消耗内存，尽管会定期回收零值的内存。
如果位是真正稀疏的，使得每个后备长值仅设置一个位，那么存储开销将非常低，每个实际存储位需要 64 位。但是正如您提到的典型情况是 20-40% 稀疏，那么开销会低得多，如果位聚集在范围内，例如位从 0-100、1000-1100 和 2000-2200 （十六进制值。）总体而言，只有 1/16 的区域分配给位，但聚类意味着位的存储不会浪费空间。
于 2010-06-14T21:04:22.250 回答
1
你可以试试FastUtil 的 AVL Tree Map。
于 2010-06-14T21:13:10.523 回答
0
CERN COLT 广泛用于向量和矩阵计算，具有稀疏矩阵，但并非专门用于位向量。
http://acs.lbl.gov/software/colt/api/cern/colt/matrix/impl/SparseObjectMatrix1D.html
于 2010-06-14T20:59:41.090 回答
0
一个哈希表，其中仅存在或不存在密钥就可以告诉您一些事情？那将是一个哈希集！我对 BitSet 上的一组（甚至是散列）的性能持怀疑态度。这实际上取决于速度或内存是主要驱动因素。
于 2010-06-14T21:21:58.733 回答
0
于 2013-09-16T14:41:36.837 回答