如何在Java中比较两个巨大的List ？

我的应用程序生成2个大列表（最多3.5个字符串记录）。 我需要最好和最快的方式来比较它。 目前我这样做：

List list1 = ListUtils.subtract(sourceDbResults, hiveResults); List list2 = ListUtils.subtract(hiveResults, sourceDbResults); 

但是这种方法在内存上确实非常昂贵，因为我从jconsole看到，有时甚至可以在其上处理堆栈。 任何好的解决方案或想法？

列表中的元素位置/顺序始终相同，因此我不需要处理它。 在比较之后，我需要知道列表是否相同，并且如果它们不相同则从这些列表中获得差异。 减法适用于小型列表。

Answer 1

鉴于您已经说过您的两个列表已经排序，它们可以在O（N）时间内进行比较，这比使用ListUtils的当前解决方案快得多。 以下方法使用与合并两个排序列表的算法类似的算法来执行此操作，这些列表可以在大多数教科书中找到。

 import java.util.*; public class CompareSortedLists { public static void main(String[] args) { List sourceDbResults = Arrays.asList(1, 2, 3, 4, 5, 8); List hiveResults = Arrays.asList(2, 3, 6, 7); List inSourceDb_notInHive = new ArrayList<>(); List inHive_notInSourceDb = new ArrayList<>(); compareSortedLists( sourceDbResults, hiveResults, inSourceDb_notInHive, inHive_notInSourceDb); assert inSourceDb_notInHive.equals(Arrays.asList(1, 4, 5, 8)); assert inHive_notInSourceDb.equals(Arrays.asList(6, 7)); } /** * Compares two sorted lists (or other iterable collections in ascending order). * Adds to onlyInList1 any and all elements in list1 that are not in list2; and * conversely to onlyInList2. The caller must ensure the two input lists are * already sorted and should initialize onlyInList1 and onlyInList2 to empty, * writable collections. */ public static > void compareSortedLists( Iterable list1, Iterable list2, Collection onlyInList1, Collection onlyInList2) { Iterator it1 = list1.iterator(); Iterator it2 = list2.iterator(); T e1 = it1.hasNext() ? it1.next() : null; T e2 = it2.hasNext() ? it2.next() : null; while (e1 != null || e2 != null) { if (e2 == null) { // No more elements in list2, some remaining in list1 onlyInList1.add(e1); e1 = it1.hasNext() ? it1.next() : null; } else if (e1 == null) { // No more elements in list1, some remaining in list2 onlyInList2.add(e2); e2 = it2.hasNext() ? it2.next() : null; } else { int comp = e1.compareTo(e2); if (comp < 0) { onlyInList1.add(e1); e1 = it1.hasNext() ? it1.next() : null; } else if (comp > 0) { onlyInList2.add(e2); e2 = it2.hasNext() ? it2.next() : null; } else /* comp == 0 */ { e1 = it1.hasNext() ? it1.next() : null; e2 = it2.hasNext() ? it2.next() : null; } } } } } 

上述方法不使用外部库，可以与6个以上的任何Java版本一起使用。 如果您使用PeekingIterator，例如Apache Commons Collections或Guava中的PeekingIterator，或者编写自己的PeekingIterator，那么您可以使方法更简单，特别是如果您还使用Java 8：

 public static > void compareSortedLists( Iterable list1, Iterable list2, Collection onlyInList1, Collection onlyInList2) { PeekingIterator it1 = new PeekingIterator<>(list1.iterator()); PeekingIterator it2 = new PeekingIterator<>(list2.iterator()); while (it1.hasNext() && it2.hasNext()) { int comp = it1.peek().compareTo(it2.peek()); if (comp < 0) onlyInList1.add(it1.next()); else if (comp > 0) onlyInList2.add(it2.next()); else /* comp == 0 */ { it1.next(); it2.next(); } } it1.forEachRemaining(onlyInList1::add); it2.forEachRemaining(onlyInList2::add); }