2

Jason Hickey による Introduction to Objective Camlから、末尾再帰マップ関数があります。

let rec rev_accum result = function  
    h::tl -> rev_accum (h :: result) tl
    | [] -> result

let rec rec_map f result = function
    h :: tl -> rec_map  f (f h :: result)   tl 
    | [] -> result 

let map1 f l = rev_accum  [] ( rec_map f [] l )

リストを 2 回トラバースします。この代替案を検討してください。

let rec rec_map2 f result = function
    h :: tl -> rec_map2  f ( result @[f h]) tl 
    | [] -> result 

let map2 f l = rec_map2 f [] l ;

2 番目のものは最初のものよりも速くなりますか?

4

1 に答える 1

3

リストの最後に繰り返し追加すると、リストの最終的な長さが 2 次になる時間がかかります。別の言い方をすれば、リストをn回トラバースするということです。これは簡単に 2 回以上になる可能性があります。そのため、2 番目の実装は一般的にはるかに遅くなります。最初の実装は、リストを 2 回トラバースしますが、線形です。

(もちろん、関数のパフォーマンスはわかりませんf。)

于 2015-08-15T05:33:41.927 に答える