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

Question

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

例如，给定日志，用户可以过滤到只看到出现一定缩放次数的条目。

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

Answer 1

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

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

Answer 2

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

取排序数组的每个m=n/l第2个元素。只有这些元素才是重要的，因为没有长度相同的元素序列m可以在i*m和（i 1）*m之间匹配。

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

总的复杂性将是O（（n/m）*logn）=O（l*logn）。对于较大的m，它可能（渐进地）优于O（n）。然而，要在实践中获得改进，您需要非常具体的情况：

>

您可以访问O（1）中数组的i-th元素，而无需读取整个数组。否则，再次使用哈希表的计数排序。

假设您有一个由排序的固定宽度整数组成的文件“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)

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