Эффективный способ найти подходящие элементы в N списках?

Question

Учитывая количество списков элементов, найдите списки с соответствующими элементами.

Псевдокод методом грубой силы для этой задачи выглядит следующим образом:

foreach list L
    foreach item I in list L
        foreach list L2 such that L2 != L  
            for each item I2 in L2
                if I == I2
                    return new 3-tuple(L, L2, I) //not important for the algorithm

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

Я использую Java, если это имеет значение для вашей реализации.

Спасибо

Answer 1

1. Создать Map<Item,List<List>>.
2. Итерация по каждому элементу в каждом списке.
3. каждый раз, когда вы касаетесь элемента, добавьте текущий список к записи этого элемента на карте.

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

Этот алгоритм примерно равен O (N) , где N - количество списков (насколько сложна реализация Map, зависит от сложности) Я полагаю, что ваш алгоритм был по крайней мере O (N ^ 2) .

Предостережение: Я сравниваю количество сравнений, а не использование памяти. Если ваши списки очень большие и содержат в основном не дублированные элементы, карта, которую создает мой метод, может стать слишком большой.

Answer 2

Согласно вашему комментарию вы хотите MultiMap реализацию.Мультикарта похожа на карту, но может сопоставлять каждый ключ нескольким значениям.Сохраните значение и ссылку на все карты, содержащие это значение.

Map<Object, List>

Конечно, вы должны использовать безопасный тип вместо Object и безопасный тип List в качестве значения.То, что вы пытаетесь сделать, называется инвертированным индексом .

Answer 3

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

Я ссылаюсь ниже на «набор», где я думаю о чем-то похожем на C ++ std :: set.Я не знаю эквивалент Java, но любая схема хранения, которая позволяет быстрый поиск (дерево, хэш-таблица, что угодно).

Сравнение трех списков: L0, L1 и L2.

1. Чтение L0, размещение каждого элемента в наборе: S0.
2. Чтение L1, размещение элементов, которые соответствуютэлемент S0 в новый набор: S1 и отбрасывание других.
3. Сброс S0.
4. Считывание L2, сохранение элементов, соответствующих элементу S1, и отбрасывание других.

Обновление Просто понял, что вопрос был о "n" списках, а не трех.Однако расширение должно быть очевидным.(Надеюсь)

Обновление 2 Некоторый непроверенный код C ++ для иллюстрации алгоритма

#include <string>
#include <vector>
#include <set>
#include <cassert>

typedef std::vector<std::string> strlist_t;

strlist_t GetMatches(std::vector<strlist_t> vLists)
{
    assert(vLists.size() > 1);
    std::set<std::string> s0, s1;
    std::set<std::string> *pOld = &s1;
    std::set<std::string> *pNew = &s0;

    // unconditionally load first list as "new"
    s0.insert(vLists[0].begin(), vLists[0].end());

    for (size_t i=1; i<vLists.size(); ++i)
    {
        //swap recently read "new" to "old" now for comparison with new list
        std::swap(pOld, pNew);
        pNew->clear();

        // only keep new elements if they are matched in old list
        for (size_t j=0; j<vLists[i].size(); ++j)
        {
            if (pOld->end() != pOld->find(vLists[i][j]))
            {
                // found match
                pNew->insert(vLists[i][j]);
            }
        }
    }
    return strlist_t(pNew->begin(), pNew->end());
}

Answer 4

Вы можете использовать trie , модифицированный для записи списков, к которым принадлежит каждый узел.