OCaml에서 두리스트를 교차시키는 방법은 무엇입니까?

Question

내가 예를 들어 OCaml의 두 목록을 가질 때

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

및

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

두 목록의 교차를 얻을 수있는 효율적인 방법이 있나요? 즉 :

[3; 5; 7] 

내가 이렇게 큰 순서의 오 N^2를 생성, 목록 E1의 모든 요소에 대한 목록 E2의 모든 요소를 ​​스캔 좋아하지 않기 때문에.

Answer 1

Franck와 Rémi가 말했듯이, 목록을 stdlib 모듈 세트 (set)로 변환하면 n log (n) 비용이 들게되고 Sets는 선형 교차 구현을 제공합니다. Franck는 또한 목록을 정렬하고 동기화 된 방식으로 트래버스하는 동등한 대안을 언급했습니다. 이들은 거의 동일합니다 (그리고 두 경우 모두 목록의 요소에 대한 전체 순서를 제공 할 수 있어야합니다).

교차로가 알고리즘의 중요한 부분이고 약간 다른 두 세트의 요소의 경우 교차가 더 빠르도록하려면 패트리샤 나무와 같은 구조로 전환해야합니다 (구조로 전환해야 함). 파일 pt*을 http://www.lri.fr/~filliatr/ftp/ocaml/ds/에 보아라.

모든 경우에 교차가 빠르면 해시가있는 패트리샤 트리를 사용할 수 있습니다. Hash-consing은 구조적으로 동일한 하위 트리를 인식하고 비교 작업을 저렴하게하여 이전 작업에 효율적인 캐시를 구축하는 데 도움이됩니다.

패트리샤 나무는 임의의 유형을 키로 사용할 수 없습니다 (일반적으로 int는 키로 표시됩니다). 그러나 때로는 키로 사용할 각 값을 생성시 번호 매기기로이 제한을 피할 수 있습니다.

Answer 2

나는 OCaml의을 (구문 현명) 모르겠지만, 일반적으로 두 가지 방법으로이 작업을 수행 할 수 있습니다 : 언어가 설정-자료 구조에 대한 지원이있는 경우

이

1. , 다음 세트에 두 목록을 변환 설정 교차 연산을 사용하십시오.

2. 더 일반적으로 : 두 목록을 모두 정렬 한 다음 정렬 된 목록을 스캔하면 훨씬 더 효율적으로 사본을 찾을 수 있습니다. 정렬을 위해 n log (n)을 취하면 선형 시간에 중복을 찾을 수 있습니다.

Answer 3

내 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 
      ) 
     );; 

(N + m) 시간 O에서 실행해야합니다. 기본적으로 각 목록의 첫 번째 요소를 확인합니다. 그것들이 동일하면 재귀 호출의 결과를 꼬리에 저장 한 다음 저장된 결과의 머리가 목록의 머리와 같은지 확인합니다. 그렇지 않으면 삽입하고, 그렇지 않으면 중복되어 무시합니다.

등가가 아닌 경우 더 작은 쪽이 앞으로 나아갑니다.

@Frank는 이제까지 가장 좋은 대답은 아니지만, 여기에 목록이 OCaml이 달성 될 수있는 방법을 보여주는 짧은 코드이지만, 당신은이 문제를 해결하기 위해 세트를 사용할 수있는 제안으로

Answer 4

:

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

출력은 :

1) (Y)의 크기의 논리 값의 배열을 작성

3 
5 
7 
- : unit =() 

Answer 5

내리스트 제한된 크기의 정수를 포함하는 경우는, 또한 O의 수용액 (N)가 원래 목록의 1보다 큰 정수 값 (예 : 귀하의 예에서 '9 + 1'); 모든 필드를 false로 설정하십시오.

let m = Array.create 10 false

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

2) 반복 처리는 첫 번째 목록을 통해 : 발생할 모든 요소에 대해, '사실'로 오프셋 (offset) 각각에 부울을 설정; 귀하의 예제에서이 얻을 것이다

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]