在已排序的日志中查找 "important" 个条目

Question

我有一个由几千个整数组成的日志文件，每个整数都占一行。我已经将其解析为这样的整数数组，也进行了排序。现在我的问题变成了从这个日志中找到 "important" 整数——这些整数有时会出现一些用户可配置的部分。

例如，给定日志，用户可以过滤以仅查看出现特定比例次数的条目。

目前我正在扫描整个数组并记录每个条目出现的次数。肯定有更好的方法吧？

Answer 1

您的排序可能需要 O(NlogN) 时间。您是否需要对同一个数据集进行多次 (n/I) 查询？

如果是，遍历排序数组，生成 (Value;Count) 对并按 Count 字段对它们进行排序。现在您可以使用二进制搜索轻松分离具有高计数的对

Answer 2

首先，我需要注意以下只是一个理论解决方案，您可能应该使用@MBo 提出的方案。

取出排序数组的第 m = n / l 个元素。只有那些元素可能是重要的，因为在 i*m 和 (i+1)*m 之间不能容纳长度为 m 的相同元素序列。

对于每个元素x，用二进制搜索在数组中找到它的下界和上界。减去索引，你可以知道计数，并决定保留或丢弃 x 不重要。

总复杂度为 O((n/m) * log n) = O(l * log n)。对于大 m，它可能（渐近地）优于 O(n)。但是，要在实践中取得进步，您需要非常具体的情况：

给你的数组是预排序的（否则只要使用计数排序，你就会立即得到答案）
您可以访问 O(1) 中数组的第 i 个元素，而无需读取整个数组 。否则，再次使用散列 table.

假设您有一个由 排序的 fixed-width 整数 "data.bin" 组成的文件（可变宽度也是可能的，但需要一些额外的努力） .然后在伪代码中，算法可能是这样的：

def find_all_important(l, n):
  m = n / l
  for i = m to l step m:
    x = read_integer_at_offset("data.bin", i)
    lower_bound = find_lower_bound(x, 0, i)
    upper_bound = find_upper_bound(x, i, n)
    if upper_bound - lower_bound >= m:
      report(x)

def find_lower_bound(x, begin, end):
  if end - begin == 0:
    return begin
  mid = (end + begin) / 2
  x = read_integer_at_offset("data.bin", mid)
  if mid < x:
    return find_lower_bound(x, mid + 1, end)
  else:
    return find_lower_bound(x, begin, mid)

作为猜测，与现代硬件上的天真 O(n) 相比，您不会获得任何明显的改进，除非您的文件非常大（数百 MB）。当然，如果您的数据无法放入 RAM，这也是可行的。但与优化一样，它可能值得测试。

在已排序的日志中查找 "important" 个条目

Find "important" entries in a sorted log

algorithm

big-o