2

我有一个位数组，在某些部分可能非常密集，而在其他部分非常稀疏。该数组可以达到 2**32 位。我将它变成一堆包含偏移量和长度的元组，以使其在内存中处理更有效。但是，有时这对于 10101010100011 之类的东西效率较低。关于将其存储在内存中的好方法有什么想法吗？

4

5 回答 5

2

如果我理解正确，您使用元组(offset, length)来表示 1 位的运行？如果是这样，更好的方法是使用打包位域的运行。对于密集区域，您会得到一个非常有效的数组，而在非密集区域，您会得到隐含的零。例如，在 C++ 中，表示可能如下所示：

// The map key is the offset; the vector's length gives you the length
std::map<unsigned int, std::vector<uint32_t> >

查找将包括在所讨论的位位置之前找到密钥，并查看该位是否落在其向量中。如果是，请使用向量中的值。否则，返回 0。例如：

typedef std::map<unsigned int, std::vector<uint32_t> > bitmap; // for convenience
typedef std::vector<uint32_t> bitfield; // also convenience

bool get_bit(const bitmap &bm, unsigned int idx) {
  unsigned int offset = idx / 32;
  bitmap::const_iterator it = bm.upper_bound(offset);

  // bm is the element /after/ the one we want
  if (it == bm.begin()) {
    // but it's the first, so we don't have the target element
    return false;
  }

  it--;

  // make offset be relative to this element start
  offset -= it.first;
  // does our bit fall within this element?
  if (offset >= it.second.size())
    return false; // nope

  unsigned long bf = it.second[offset];
  // extract the bit of interest
  return (bf & (1 << (offset % 32))) != 0;
}
于 2009-08-10T02:01:41.850 回答
1

这将有助于了解更多。“非常稀疏/密集”是指数百万个连续的 0/1，还是指 0 非常接近 0 或 1 的局部（如何局部？）比例？一个或另一个价值占主导地位吗？是否有任何模式可以使游程编码有效？你将如何使用这个数据结构？（随机访问？访问索引的分布是什么样的？大块永远不会或很少访问？）

我只能猜测您不会以每秒数十亿位的速率随机访问和修改所有 40 亿位。除非它在局部级别上非常稀疏/密集（例如任何一百万个连续位可能是相同的，除了 5 或 10 位）或充满大规模重复或模式，我的直觉是数据结构的选择取决于更多关于如何使用数组而不是数据的性质。

于 2009-08-10T02:08:28.300 回答
0

如何构建事物将取决于您的数据是什么。为了尝试表示大量数据，您需要长时间运行零或一。这将消除重新呈现它的需要。如果不是这种情况，并且您的 1 和 0 的数量大致相同，那么使用所有内存会更好。

将其视为压缩问题可能会有所帮助。为了使压缩有效，必须有一种模式（或在整个空间中使用的一组限制项目）和不均匀的分布才能使压缩起作用。如果所有元素都使用并均匀分布，则很难进行压缩，或者可能会占用比实际数据更多的空间。

如果只有零和一的运行（不止一个），使用偏移量和长度可能会有意义。如果运行不一致，您可以将位复制为具有偏移量、长度和值的位数组。

如果您有大量的 1 或 0，上述方法的效率将取决于您。您需要小心确保您没有使用更多内存来表示您的内存，而只是使用内存本身（即您正在使用更多内存来表示内存，然后只是将其放入内存中）。

于 2009-08-10T03:27:47.313 回答
0

查看野牛源代码。看看 biset 的实现。它提供了多种实现方式来处理具有不同密度的位数组。

于 2009-08-10T04:14:21.463 回答
0

您打算一次记住其中多少个？

据我所知，2**32 位 = 512M，只有半个演出，现在这不是很多内存。你有什么更好的关系吗？

假设您的服务器有足够的内存，在启动时将其全部分配，然后将其保存在内存中，网络处理线程可以在恒定时间内仅在几条指令中执行——它应该能够跟上任何工作负载。

于 2009-08-10T20:00:12.463 回答