Самый эффективный способ найти уникальные пересечения из двух разных списков ArrayLists?
У меня есть два Arraylists, A и B.
ArrayList A состоит из классов, которые состоят из набора данных, включая идентификатор categoryID, Несколько элементов в A могут иметь одинаковые categoryID, CategoryID могут выглядеть так для каждого элемента в A: [1, 1, 2, 2, 3, 4, 7],
ArrayList B состоит из разных классов, которые содержат разный набор данных, в том числе categoryID, categoryID уникален для каждого элемента в этом списке. Пример: [1, 2, 3, 4, 5, 6, 7],
Оба списка отсортированы по categoryIDчто, надеюсь, делает это проще.
Я пытаюсь создать новый список C, который состоит из элементов из listB, имеющих хотя бы одно пересечение со списком A. Таким образом, список C должен содержать пункты [1, 2, 3, 4, 7] из приведенного выше ввода.
Пока что моя стратегия - перебирать оба списка. Я не верю, что это самый эффективный способ сделать это, поэтому я спрашиваю, какие есть другие альтернативы.
Мой метод:
ArrayList<classB> results = new ArrayList<classB>();
for (classA itemA : listA){
int categoryID = item.categoryID;
for (classB itemB : listB){
if (itemB.categoryID == categoryID){
if (!results.contains(itemB)){
results.add(itemB);
}
break;
}
}
}
Сначала я пересекаю список A, перехватываю categoryID, затем пересекаю listB, чтобы найти соответствующий ID категории. Когда я нахожу это, я проверяю, содержит ли список результатов этот элемент из listB. Если это не так, то я добавляю его к результатам, вырываюсь из внутреннего цикла for и продолжаю проходить через listA. Если список результатов уже содержит itemB, я просто выйду из внутреннего цикла for и продолжу работу через listA. Этот метод O(n^2), что не очень хорошо для больших наборов данных. Есть какие-нибудь идеи по улучшению?
6 ответов
Добавьте все идентификаторы категории из ListA в Setдавайте назовем это setACategories, После этого переберите ListB, если setACategories содержит categoryID элемента из ListB, а затем добавить этот элемент ListB в results,
results также должен быть Set, потому что, похоже, вы хотите, чтобы только один матч из списка B вошел в results а не несколько совпадений (позволяет избежать вызова (!results.contains(itemB)),
Добавить categoryID значения из listA в Set, а затем переберите listB, выбирая те элементы, для которых categoryId находится в вашем наборе.
Ты пытался:
public void test() {
Collection c1 = new ArrayList();
Collection c2 = new ArrayList();
c1.add("Text 1");
c1.add("Text 2");
c1.add("Text 3");
c1.add("Text 4");
c1.add("Text 5");
c2.add("Text 3");
c2.add("Text 4");
c2.add("Text 5");
c2.add("Text 6");
c2.add("Text 7");
c1.retainAll(c2);
for (Iterator iterator = c1.iterator(); iterator.hasNext();) {
Object next = iterator.next();
System.out.println(next); //Output: Text 3, Text 4, Text 5
}
}
Лучший способ сейчас - использовать поток Java:
List<foo> list1 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<foo> list2 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
list1.stream().filter(f -> list2.contains(f)).collect(Collectors.toList());
Тем не менее, я сам использую библиотеку Apache Commons для такого рода вещей:
Попробуйте использовать Sets.intersection(Set<E> set1,Set<?> set2) из Google Guava.
Конечно, вы можете преобразовать массивы в наборы с Sets.newHashSet(Iterable<? extends E> elements)
Смотрите следующий код. Я реализовал пересечение, которое использует тот факт, что они отсортированы, чтобы улучшить метод верхнего ответа.
Он вроде работает как шаг слияния в сортировке слиянием, за исключением того, что он обеспечивает пересечения. Вероятно, это может быть улучшено дальше, я написал это через 30 минут.
С текущими данными он работает примерно в 17 раз быстрее, чем топовый ответ. Это также экономит O(n) памяти, так как требуется только один набор
Также см.: Пересечение двух отсортированных массивов
import java.util.*;
public class test {
public static void main (String[] args) {
List<Integer> a1 = new ArrayList<Integer>();
List<Integer> a2 = new ArrayList<Integer>();
Random r = new Random();
for(int i = 0; i < 1000000; i++) {
a1.add(r.nextInt(1000000));
a2.add(r.nextInt(1000000));
}
Collections.sort(a1);
Collections.sort(a2);
System.out.println("Starting");
long t1 = System.currentTimeMillis();
Set<Integer> set1 = func1(a1, a2);
long t2 = System.currentTimeMillis();
System.out.println("Func1 done in: " + (t2-t1) + " milliseconds.");
long t3 = System.currentTimeMillis();
Set<Integer> set2 = func2(a1, a2);
long t4 = System.currentTimeMillis();
System.out.println("Func2 done in: " + (t4-t3) + " milliseconds.");
if(set1.size() != set2.size()) {
System.out.println("ERROR - sizes not equal");
System.exit(1);
}
for(Integer t : set1) {
if (!set2.contains(t)) {
System.out.println("ERROR");
System.exit(1);
}
}
}
public static Set<Integer> func1(List<Integer> a1, List<Integer> a2) {
Set<Integer> intersection = new HashSet<Integer>();
int index = 0;
for(Integer a : a1) {
while( index < a2.size() && a2.get(index) < a) {
index++;
}
if(index == a2.size()) {
break;
}
if (a2.get(index).equals(a)) {
intersection.add(a);
} else {
continue;
}
}
return intersection;
}
public static Set<Integer> func2(List<Integer> a1, List<Integer> a2) {
Set<Integer> intersection = new HashSet<Integer>();
Set<Integer> tempSet = new HashSet<Integer>();
for(Integer a : a1) {
tempSet.add(a);
}
for(Integer b : a2) {
if(tempSet.contains(b)) {
intersection.add(b);
}
}
return intersection;
}
}