Эффективный алгоритм пересечения списка
С учетом двух списков (необязательно отсортированных), каков наиболее эффективный нерекурсивный алгоритм для поиска пересечения этих списков?
16 ответов
Вы можете поместить все элементы первого списка в хэш-набор. Затем выполните итерацию второго и для каждого из его элементов проверьте хеш, чтобы увидеть, существует ли он в первом списке. Если это так, выведите его как элемент пересечения.
Возможно, вы захотите взглянуть на фильтры Bloom. Это битовые векторы, которые дают вероятностный ответ о том, является ли элемент членом набора. Задание пересечения может быть реализовано с помощью простой побитовой операции И. Если у вас есть большое количество нулевых пересечений, фильтр Блума может помочь вам быстро их устранить. Однако вам все равно придется прибегнуть к одному из других алгоритмов, упомянутых здесь, чтобы вычислить фактическое пересечение. http://en.wikipedia.org/wiki/Bloom_filter
Без хеширования, я полагаю, у вас есть два варианта:
- Наивным способом будет сравнение каждого элемента с каждым другим элементом. O(N ^2)
- Другой способ - сначала отсортировать списки, а затем выполнить итерации по ним: O(n lg n) * 2 + 2 * O(n)
Из списка возможностей eviews кажется, что он поддерживает сложные слияния и объединения (если это "соединение", как в терминологии БД, он вычислит пересечение). Теперь покопайтесь в вашей документации:-)
Кроме того, eviews имеет свой собственный пользовательский форум - почему бы не спросить там?
В 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;
}
С набором 1 построить двоичное дерево поиска с O(log n) и итерации set2 и искать BST m X O(log n) итого O(log n) + O(m)+O(log n) ==> O(log n)(m+1)
Вот еще одно возможное решение, которое я придумала: использование O(nlogn) во временной сложности и без дополнительной памяти. Вы можете проверить это здесь https://gist.github.com/4455373
Вот как это работает. Предполагая, что наборы не содержат повторений, объедините все наборы в один и отсортируйте их. Затем переберите объединенный набор и на каждой итерации создайте подмножество между текущим индексом i и i+n, где n - количество наборов, доступных в юниверсе. То, что мы ищем в цикле, - это повторяющаяся последовательность размером n, равной количеству множеств в юниверсе.
Если это подмножество в i равно этому подмножеству в n, это означает, что элемент в i повторяется n раз, что равно общему количеству множеств. И поскольку в любом наборе нет повторений, это означает, что каждый из наборов содержит это значение, поэтому мы добавляем его в пересечение. Затем мы сдвигаем индекс на i +, что остается между ним и n, потому что определенно ни один из этих индексов не будет образовывать повторяющуюся последовательность.
Сначала отсортируйте оба списка с помощью быстрой сортировки: 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 Размеры списков.
РЕДАКТИРОВАТЬ: быстрая сортировка является рекурсивной, как сказано в комментариях, но похоже, что есть нерекурсивные реализации
Использование указателей пропуска и инструкций SSE может повысить эффективность пересечения списков.
Если есть поддержка наборов (как вы их называете в заголовке) как встроенных, то обычно существует метод пересечения.
Во всяком случае, как кто-то сказал, вы можете сделать это легко (я не буду публиковать код, кто-то уже сделал это), если у вас есть отсортированные списки. Если вы не можете использовать рекурсию, нет проблем. Существуют быстрые сортировки без рекурсии.
Почему бы не реализовать собственную простую хэш-таблицу или хэш-набор? Это стоит того, чтобы избежать пересечения nlogn, если ваши списки большие, как вы говорите.
Поскольку вы заранее знаете немного о своих данных, вы сможете выбрать хорошую хэш-функцию.
Я придерживаюсь идеи "множеств". В JavaScript вы можете использовать первый список для заполнения объекта, используя элементы списка в качестве имен. Затем вы используете элементы списка из второго списка и посмотрите, существуют ли эти свойства.
Из определения Big-Oh обозначений:
T (N) = O (f (N)), если существуют положительные постоянные c и n 0, такие что T(N) ≤ cf(N), когда N ≥ n 0.
Что на практике означает, что, если два списка относительно малы по размеру, скажем, что в каждом из двух циклов примерно 100 элементов, то это прекрасно работает. Зациклите первый список и найдите похожий объект во втором. В моем случае это работает просто отлично, потому что в моих списках не будет более 10 - 20 элементов max. Однако, хорошим решением является сортировка первого O(n log n), сортировка второго также O (n log n) и объединение их, еще один O(n log n), грубо говоря O (3 n log n), скажем, что два списка имеют одинаковый размер.
В 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;
}
Время: O(n) Пространство: O(n) Решение для определения точек пересечения.
Например, два заданных узла будут определять точку пересечения, меняя местами указатели каждый раз, когда они достигнут конца. Пояснение к видео здесь.
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
Я получил от этого несколько хороших ответов, которые вы можете применить. У меня пока нет возможности попробовать их, но, поскольку они также охватывают перекрестки, вы можете найти их полезными.