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

algorithm list set-intersection

72359 просмотра

15 ответа

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

Источник Размещён: 12.11.2019 09:07

Ответы (15)


36 плюса

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

Автор: Frank Размещён: 30.01.2009 09:39

22 плюса

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

Автор: Aneil Mallavarapu Размещён: 23.05.2010 04:22

9 плюса

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

  • Наивным способом будет сравнение каждого элемента с каждым другим элементом. O (N ^ 2)
  • Другой способ - сначала отсортировать списки, а затем выполнить итерации по ним: O (n lg n) * 2 + 2 * O (n)
Автор: Tom Ritter Размещён: 30.01.2009 09:49

7 плюса

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

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

Автор: zvrba Размещён: 23.05.2010 04:56

6 плюса

с набором 1 построить двоичное дерево поиска с O(log n)и итерации set2 и искать BST m X O(log n)итогоO(log n) + O(m)+O(log n) ==> O(log n)(m+1)

Автор: khaja Размещён: 21.04.2011 02:23

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;
}
Автор: quasar Размещён: 07.05.2010 04:41

3 плюса

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

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

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

Автор: Ayman Farhat Размещён: 04.01.2013 07:55

2 плюса

Сначала отсортируйте оба списка с помощью быстрой сортировки: 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являются размеры списков.

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

Автор: Wookai Размещён: 30.01.2009 09:47

2 плюса

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

Автор: Wolf Garbe Размещён: 16.06.2016 02:11

1 плюс

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

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

Автор: Imran Размещён: 30.01.2009 09:53

1 плюс

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

Автор: Nosredna Размещён: 31.01.2009 10:55

1 плюс

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

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

Автор: Andrea Ambu Размещён: 30.01.2009 09:54

0 плюса

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

Автор: StingyJack Размещён: 30.01.2009 09:51

0 плюса

В 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;
}
Автор: Размещён: 16.07.2009 12:47

0 плюса

Из определения 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), скажем, что два списка имеют одинаковый размер.

Автор: Adelin Размещён: 19.10.2015 10:08
Вопросы из категории :
32x32