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

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

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

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

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

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

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

в 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;
}

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

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

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

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

В 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;
}

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