Как мне пересечь два списка в OCaml?

Question

Когда у меня есть два списка в OCaml, например

e1 = [3; 4; 5; 6; 7]

и

e2 = [1; 3; 5; 7; 9]

Есть ли эффективный способ пересечения этих двух списков? I.e.:

[3; 5; 7]

Поскольку я не люблю сканировать каждый элемент в списке e2 для каждого элемента в списке e1, таким образом создавая большой Oh порядка n ^ 2.

Answer 1

Как сказали Франк и Реми, преобразование ваших списков в наборы (из модуля Set в stdlib) стоит n log (n), а затем Sets обеспечивает линейную реализацию пересечения. Франк также упомянул эквивалентную альтернативу, чтобы отсортировать списки, а затем пройти их синхронизированным способом. Они примерно одинаковы (и, между прочим, в обоих случаях вам необходимо обеспечить полное упорядочение элементов в ваших списках).

Если пересечения являются важной частью вашего алгоритма и вы хотите, чтобы они были быстрее в случае двух наборов элементов, которые немного отличаются друг от друга, вам нужно переключиться на объединяемую структуру, такую ​​как Патриция деревья. Смотрите файлы pt* в http://www.lri.fr/~filliatr/ftp/ocaml/ds/.

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

Деревья Патриции не могут использовать произвольный тип в качестве ключа (обычно они представлены с целочисленными значениями в качестве ключей). Но иногда вы можете обойти это ограничение путем нумерации при создании каждого значения, которое вы намерены использовать в качестве ключа.

Answer 2

Мой OCaml не самый лучший, но я взломал эту функцию, которая будет пересекать отсортированные списки:

let rec intersect l1 l2 =
    match l1 with [] -> []
        | h1::t1 -> (
          match l2 with [] -> []
              | h2::t2 when h1 < h2 -> intersect t1 l2
              | h2::t2 when h1 > h2 -> intersect l1 t2
              | h2::t2 -> (
                match intersect t1 t2 with [] -> [h1]
                    | h3::t3 as l when h3 = h1 -> l
                    | h3::t3 as l -> h1::l
              )
        );;

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

Если они не равны, он просто продвигается в зависимости от того, кто меньше.

Answer 3

Как подсказал @Frank, вы можете использовать наборы для решения этой проблемы, хотя это не самый лучший ответ, но вот короткий список кода, демонстрирующий, как этого можно достичь в OCaml:

module Int_set = Set.Make (struct
                             type t = int
                             let compare = compare
                           end);;

(* iters through a list to construct a set*)
let set_of_list = List.fold_left (fun acc x -> Int_set.add x acc) Int_set.empty;;

let e1 = [3; 4; 5; 6; 7];;
let e2 = [1; 3; 5; 7; 9];;

let s1 = set_of_list e1;;
let s2 = set_of_list e2;;

(*result*)
let s3 = Int_set.inter s1 s2;;


(*testing output*)
Int_set.iter (fun elt -> print_int elt;print_string "\n") s3;;

Вывод:

3
5
7
- : unit = ()

Answer 4

Я не знаю OCaml (по синтаксису), но обычно вы можете сделать это двумя способами:

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

2. В более общем плане: сортируйте оба списка, затем сканируйте отсортированные списки, что делает поиск дубликатов намного более эффективным. Вы берете n log (n) для сортировки и можете найти дубликаты за линейное время.

Answer 5

Если ваши списки содержат только целые числа ограниченного размера, в O (n) также есть решение:

1.) Создайте массив логических значений размера наибольшего целочисленного значения плюс 1 в исходных списках (например, в вашем примере «9 + 1»); установите для всех полей значение false;

let m = Array.create 10 false

-> [|false; false; false; false; false; false; false; false; false; false|]

2.) Итерация по первому списку: для каждого элемента, с которым вы столкнетесь, установите логическое значение с соответствующим смещением равным 'true'; в вашем примере это даст

List.iter (fun x -> m.(x) <- true) e1

-> [|false; false; false; true; true; true; true; true; false; false|]

3.) Отфильтровать второй список, сохранив только те элементы, для которых соответствующее поле в массиве имеет значение true

List.filter (fun x -> m.(x) = true) e2

-> [3; 5; 7]

Answer 6

Я не думаю, что мое решение - O (n), но оно очень короткое и может быть интересным для людей, которые не ограничены сложностью (поскольку этот ответ является одним из первых результатов поиска для "Ocaml intersect list «)

Эта функция возвращает true, если пересечение не пустое. Другими словами, он проверяет, имеют ли два списка общие элементы, если да, true, иначе false.

let intersect l1 l2 =
    List.fold_left (fun acc x -> if (List.exists (fun y -> y = x) l1) then true else acc) false l2;;

Очень похоже, что эта функция возвращает фактическое пересечение.

let intersect l1 l2 =
    List.fold_left (fun acc x -> if (List.exists (fun y -> y = x) l1) then x::acc else acc) [] l2;;

Не стесняйтесь поправлять меня, если мой солутон неверен. Это должен быть полиморф, поскольку x и y могут быть любыми типами, которые можно сравнивать.