Comment optimiser ces fonctions ocaml pour la planification d'intervalle dynamique?

Question

J'ai un programme qui permet de résoudre le interval scheduling problem using dynamic programming pondéré (et croyez-le ou non, ce n'est pas pour les devoirs). Je l'ai profilé, et il me semble que je passe le plus clair de mon temps à remplir M avec p (...). Voici les fonctions:

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); 
    | [] ->();; 

Je ne peux pas vraiment penser à des façons d'optimiser cela, et ma connaissance de cet algorithme, cela semble être l'endroit qui est susceptible de prendre le plus de temps. Mais c'est aussi mon deuxième programme OCaml. Alors, y a-t-il un moyen d'optimiser cela?

Answer 1

Il n'y a rien évidemment inefficace avec vos deux fonctions. Vous attendiez-vous à ce que votre implémentation soit plus rapide, par exemple en référence à une implémentation dans une autre langue?

Je me demandais sur les listes transmises à get_highest_nonconflicting. Si vous avez des raisons de penser que cette fonction est souvent des listes passé qui sont physiquement identiques aux listes précédemment passés (et cela inclut les sous-listes transmises appels récursifs), un cache, il pourrait aider.

Si vous prévoyez des listes qui sont égales mais physiquement différents, hachage consing (puis la mise en cache) pourrait aider.