如何比較Java中的兩個巨大列表<String>？

Question

我的應用程序生成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<Integer> sourceDbResults = Arrays.asList(1, 2, 3, 4, 5, 8); 
     List<Integer> hiveResults = Arrays.asList(2, 3, 6, 7); 
     List<Integer> inSourceDb_notInHive = new ArrayList<>(); 
     List<Integer> 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 <T extends Comparable<? super T>> void compareSortedLists(
      Iterable<T> list1, Iterable<T> list2, 
      Collection<T> onlyInList1, Collection<T> onlyInList2) { 
     Iterator<T> it1 = list1.iterator(); 
     Iterator<T> 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; 
       } 
      } 
     } 
    } 
} 

上述方法不使用外部庫，可以使用任何版本的Java，從6開始。如果使用PeekingIterator，比如Apache Commons Collections中，或番石榴的人，或者自己寫，那麼你就可以使該方法更簡單，特別是如果你還使用Java 8：

public static <T extends Comparable<? super T>> void compareSortedLists(
     Iterable<T> list1, Iterable<T> list2, 
     Collection<T> onlyInList1, Collection<T> onlyInList2) { 
    PeekingIterator<T> it1 = new PeekingIterator<>(list1.iterator()); 
    PeekingIterator<T> 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); 
}