如何在一次通过它的过程中估算数组中不同值的计数

问题描述 投票：14回答：5

我有几个巨大的数组（数百万++成员）。所有这些都是数字数组，它们没有排序（我不能这样做）。有些是uint8_t，有些是uint16_t/32/64。我想估计这些数组中不同值的计数。条件如下：

  1. 速度非常重要，我需要在一次通过数组时执行此操作，我必须按顺序执行它（不能来回跳转）（我在C ++中这样做，如果这很重要）
  2. 我不需要精确计数。我想知道的是，如果它是一个uint32_t数组，如果有10或20个不同的数字，或者有数千或数百万。
  3. 我可以使用相当多的内存，但使用的越少越好
  4. 数组数据类型越小，我需要越准确
  5. 我不介意STL，但如果我能做到没有它那将是伟大的（虽然没有BOOST，对不起）
  6. 如果方法可以很容易地并行化，那将很酷（但它不是强制条件）

完美输出的例子：

ArrayA [uint32_t, 3M members]: ~128 distinct values
ArrayB [uint32_t, 9M members]: 100000+ distinct values
ArrayC [uint8_t, 50K members]: 2-5 distinct values
ArrayD [uint8_t, 700K members]: 64+ distinct values

我知道有些限制可能看起来不合逻辑，但就是这样。作为旁注，我也想要最常用的X（3或10）和最少使用的值，但这样做要容易得多，我可以自己做。但是，如果有人也有这样的想法，请随时分享！

编辑：关于STL的一些澄清。如果您有使用它的解决方案，请发布它。不使用STL对我们来说只是一个奖励，我们不太喜欢它。但是，如果它是一个很好的解决方案，它将被使用！

c++ arrays algorithm search
5个回答
7
投票

对于8位和16位值，您只需创建每个值的计数表;每次写入之前为零的表条目时，都会找到不同的值。

对于较大的值，如果您对100000以上的计数不感兴趣，std::map是合适的，如果它足够快。如果这对你来说太慢了，你可以编写自己的B树。

7
投票

我很确定你能做到：

  1. 创建Bloom过滤器
  2. 运行数组将每个元素插入到过滤器中（这是一个“慢”O（n），因为它需要计算每个值的几个独立的正确哈希值）
  3. 计算布隆过滤器中设置的位数
  4. 从过滤器的密度计算回到不同值的数量的估计。我不知道我头脑中的计算，但对Bloom过滤器理论的任何处理都会涉及到这一点，因为它对于过滤器在查找中产生误报的可能性至关重要。

假设您同时计算前10个最常见的值，那么如果少于10个不同的值，您将确切地知道它们是什么，并且您不需要估计。

我认为“最常用”的问题很难（很好，耗费内存）。假设您只需要最常用的前1个值。进一步假设您在阵列中有1000万个条目，并且在第一个990万个条目之后，到目前为止您看到的数字都没有出现超过100k次。那么你到目前为止看到的任何值都可能是最常用的值，因为它们中的任何一个都可以在最后运行100k值。更糟糕的是，他们中的任何两个最终都会有50k的运行，在这种情况下，前990万条目的计数是它们之间的平局。因此，为了在最常用的单次通过中进行计算，我认为您需要知道出现在990万中的每个值的确切计数。你必须为过去的10万个中两个值之间的近似关系做准备，因为如果发生这种情况，你不能再倒带并再次检查两个相关值。最终你可以开始剔除值 - 如果有一个数量为5000的值并且只剩下4000个条目要检查，那么你可以剔除任何数量为1000或更少的数据。但这并没有多大帮助。

所以我可能错过了一些东西，但我认为在最坏的情况下，“最常用”的问题要求你为你看到的每个值保持一个计数，直到几乎结束阵列。因此，您可以使用该计数集合来计算出有多少不同的值。

2
投票

即使对于大值，一种可以工作的方法是将它们分散到延迟分配的桶中。

假设你正在使用32位整数，创建一个2**32位数组是相对不切实际的（2**29 bytes，hum）。但是，我们可以假设2**16指针仍然合理（2**19字节：500kB），因此我们创建2**16桶（空指针）。

