Wie optimiere ich diese OCAML -Funktionen für die dynamische Intervallplanung?

Question

Ich habe ein Programm, das das Gewicht löst Intervallplanungsproblem mit dynamischer Programmierung (Und ob Sie es glauben oder nicht, es ist nicht für Hausaufgaben). Ich habe es profiliert und verbringe die meiste Zeit damit, M mit P (...) zu füllen. Hier sind die Funktionen:

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

Ich kann mir keine Möglichkeiten vorstellen, dies zu optimieren, und basierend auf meinem Wissen über diesen Algorithmus scheint dies der Ort zu sein, der wahrscheinlich die meiste Zeit in Anspruch nimmt. Dies ist aber auch nur mein zweites OCAML -Programm. Gibt es also eine Möglichkeit, dies zu optimieren?

Answer 1

Mit Ihren beiden Funktionen gibt es offensichtlich etwas ineffizient. Haben Sie erwartet, dass Ihre Implementierung schneller ist, beispielsweise in Bezug auf eine Implementierung in einer anderen Sprache?

Ich habe mich über die Listen gefragt, die an verabschiedet wurden get_highest_nonconflicting. Wenn Sie Gründe zu erwarten haben, dass diese Funktion häufig übergeben wird, sind Listen, die physisch identisch mit zuvor bestandenen Listen sind (und dies schließt die Unterlisten ein, die rekursive Anrufe verabschiedet haben), ein Cache kann helfen.

Wenn Sie erwarten, dass Listen gleich, aber physisch unterschiedlich sind, können Hash-Consing (und dann das Caching) helfen.