如何爲動態間隔調度優化這些ocaml函數？

Question

我有一個程序，解決加權interval scheduling problem using dynamic programming（並相信與否，它不是作業）。我已經介紹過它，而且我似乎花費了大部分時間用p填充M（...）。下面是功能：

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的列表。如果您有理由期望該函數經常通過與之前傳遞的列表物理上相同的列表（並且這包括遞歸調用傳遞的子列表），那麼緩存可能會有所幫助。

如果您希望列表相同但物理上不同，則哈希引用（然後高速緩存）可能會有所幫助。