Эффективный алгоритм пересечения списка

Question

С учетом двух списков (необязательно отсортированных), каков наиболее эффективный нерекурсивный алгоритм для поиска пересечения этих списков?

Answer 1

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

Answer 2

Возможно, вы захотите взглянуть на фильтры Блума. Это битовые векторы, которые дают вероятностный ответ, является ли элемент членом набора. Задание пересечения может быть реализовано с помощью простой побитовой операции И. Если у вас есть большое количество нулевых пересечений, фильтр Блума может помочь вам быстро устранить их. Однако вам все равно придется прибегнуть к одному из других алгоритмов, упомянутых здесь, чтобы вычислить фактическое пересечение. http://en.wikipedia.org/wiki/Bloom_filter

Answer 3

без хеширования, я полагаю, у вас есть два варианта:

• Наивным способом будет сравнение каждого элемента с каждым другим элементом. O (N ^ 2)
• Другим способом будет сначала отсортировать списки, а затем итерировать их: O (n lg n) * 2 + 2 * O (n)

Answer 4

Из списка функций eviews кажется, что он поддерживает сложные объединения и объединения (если это 'объединение', как в терминологии БД, он вычислит пересечение). Теперь покопайтесь в вашей документации: -)

Кроме того, eviews имеет свой собственный форум пользователей - почему бы не спросить там

Answer 5

с набором 1 создайте двоичное дерево поиска с O(log n), итерируйте set2 и выполните поиск по BST m X O(log n), так что всего O(log n) + O(m)+O(log n) ==> O(log n)(m+1)

Answer 6

в C ++ можно попробовать следующее с использованием карты STL

vector<int> set_intersection(vector<int> s1, vector<int> s2){

    vector<int> ret;
    map<int, bool> store;
    for(int i=0; i < s1.size(); i++){

        store[s1[i]] = true;
    }
    for(int i=0; i < s2.size(); i++){

        if(store[s2[i]] == true) ret.push_back(s2[i]);

    }
    return ret;
}

Answer 7

Вот еще одно возможное решение, которое я придумала: использование O (nlogn) во временной сложности и без дополнительной памяти. Вы можете проверить это здесь https://gist.github.com/4455373

Вот как это работает. Предполагая, что наборы не содержат повторений, объедините все наборы в один и отсортируйте его. Затем переберите объединенный набор и на каждой итерации создайте подмножество между текущим индексом i и i + n, где n - количество наборов, доступных в юниверсе. То, что мы ищем в цикле, - это повторяющаяся последовательность размером n, равной количеству множеств в юниверсе.

Если это подмножество в i равно этому подмножеству в n, это означает, что элемент в i повторяется n раз, что равно общему количеству множеств. И поскольку в любом наборе нет повторений, это означает, что каждый из наборов содержит это значение, поэтому мы добавляем его в пересечение. Затем мы сдвигаем индекс на i + что остается между ним и n, потому что определенно ни один из этих индексов не будет образовывать повторяющуюся последовательность.

Answer 8

Сначала отсортируйте оба списка с помощью быстрой сортировки: O (n * log (n). Затем сравните списки, сначала просмотрев самые низкие значения, и добавьте общие значения. Например, в lua):

function findIntersection(l1, l2)
    i, j = 1,1
    intersect = {}

    while i < #l1 and j < #l2 do
        if l1[i] == l2[i] then
            i, j = i + 1, j + 1
            table.insert(intersect, l1[i])
        else if l1[i] > l2[j] then
            l1, l2 = l2, l1
            i, j = j, i
        else
            i = i + 1
        end
    end

    return intersect
end

, что O(max(n, m)), где n и m - размеры списков.

РЕДАКТИРОВАТЬ: быстрая сортировка является рекурсивной, как сказано в комментариях, но похоже, что есть нерекурсивных реализаций

Answer 9

Использование указателей пропуска и Инструкции SSE может повысить эффективность пересечения списка.

Answer 10

Я придерживаюсь идеи «множеств». В JavaScript вы можете использовать первый список для заполнения объекта, используя элементы списка в качестве имен. Затем вы используете элементы списка из второго списка и посмотрите, существуют ли эти свойства.