Как избежать O (N ^ 2) при сравнении элементов из 2 списков?

Question

У меня есть 2 списка с одним и тем же типом объекта.

List A [ foo, bar, moo, woo, pee ]

List B [ bar, woo ]

Я хочу сравнить эти 2 списка и, если имя совпадает, установить для его свойства значение true.

Например,

if(ListA[1].name.equals(ListB[0].name)) { //match name 'bar' and 'bar'
    ListA[1].hasSameName = true;
}

что-то в этом роде.

Я могу написать O (N ^ 2) решение.

for(Talent checkedTalent : ListA) {
    for(Talent filteredTalent : ListB) {
        if( checkedTalent.Id.equals(filteredTalent.Id) ) {
            filteredTalent.isSelected = true;   
        }
    }
}

Может ли этобыть сделано более эффективным способом?

Answer 1

Использовать хеширование для решения O (n) (при условии эффективной реализации хеширования):

Set<String> ids = new HashSet<String>(ListA.size());
for(Talent checkedTalent : ListA) {
    ids.add(checkedTalent.Id);
}
for(Talent filteredTalent : ListB) {
    if (ids.contains(filteredTalent.Id)) {
        filteredTalent.isSelected = true;
    }
}

Answer 2

Обратите внимание, что решение O (n ² ) имеет такую ​​временную сложность, потому что для каждого элемента из ListA необходимо проверить все из ListB (снова). Вы могли бы уменьшить значение до O (n), если бы могли каким-либо образом выполнить поиск O (1) на ListB для текущего элемента из ListA. Одна структура данных, которую вы можете использовать для этого, это Map.

Итак, если вы строите Map из одного из списков и пересекаете другой, просматривая каждый элемент в Map, чтобы увидеть, есть ли совпадение, вы можете уменьшить общую сложность времени до O (n ) - за счет O (n) места.

Например:

Map<String, Talent> map = new HashMap<String, Talent>();

for(Talent t : ListA)
{
    t.put(t.id, t);
}

for(Talent t : ListB)
{
    if(map.containsKey(t.id))
    {
        t.isSelected = true;
    }
}

Answer 3

Сортируйте затем (2 * (n log n)), а затем пройдитесь по каждому списку (2 * n).

Answer 4

Вы можете создать набор из первого списка:

Set mySet = new HashSet(listA);

Теперь вы перебираете список B:

for(Object foo : listB)
    if(mySet.contains(foo))
        foo.isSelected = true

Я думаю, это O (n * lg n), но я не собираюсь приводить доказательства. :)

Answer 5

Чтобы получить представление о том, как сделать это более эффективно, ознакомьтесь с тем, как можно реализовать объединение SQL, а именно: Соединение с вложенным циклом , Соединение с вложенным циклом с индексом b-дереваи двоичный поиск по нему для каждого элемента в другом), объединение слиянием или хеш-соединение .Та же концепция.