因此，最重要的想法是采用“稀疏”的方法进行计数，并希望整数不会分散，因此许多桶指针将保持null。

typedef std::pair<int32_t, int32_t> Pair;
typedef std::vector<Pair> Bucket;
typedef std::vector<Bucket*> Vector;

struct Comparator {
  bool operator()(Pair const& left, Pair const& right) const {
    return left.first < right.first;
  }
};

void add(Bucket& v, int32_t value) {
  Pair const pair(value, 1);
  Vector::iterator it = std::lower_bound(v.begin(), v.end(), pair, Compare());
  if (it == v.end() or it->first > value) {
    v.insert(it, pair);
    return;
  }

  it->second += 1;
}

void gather(Vector& v, int32_t const* begin, int32_t const* end) {
  for (; begin != end; ++begin) {
    uint16_t const index = *begin >> 16;

    Bucket*& bucket = v[index];

    if (bucket == 0) { bucket = new Bucket(); }

    add(*bucket, *begin);
  }
}

收集数据后，您可以计算不同值的数量或轻松找到顶部或底部。

几点说明：

  • 桶的数量是完全可定制的（从而让您控制原始内存的数量）
  • 重新分区的策略也是可定制的（这只是我在这里制作的廉价哈希表）
  • 如果它开始爆炸，可以监控分配的铲斗的数量并放弃或切换齿轮。
  • 如果每个值都不同，那么它就不会起作用，但是当你意识到它时，你已经收集了很多计数，所以你至少能够给出不同值的下限，并且你还有一个顶部/底部的起点。

如果您设法收集这些统计信息，那么您的工作就会被删除。

0
投票

对于8位和16位非常明显，您可以在每次迭代时跟踪每种可能性。

当你得到32位和64位整数时，你真的没有记忆来追踪每一种可能性。

这里有一些可能超出约束范围的自然建议。

我真的不明白你为什么不能对数组进行排序。 RadixSort是O（n），一旦排序，将获得准确的独特性和前X个信息。实际上，如果使用1字节基数（1个通道用于计数+ 1 * 4通道用于每个字节+ 1个通道用于获取值），那么对于32位将共有6个通道。

在与上面相同的尖点中，为什么不使用SQL。您可以创建一个存储过程，该数组将数组作为表值参数，并一次性返回不同值的数量和前面的x值。也可以并行调用此存储过程。

-- number of distinct
SELECT COUNT(DISTINCT(n)) FROM @tmp
-- top x
SELECT TOP 10 n, COUNT(n) FROM @tmp GROUP BY n ORDER BY COUNT(n) DESC
0
投票

我刚才想到了一个有趣的解决方案。它基于布尔代数定律，称为乘法幂乘，它指出：

X * X = X.

从它，并使用布尔乘法的可交换属性，我们可以推导出：

X * Y * X = X * X * Y = X * Y.

现在，你看到我要去哪里？这就是算法的工作方式（我对伪代码很糟糕）：

  1. make c = element1＆element2（整数的二进制表示之间的二进制AND）
  2. 对于i = 3，直到i == size_of_array使b = c＆element [i];如果b！= c那么diferent_values ++; C = B;

在第一次迭代中，我们使（element1 * element2）* element3。我们可以将其表示为：

（X * Y）* Z.

如果Z（element3）等于X（element1），那么：

（X * Y）* Z = X * Y * X = X * Y.

如果Z等于Y（element2），那么：

（X * Y）* Z = X * Y * Y = X * Y.

因此，如果Z与X或Y不同，那么当我们将它乘以Z时，X * Y不会改变

这对于大表达式仍然有效，例如：

（X * A * Z * G * T * P * S）* S = X * A * Z * G * T * P * S

如果我们收到的值是我们的大被乘数的因子（这意味着它已经被计算过），那么当我们将它乘以收到的输入时，大被乘数不会改变，因此没有新的不同值。

这就是它将如何发展。每次计算出不同的值时，我们的大被乘数和该不同值的乘法将与大操作数不同。所以，使用b = c & element[i]，如果b!= c我们只是增加不同的值计数器。

我想我不够清楚。如果是这种情况，请告诉我。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.