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

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

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

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

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

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

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

, Так как Вы знаете немного о своих данных заранее, необходимо смочь выбрать хорошую хеш-функцию.

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

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

Во-первых, вид оба списка с помощью quicksort: 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 размеры списков.

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

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

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

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

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

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

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