Wie vergleicht man zwei riesige List in Java? - Java, Arraylist

Meine Anwendung generiert 2 große Listen (bis zu 3,5 Millionen Zeichenfolgen). Ich brauche den besten und schnellsten Weg, um es zu vergleichen. Momentan mache ich es so:

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

Aber diese Methode ist sehr teuer im Speicher, wie ich von jconsole sehe und manchmal sogar Stapel darauf verarbeiten. Irgendwelche guten Lösungen oder Ideen?

Elementpositionen / Reihenfolge in der Liste sind immerdas Gleiche, also muss ich nicht damit umgehen. Nach dem Vergleich muss ich wissen, ob die Liste gleich ist und um die Unterschiede von dieser Liste zu erhalten, wenn sie nicht gleich sind. Subtrahieren funktioniert perfekt für kleine Listen.

Antworten:

3 für die Antwort № 1

Vorausgesetzt, du hast gesagt, deine zwei Listen sind bereitssortiert, können sie in O (N) Zeit verglichen werden, was viel schneller ist als Ihre aktuelle Lösung, die ListUtils verwendet. Die folgende Methode verwendet dies mit einem ähnlichen Algorithmus wie der, der zwei sortierte Listen zusammenführt, die in den meisten Lehrbüchern gefunden werden können.

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

Die obige Methode verwendet keine externen Bibliotheken undkann mit jeder Version von Java ab 6 verwendet werden. Wenn Sie einen PeekingIterator, wie den von Apache Commons Collections oder Guava, verwenden oder eigene schreiben, können Sie die Methode vereinfachen, besonders wenn Sie auch Java 8 verwenden:

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

Verwandte Fragen
Speisekarte