Как я пересекаю два списка в OCaml?
Когда у меня есть два списка в OCaml, например
e1 = [3; 4; 5; 6; 7]
и
e2 = [1; 3; 5; 7; 9]
Существует ли эффективный способ получить пересечение тех двух списков? Т.е.:
[3; 5; 7]
Поскольку мне не нравится сканировать каждый элемент в списке e2 для каждого элемента в списке e1, таким образом создавая большое, О, порядка n^2.
4 ответа
Как сказали Франк и Реми, преобразование ваших списков в наборы (из модуля stdlib Set) стоит n log (n), а затем Sets обеспечивает линейную реализацию пересечения. Франк также упомянул эквивалентную альтернативу для сортировки списков, а затем синхронизированного просмотра их. Они примерно одинаковы (и, кстати, в обоих случаях вам нужно иметь возможность обеспечить полное упорядочение элементов в ваших списках).
Если пересечения являются важной частью вашего алгоритма и вы хотите, чтобы они были быстрее в случае двух наборов элементов, которые лишь немного отличаются, вам необходимо переключиться на объединяемую структуру, такую как Patricia деревья. См. Файлы pt * в http://www.lri.fr/~filliatr/ftp/ocaml/ds/ .
Если вам нужно, чтобы пересечение было быстрым во всех случаях, у вас есть возможность использовать деревья Патрисии с обработкой хешей. Хеширование помогает распознавать структурно идентичные поддеревья и помогает создавать эффективные кеши для предыдущих операций, делая сравнение дешевым.
Деревья Патрисии не могут использовать произвольный тип в качестве ключа (обычно они представлены с целыми числами в качестве ключей). Но иногда это ограничение можно обойти, пронумеровав при создании каждое значение, которое вы собираетесь использовать в качестве ключа.
Как предложил @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 = ()
Мой 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). В основном она проверяет первый элемент каждого списка. Если они равны, она сохраняет результат рекурсивного обращения к их хвостам, а затем проверяет, равна ли голова сохраненного результата головам списков. Если нет, то вставляет его, иначе это дубликат, и он игнорируется.
Если они не равны, то просто продвигается тот, который меньше.
Я не знаю OCaml (с точки зрения синтаксиса), но, как правило, вы можете сделать это двумя способами:
Если ваш язык поддерживает структуру Set-data, конвертируйте оба списка в Наборы и используйте операцию пересечения множеств.
В более общем плане: отсортируйте оба списка, а затем просканируйте отсортированные списки, что значительно упрощает поиск дубликатов. Вы берете n log (n) для сортировки и тогда можете найти дубликаты за линейное время.