プログラミングの基礎 saitan_wo_bunriの高速化

ちょっと本の話題とは、脇道にそれました。saitan_wo_bunri関数を次のように定義していて

et saitan_wo_bunri xs = match xs with
| [] -> ([], []) 
| first::rest 
   -> let min = List.fold_right 
                (fun k data -> if k.saitan_kyori < data.saitan_kyori then k else data) 
                rest first  
in ([min], (List.filter (fun x -> x <> min) xs)) 

これだと計算回数がO(2n)で少しタコなプログラムで、気になってはいたのですが、話題が高速化の話になってきたので、ここらで高速化しようと次のように変更しました

let saitan_wo_bunri xs = match xs with
| [] -> ([], []) 
| x::xs 
  -> List.fold_right
       (fun elm tuple -> match tuple with
       | ([], _) -> ([elm], [])
       | (min::nil, data) 
       -> if min.saitan_kyori < elm.saitan_kyori 
        then ([min], elm::data)
        else ([elm], min::data))
       xs
       ([x], [])

これだと計算回数はO(n)回で前回よりも高速に動作するはずです。そのかわりxsの順番が入れ替わるというよくない影響もあります。関数の仕様通り最短の駅を取り出す事には、成功するのですが、dijkstra関数の中に、入れるとなんだかよからぬ動きをするようです。なんでだろう。わかんない。。明日は、この関数の変更の影響を見ていきたいと思います。
ちょっと風邪気味で、体調がよくないです。（昨日もブログ休んでしまった。。）

プログラミングの基礎 ((Computer Science Library))