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

Question

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

Answer 1

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

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

Answer 2

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

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

Answer 3

Из определения обозначения Big-Oh:

T (N) = O (f (N)), если существуют положительные постоянные c и n 0, такие что T (N) ≤ cf (N), когда N ≥ n 0.

Что на практике означает, что если два списка относительно малы по размеру, скажем, что менее 100 элементов в каждом из двух циклов for работают нормально. Зациклите первый список и найдите похожий объект во втором. В моем случае это работает просто отлично, потому что в моих списках не будет более 10 - 20 элементов max. Однако хорошим решением является сортировка первого O (n log n), сортировка второго также O (n log n) и объединение их, еще один O (n log n), грубо говоря O (3 n log n), говорят два списка имеют одинаковый размер.

Answer 4

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

Answer 5

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