동적 간격 스케줄링을 위해 이러한 OCAML 기능을 최적화하려면 어떻게합니까?

Question

가중치를 해결하는 프로그램이 있습니다 동적 프로그래밍을 사용한 간격 스케줄링 문제 (그리고 믿거 나 말거나, 숙제를위한 것이 아닙니다). 나는 그것을 프로파일 링했고, 나는 대부분의 시간을 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);
    | [] -> ();;

나는 이것을 최적화하는 방법을 실제로 생각할 수 없으며,이 알고리즘에 대한 나의 지식을 바탕으로 이것은 가장 많은 시간을 할애 할 가능성이있는 것 같습니다. 그러나 이것은 또한 나의 두 번째 OCAML 프로그램 일뿐입니다. 그렇다면 이것을 최적화 할 수있는 방법이 있습니까?

Answer 1

두 기능에는 분명히 비효율적 인 것이 없습니다. 예를 들어 다른 언어의 구현과 관련하여 구현이 더 빠를 것으로 기대 했습니까?

나는 목록이 전달 된 것에 대해 궁금했다 get_highest_nonconflicting. 이 기능이 이전에 전달 된 목록과 물리적으로 동일한 목록이 종종 전달 될 것으로 예상 할 이유가있는 경우 (여기에는 재귀 통한 통과에 전달 된 서브리스트가 포함됩니다) 캐시가 도움이 될 수 있습니다.

동일하지만 육체적으로 다른 목록을 기대하면 해시 소싱 (및 캐싱)이 도움이 될 수 있습니다.