3

動的計画法を使用して加重間隔スケジューリングの問題を解決するプログラムがあります（信じられないかもしれませんが、宿題用ではありません）。私はそれをプロファイリングしました、そして私は私の時間のほとんどを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);
    | [] -> ();;

これを最適化する方法を実際に考えることはできません。このアルゴリズムに関する私の知識に基づくと、これは最も時間がかかる可能性が高い場所のようです。しかし、これは私の2番目のOCamlプログラムでもあります。では、これを最適化する方法はありますか？

4

1 に答える 1

2

2つの機能に明らかに非効率なものはありません。たとえば、別の言語での実装を参照する場合など、実装が高速になることを期待していましたか？

に渡されるリストについて疑問に思っていましたget_highest_nonconflicting。この関数が以前に渡されたリストと物理的に同一のリストが渡されることが多いと予想する理由がある場合（これには再帰呼び出しで渡されるサブリストが含まれます）、そこにキャッシュが役立つ可能性があります。

等しいが物理的に異なるリストが必要な場合は、ハッシュコンシング（およびキャッシュ）が役立つ可能性があります。

于 2009-11-04T14:04:41.170 に答える