동적 간격 예약을 위해 이러한 ocaml 함수를 어떻게 최적화합니까?

Question

나는 가중치가 적용된 interval scheduling problem using dynamic programming을 해결하는 프로그램을 가지고있다. (믿거 나 말거나, 숙제가 아니다.) 나는 그것의 윤곽을 잡았고, 나는 대부분의 시간을 P (...)로 채우고있다. 여기에 기능은 다음과 같습니다

let rec get_highest_nonconflicting prev count start = 
    match prev with 
     head :: tail -> 
    if head < start then 
     count 
    else 
     get_highest_nonconflicting tail (count - 1) start 
    | [] -> 0;; 

let m_array = Array.make (num_genes + 1) 0;;  

let rec fill_m_array ?(count=1) ?(prev=[]) gene_spans = 
    match gene_spans with 
     head :: tail -> m_array.(count) <- 
    get_highest_nonconflicting prev (count - 1) (get_start head); 
    fill_m_array tail ~prev:(get_stop (head) :: prev) ~count:(count+1); 
    | [] ->();; 

난 정말이를 최적화 할 수있는 방법을 생각 할 수 없으며,이 알고리즘의 내 지식을 바탕으로,이 대부분의 시간을 걸릴 가능성이 장소가 될 것으로 보인다. 하지만 이것은 제 2 번째 OCaml 프로그램이기도합니다. 그래서 이것을 최적화 할 수있는 방법이 있습니까?

Answer 1

두 기능을 사용하면 분명히 비효율적 인 것은 없습니다. 예를 들어 다른 언어로 구현 된 것과 관련하여 구현이 더 빨라질 것으로 기대 했습니까?

get_highest_nonconflicting에 전달 된 목록에 대해 궁금합니다. 이 함수가 이전에 전달 된 목록과 물리적으로 동일한 목록을 전달하기를 기대하는 이유가 있다면 (그리고 재귀 호출에 전달 된 하위 목록을 포함) 캐시가 도움이 될 수 있습니다.

동일하지만 물리적으로 다른 목록을 기대하는 경우 해시 처리 (및 캐싱)가 도움이 될 수 있습니다.