java - 列表比较算法复杂度的改进

Question

我有两个数组 array1 = Array<List<Integer>>和 array2 = Array<Integer>我遍历 array2 .然后我尝试从array1中找到哪个列表array2 中的当前项目可能。我从 array1 检索相应的列表并遍历它看看我是否可以在 array1 中找到类似的数字.我将相似性定义为一些错误 epsilon 内的相等数字(即 6 将被发现等于 7 与 epsilon=1 自 7-6=1 )。如果数字相等，我将它们添加到名为 matchList 的列表中.最后我有一个列表 matchList我们叫 resultList .

这是一些伪代码:

List<List<Integer>> resultList = new ArrayList<List<Integer>>();
for (i = 0; i < array2.length; i++) {
  int index = array2[i] % n;
  List<Integer> currentList = array1[index];
  List<Integer> matchList = new LinkedList<Integer>();

  while(int currentItem : currentList) {
    if (currentItem - array2[i] < epsilon){
      matchList.add(currentItem);
    }
  }

  if (!matchList.isEmpty()){
    resultList.add(matchList);
  }
}

我的问题是我是否可以改进这个 O(n*m)算法的复杂性。我已经通过预分配数组、使用迭代器遍历链表以及使用原始类型集合(Trove 而不是 Java 的内置函数)和其他一些措施大大提高了算法的速度。

编辑:我只对改进 big-O 运行时的建议感兴趣。

Answer 1

为了通过算法解决这个问题(简单地按照评论中的建议并行运行您的算法并不会降低您的算法复杂性)，您需要引入一种更高效的数据结构，使您能够执行更快的查找。

您首先要创建存储桶，其中每个存储桶都包含给定范围内的值(value plus/minus epsilon)。因此，一个列表值可以在多个桶中。您至少可以在 O(n * #buckets) 中创建此遗愿 list ，这可能会更少，具体取决于您是否对值的分布进行了假设。

接下来，您可以根据这些存储桶检查您的其他列表。根据您的范围比率和这些桶的值的数量，延迟创建桶并将桶本身组织在某种哈希表中可能是有效的。然后您将遍历另一个列表并检查桶中包含的值，这可以在 O(m) 时间内完成。

这使您总共有 O(n * #buckets + m)。