Пересечение и объединение ArrayLists в Java

Question

Есть ли способы сделать это?Я искал, но не мог найти.

Еще один вопрос: мне нужны эти методы, чтобы я мог фильтровать файлы.Некоторые из них являются AND фильтрами, а некоторые - OR фильтрами (как в теории множеств), поэтому мне нужно фильтровать по всем файлам и объединять / пересекать ArrayLists, которые содержат эти файлы.

Должен ли я использоватьдругая структура данных для хранения файлов?Есть ли что-нибудь еще, что могло бы предложить лучшее время выполнения?

Answer 1

Коллекция (так же ArrayList) имеет:

col.retainAll(otherCol) // for intersection
col.addAll(otherCol) // for union

Используйте реализацию List, если вы принимаете повторы, реализацию Set, если вы этого не сделаете:

Collection<String> col1 = new ArrayList<String>(); // {a, b, c}
// Collection<String> col1 = new TreeSet<String>();
col1.add("a");
col1.add("b");
col1.add("c");

Collection<String> col2 = new ArrayList<String>(); // {b, c, d, e}
// Collection<String> col2 = new TreeSet<String>();
col2.add("b");
col2.add("c");
col2.add("d");
col2.add("e");

col1.addAll(col2);
System.out.println(col1); 
//output for ArrayList: [a, b, c, b, c, d, e]
//output for TreeSet: [a, b, c, d, e]

Answer 2

Вот простая реализация без использования сторонней библиотеки.Основное преимущество перед retainAll, removeAll и addAll заключается в том, что эти методы не изменяют исходные списки, вводимые в методы.

public class Test {

    public static void main(String... args) throws Exception {

        List<String> list1 = new ArrayList<String>(Arrays.asList("A", "B", "C"));
        List<String> list2 = new ArrayList<String>(Arrays.asList("B", "C", "D", "E", "F"));

        System.out.println(new Test().intersection(list1, list2));
        System.out.println(new Test().union(list1, list2));
    }

    public <T> List<T> union(List<T> list1, List<T> list2) {
        Set<T> set = new HashSet<T>();

        set.addAll(list1);
        set.addAll(list2);

        return new ArrayList<T>(set);
    }

    public <T> List<T> intersection(List<T> list1, List<T> list2) {
        List<T> list = new ArrayList<T>();

        for (T t : list1) {
            if(list2.contains(t)) {
                list.add(t);
            }
        }

        return list;
    }
}

Answer 3

Это сообщение довольно старое, но, тем не менее, оно было первым, всплывающим в Google при поиске этой темы.

Я хочу обновить информацию, используя потоки Java 8, делающие (в основном) то же самое водна строка:

List<T> intersect = list1.stream()
    .filter(list2::contains)
    .collect(Collectors.toList());

List<T> union = Stream.concat(list1.stream(), list2.stream())
    .distinct()
    .collect(Collectors.toList());

Если у кого-нибудь есть лучшее / более быстрое решение, дайте мне знать, но это хорошее решение, которое можно легко включить в метод без добавления ненужного вспомогательного класса / метода ивсе еще сохраняйте читаемость.

Answer 4

list1.retainAll(list2) - is intersection

объединение будет removeAll, а затем addAll.

Найти больше в документации коллекции (ArrayList - коллекция) http://download.oracle.com/javase/1.5.0/docs/api/java/util/Collection.html

Answer 5

Объединения и пересечения определены только для множеств, а не списков.Как вы упомянули.

Проверьте guava библиотека для фильтров.Также гуава обеспечивает реальные пересечения и союзы

 static <E> Sets.SetView<E >union(Set<? extends E> set1, Set<? extends E> set2)
 static <E> Sets.SetView<E> intersection(Set<E> set1, Set<?> set2)

Answer 6

Вы можете использовать CollectionUtils из Apache Commons .

Answer 7

Решение помечено неэффективно.Он имеет O (n ^ 2) временную сложность.Что мы можем сделать, так это отсортировать оба списка и выполнить алгоритм пересечения, как показано ниже.

private  static ArrayList<Integer> interesect(ArrayList<Integer> f, ArrayList<Integer> s) { 
    ArrayList<Integer> res = new ArrayList<Integer>();

    int i = 0, j = 0; 
    while (i != f.size() && j != s.size()) { 

        if (f.get(i) < s.get(j)) {
            i ++;
        } else if (f.get(i) > s.get(j)) { 
            j ++;
        } else { 
            res.add(f.get(i)); 
            i ++;  j ++;
        }
    }


    return res; 
}

Этот имеет сложность O (n log n + n), которая находится в O (n log n).Союз делается аналогичным образом.Просто убедитесь, что вы вносите соответствующие изменения в операторы if-elseif-else.

Вы также можете использовать итераторы, если хотите (я знаю, что они более эффективны в C ++, я не знаю, так ли это и в Java).

Answer 8

Вот способ, которым вы можете сделать пересечение с потоками (помните, что вы должны использовать java 8 для потоков):

List<foo> fooList1 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<foo> fooList2 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
fooList1.stream().filter(f -> fooList2.contains(f)).collect(Collectors.toList());

Пример для списков с различными типами.Если у вас есть связь между foo и bar, и вы можете получить bar-объект из foo, вы можете изменить свой поток:

List<foo> fooList = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<bar> barList = new ArrayList<>(Arrays.asList(new bar(), new bar()));

fooList.stream().filter(f -> barList.contains(f.getBar()).collect(Collectors.toList());

Answer 9

Я думаю, вы должны использовать Set для хранения файлов, если вы хотите сделать пересечение и объединить их. Затем вы можете использовать Гуава * Устанавливает класс для выполнения union, intersection и фильтрации по Predicate. Разница между этими методами и другими предложениями заключается в том, что все эти методы создают ленивые представления объединения, пересечения и т. Д. Из двух наборов. Apache Commons создает новую коллекцию и копирует в нее данные. retainAll изменяет одну из ваших коллекций, удаляя из нее элементы.

Answer 10

• retainAll изменит ваш список
• У Guava нет API для Списка (только для набора)

Я нашел ListUtils очень полезным для этого случая использования.

Используйте ListUtils из org.apache.commons.collections, если вы не хотите изменять существующий список.

ListUtils.intersection(list1, list2)