Самый эффективный способ вернуть общие элементы из двух строковых массивов - PullRequest
10 голосов
/ 19 декабря 2011

В Java, какой самый эффективный способ вернуть общие элементы из двух String Arrays? Я могу сделать это с помощью пары циклов for, но это не очень эффективно. Лучшее, что я мог придумать, это преобразовать List и затем применить retainAll, основываясь на моем обзоре аналогичного вопроса SO :

List<String> compareList = Arrays.asList(strArr1);
List<String> baseList = Arrays.asList(strArr2);
baseList.retainAll(compareList);

Ответы [ 6 ]

5 голосов
/ 19 декабря 2011

РЕДАКТИРОВАНИЕ:

Это однострочник:

compareList.retainAll(new HashSet<String>(baseList));

Значение retainAll impl (в AbstractCollection) перебирает this и использует contains() для аргумента. Превращение аргумента в HashSet приведет к быстрому поиску, поэтому цикл внутри retainAll будет выполнен как можно быстрее.

Кроме того, имя baseList намекает на то, что оно является константой, поэтому вы получите значительное улучшение производительности, если кешируете это:

static final Set<String> BASE = Collections.unmodifiableSet(new HashSet<String>(Arrays.asList("one", "two", "three", "etc")));

static void retainCommonWithBase(Collection<String> strings) {
    strings.retainAll(BASE);
}

Если вы хотите сохранить исходный список, сделайте следующее:

static List<String> retainCommonWithBase(List<String> strings) {
   List<String> result = new ArrayList<String>(strings);
   result.retainAll(BASE);
   return result;
}
3 голосов
/ 19 декабря 2011

Сортировка обоих массивов.

После сортировки можно отсортировать оба отсортированных массива ровно один раз, используя два индекса.

Это будет O (NlogN).

3 голосов
/ 19 декабря 2011

Я бы тогда использовал HashSets (и retainAll ), что сделало бы полную проверку O (n) (для каждого элемента в первом поиске набора, если он существует (contains()), то есть O (1) для HashSet). Тем не менее, List создаются быстрее (HashSet может иметь дело с коллизиями ...).

Имейте в виду, что Set и List имеют разную семантику (списки допускают повторяющиеся элементы, нули ...).

1 голос
/ 19 декабря 2011

То, что вы хотите, называется пересечением. Видеть, что: Пересечение и объединение ArrayLists в Java

Использование коллекции, основанной на хэш-функции, обеспечивает более быстрый метод contains (), особенно для строк, которые имеют оптимизированный хэш-код.


Если вы можете импортировать библиотеки, рассмотрите возможность использования пересечения Sets.inter of Guava.


Edit:

Не знал о методе retainAll.

Обратите внимание, что реализация AbstractCollection, которая, кажется, не переопределена для HashSets и LinkedHashSets:

public boolean retainAll (Коллекция c) { логическое изменение = ложь; Iterator it = iterator (); while (it.hasNext ()) { if (! c.contains (it.next ())) { it.remove (); модифицированный = правда; } } возврат изменен; }

Что означает, что вы вызываете функции метода () для параметра коллекции! Это означает, что если вы передадите параметр List, вы получите вызов equals для многих элементов списка для каждой итерации!

Вот почему я не думаю, что приведенные выше реализации с использованием retainAll хороши.

public <T> List<T> intersection(List<T> list1, List<T> list2) {
    boolean firstIsBigger = list1.size() > list2.size();
    List<T> big =  firstIsBigger ? list1:list2;
    Set<T> small =  firstIsBigger ? new HashSet<T>(list2) : new HashSet<T>(list1);
    return big.retainsAll(small)
}

Выбор использования набора для наименьшего списка, потому что быстрее создать набор, а большой список выполняет итерации довольно хорошо ...

Обратите внимание, что один из исходных параметров списка может быть изменен, вы сами должны сделать копию ...

1 голос
/ 19 декабря 2011

сохранить все не поддерживается списком.используйте вместо этого набор:

import java.util.*;
public class Main {
    public static void main(String[] args) {
        String[] strings1={"a","b","b","c"},strings2={"b","c","c","d"};
        List<String> list=Arrays.asList(strings1);
        //list.retainAll(Arrays.asList(strings2)); // throws UnsupportedOperationException
        //System.out.println(list);
        Set<String> set=new LinkedHashSet<String>(Arrays.asList(strings1));
        set.retainAll(Arrays.asList(strings2));
        System.out.println(set);
    }
}
0 голосов
/ 19 февраля 2015

У меня было интервью, и этот вопрос они задавали мне во время технического интервью.Мой ответ был следующие строки кода:

public static void main(String[] args) {

        String[] temp1 = {"a", "b", "c"};
        String[] temp2 = {"c", "d", "a", "e", "f"};
        String[] temp3 = {"b", "c", "a", "a", "f"};

        ArrayList<String> list1 = new ArrayList<String>(Arrays.asList(temp1));
        System.out.println("list1: " + list1);
        ArrayList<String> list2 = new ArrayList<String>(Arrays.asList(temp2));
        System.out.println("list2: " + list2);
        ArrayList<String> list3 = new ArrayList<String>(Arrays.asList(temp3));
        System.out.println("list3: " + list3);

        list1.retainAll(list2);
        list1.retainAll(list3);
        for (String str : list1)
            System.out.println("Commons: " + str);
}

Вывод:

list1: [a, b, c]
list2: [c, d, a, e, f]
list3: [b, c, a, a, f]
Commons: a
Commons: c
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...