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

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

вопрос задан 30.01.2009
does_not_exist
репутация

15 ответов

  • 31 рейтинг

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

    ответ дан Frank, с репутацией 27789, 30.01.2009
  • 20 рейтинг

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

    ответ дан Aneil Mallavarapu, с репутацией 2192, 23.05.2010
  • 9 рейтинг

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

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

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

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

    ответ дан zvrba, с репутацией 20495, 23.05.2010
  • 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, с репутацией 61, 21.04.2011
  • 6 рейтинг

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

    vector set_intersection(vector s1, vector s2){

    vector ret;
    map 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, с репутацией 61, 7.05.2010
  • 3 рейтинг

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

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

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

    ответ дан Ayman Farhat, с репутацией 1066, 4.01.2013
  • 2 рейтинг

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

    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, с репутацией 12893, 30.01.2009
  • 1 рейтинг

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

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

    ответ дан Andrea Ambu, с репутацией 16338, 30.01.2009
  • 1 рейтинг

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

    ответ дан Nosredna, с репутацией 57359, 31.01.2009
  • 1 рейтинг

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

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

    ответ дан Imran, с репутацией 4930, 30.01.2009
  • 0 рейтинг

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

    ответ дан Wolf Garbe, с репутацией 152, 16.06.2016
  • 0 рейтинг

    Из определения Биг-О нотации:

    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, с репутацией 6671, 19.10.2015
  • 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;
}
    ответ дан does_not_exist, с репутацией , 16.07.2009
  • -1 рейтинг

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

    ответ дан StingyJack, с репутацией 15253, 30.01.2009