Come confrontare due enormi liste in Java?

La mia applicazione genera 2 grandi liste (fino a 3,5 milioni di stringhe). Ho bisogno del modo migliore e più veloce per confrontarlo. Attualmente lo sto facendo in questo modo:

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

Ma questo metodo è molto costoso in memoria, come vedo da jconsole e, a volte, processa anche lo stack su di esso. Qualche buona soluzione o idea?

Le posizioni dell’elemento / ordine nella lista sono sempre le stesse, quindi non ho bisogno di affrontarlo. Dopo aver confrontato ho bisogno di sapere se la lista è la stessa e di ottenere le differenze da questa lista se non sono la stessa cosa. Sottrai funziona perfettamente per le piccole liste.

Dato che hai detto che i tuoi due elenchi sono già ordinati, possono essere confrontati in tempo O (N), che è molto più veloce della tua attuale soluzione che usa ListUtils. Il seguente metodo esegue questo utilizzando un algoritmo simile a quello che unisce due elenchi ordinati che possono essere trovati nella maggior parte dei libri di testo.

 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; } } } } } 

Il metodo precedente non utilizza librerie esterne e può essere utilizzato con qualsiasi versione di Java dal 6 in poi. Se usi un PeekingIterator, come quello di Apache Commons Collections o Guava, o scrivi il tuo, allora puoi semplificare il metodo, specialmente se usi anche 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); }