Ocaml에서 임의로 요소를 선택할 수 있습니까?

Question

OCaml에서 만든 프로그램에서, 거대한 문자열 집합에서 임의로 문자열을 선택해야합니다. 지금까지이 작업을 수행하는 데있어 두 가지 다른 방법을 시도했지만 거의 성공하지 못했습니다. 내가 먼저 목록에 문자열을 모두 저장 한 후 무작위로 목록에서 요소를 선택합니다 :

let randomelement l = 
    List.nth l (Random.int (List.length l)) 

그러나이 목록에서 1000 문자열을 선택하면이 시간이 오래 걸립니다. 그래서 나는 Set.choose이 세트에서 무작위 요소를 리턴 할 것이라고 생각하면서 모든 것을 세트로 집어 넣었습니다. 그러나 그것은 작동하지 않는 것 같습니다. 나는 두 가지 질문이 있다고 생각합니다 ... Set.choose은 어떻게 작동하며 Ocaml에서 임의로 요소를 선택하는 더 좋은 방법입니까?

Answer 1

선택 속도가 걱정되면 다른 컨테이너를 사용해야합니다. Array를 O (1), 즉 일정 시간으로 사용할 수있는 경우 O (n) 또는 O (log n)로 액세스 할 수있는 List를 사용하는 이유는 무엇입니까?

은 예를 조정하려면

let randomelement arr = 
    let n = Random.int (Array.length arr) in 
    Array.get arr n;; 

Answer 2

먼저, 도우미 기능을 대체 할 수있는 List.nth 기능이 있습니다. 지금까지이 가속화 등

(나는 그것이 당신의 도우미 함수가 같은 일에 대해 수행 확신하기 때문에이 빨리되지 않을 것하지만)

let n = Random.int (List.length lst) in 
    List.nth n lst ;; 

간다 : 경우 수의 문자열은 고정되어 있으므로 Array에 대한 액세스 시간이 일정하기 때문에 작업 속도가 상당히 빨라지는 Array를 사용할 수 있습니다.

Answer 3

아니오, Set.choose는 결정적이며 설명서에 명시되어 있다고 생각합니다. 현재 구현에서는 최소 요소를 반환한다고 생각합니다.

어떤 데이터 구조가 처음에 저장된 문자열 집합입니까? 무작위 요소를 얻는 쉬운 방법은 가지고있는 다른 문자열의 수를 세고, 그 사이에 임의의 숫자 K를 선택하고, 가지고있는 "K 번째 문자열"을 얻는 것입니다. 이는 일부 데이터 구조 (예 : 배열의 경우 일정 시간 작동)에서 효율적으로 수행 할 수 있고 다른 경우에는 효율적으로 수행하지 않을 수 있습니다.

Answer 4

Set.choose은 Set.min_elt의 별칭입니다. 미래에는 그렇지 않을 수도 있습니다.

List.nth 매우 자주해야하는 경우 반드시 빨아 들여야합니다.

배열은 훌륭하게 작동하지만 더 많은 요소를 추가하거나 요소를 삭제해야 할 경우 책 관리의 악몽이 될 수 있습니다.

Random Access Lists의 구현을 살펴보십시오.이 배열은 배열에 제약을받지 않고 삽입, 삭제, 조회 및 기본 작업에 매우 적합한 시간을 제공합니다.

내가 원래이 문제로 실행

, 나는 random 및 nth를 포함 Set 및 Map의 구현을 확장했다. 모듈을 확장하려면 구조를 다시 구현하고 두 함수간에 변환 할 신원 기능을 추가해야합니다.

module Make (Ord : Set.OrderedType) = 
    struct 
     include Set.Make(Ord) 

     type impl = Empty | Node of impl * elt * impl * int 

     external impl_of_t : t -> impl = "%identity" 
     external t_of_impl : impl -> t = "%identity" 

     ... 
    end 

당신은 정상 Set 함수를 호출, 또는 전달되는 납치범 전달 된 인수에서 개인들 전화를 impl_of_t 그 반대를 사용해야 할 것입니다 : 나는 다음과 같은 상투적으로 XSet라는 새 모듈을 썼다 함수에 Set.Make의 구현은 t이 아니라 impl이어야합니다.

Answer 5

Set.choose은 주어진 세트에 대해 매번 동일한 요소를 선택할 것을 보장합니다. 선택하는 요소는 지정되지 않지만 소스 코드를 보면 최소 요소가 반환된다는 것을 알 수 있습니다.

가장 좋은 방법은 배열을 사용하는 것입니다. 대신에 불변의 데이터 구조를 원한다면, 정수형을 사용하는지도를 제안 할 것입니다.

Answer 6

귀하의 질문은 당신이 문자열을 포함하고있는 구조를 준비하기를 항상 원한다는 것을 의미합니다. 그러면 세트를 변경하지 않고 무작위로 여러 번 선택하게됩니다.

이것이 맞다면 배열에 저장하는 것이 좋습니다. 이렇게하면 무작위 요소에 가장 빨리 액세스 할 수 있습니다 (임의 인덱스를 선택하면 직접 액세스 할 수 있습니다). 집합과리스트 구현은 임의의 인덱스 i를 선택하면 i 번째 요소에 액세스하는 것이 불편합니다 (단, 집합의 경우 불규칙한 임의성을 갖는 임의의 선택에 신경 쓰지 않으면 이진 트리에서 임의의 경로를 선택할 수 있음) 구현 외부에서 그렇게 할 수는 없지만 복사하여 붙여넣고 모듈 안에 함수를 추가 할 수 있습니다.