Как оптимизировать эти функции ocaml для планирования динамического интервала?

Question

У меня есть программа, которая решает взвешенный interval scheduling problem using dynamic programming (и верьте или нет, это не для домашней работы). Я профилировал его, и я, кажется, трачу большую часть своего времени на заполнение M с помощью 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. Если у вас есть основания ожидать, что этой функции часто передаются списки, которые физически идентичны ранее спискам (и это включает в себя под-списки, переданные по рекурсивным вызовам), кэш там может помочь.

Если вы ожидаете, что списки, равные, но физически разные, могут помочь хеш-consing (а затем кэширование).