algorithm - 在排序日志中查找 "important"条目

Question

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

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

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

Answer 1

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

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

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

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

• 数组已预排序(否则只需使用计数排序，您会立即得到答案)

• 您可以在 O(1) 中访问数组的第 i 个元素，无需读取整个数组。否则，再次使用哈希表的计数排序。

假设您有一个由排序的固定宽度整数 “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，这也是可行的。但与优化一样，它可能值得测试。