在排序日志中查找“重要”条目

Question

我有一个由几千个整数组成的日志文件，每个整数都分开到一个新行上。我已经把它解析成一个这样的整数数组，也进行了排序。现在我的问题变成了从日志中找到“重要的”整数--这些整数显示了用户可配置的部分时间。

例如，给定日志，用户可以进行筛选，只看到出现一定比例次数的条目。

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

Answer 1

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

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

对于每个元素x，使用二进制搜索在数组中查找其下限和上限。减去索引，您可以知道count，并决定保留或丢弃x作为不重要的。

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)相比，您不会获得任何显著的改进，除非您的文件非常大（数百MBs）。当然，如果您的数据不能放进RAM中，它是可行的。但与优化一样，它可能值得测试。