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

Question

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

Answer 1

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

Answer 2

Во-первых, сортировать оба списка с помощью быстрой сортировки: O (. П * журнала (п) Затем сравните списки, просматривая наименьшие значения первого и добавить общие ценности, например, в 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 - размеры листинга.

EDIT: быстрая сортировка является рекурсивным, как сказано в комментариях, но, похоже, есть non-recursiveimplementations

Answer 3

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

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

Answer 4

Я получил некоторые хорошие ответы от this, которые вы можете применить. У меня пока нет возможности попробовать их, но поскольку они также охватывают пересечения, вы можете найти их полезными.

Answer 5

Почему бы не реализовать свою собственную простую хэш-таблицу или хэш-набор? Стоит избегать пересечения nlogn, если ваши списки большие, как вы говорите.

Поскольку вы знаете немного о своих данных заранее, вы должны иметь возможность выбрать хорошую хэш-функцию.

Answer 6

Если есть поддержка sets (как вы их называете в названии), так как встроенный обычно есть метод пересечения.

В любом случае, поскольку кто-то сказал, что вы можете сделать это легко (я не буду отправлять код, кто-то уже сделал это), если у вас отсортированы списки. Если вы не можете использовать рекурсию, проблем нет. Существуют версии quick sort recursion-less.

Answer 7

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

Answer 8

В PHP, что-то вроде

function intersect($X) { // X is an array of arrays; returns intersection of all the arrays 
    $counts = Array(); $result = Array(); 
    foreach ($X AS $x) { 
    foreach ($x AS $y) { $counts[$y]++; } 
    } 
    foreach ($counts AS $x => $count) { 
    if ($count == count($X)) { $result[] = $x; } 
    } 
    return $result; 
} 

Answer 9

в 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 10

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

Answer 11

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

Дополнительно, Eviews имеет свой собственный пользовательский форум - почему бы не спросить there_

Answer 12

с множеством 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 13

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

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

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

Answer 14

Из определения Big-Oh обозначений:

Т (N) = O (F (N)), если существуют положительные константы с и п 0, что Т (N) ≤ ср (N), когда N ≥ n 0.

На практике это означает, что если эти два списка относительно невелики по размеру, говорят, что менее 100 элементов в каждой из двух циклов работают очень хорошо. Завершите первый список и найдите аналогичный объект во втором. В моем случае это работает просто отлично, потому что у меня не будет больше 10 - 20 максимальных элементов в моих списках. Однако хорошее решение - это сортировка первого O (n log n), сортировка второго также O (n log n) и объединение их, другое O (n log n), грубо говорящее O (3 n log n), скажем что два списка имеют одинаковый размер.

Answer 15

Использование skip pointers и SSE instructions может улучшить эффективность пересечения списков.