1

quicksortOCamlで実装しました。コードは次のとおりです。

let shuffle d =
    let nd = List.map (fun c -> (Random.bits (), c)) d in
    let sond = List.sort compare nd in
    List.map snd sond;;

let partition = function
  | [] -> ([], [], [])
  | pivot::tl ->
    let rec p (left, right) = function
      | [] -> (left, right, [pivot])
      | first::rest ->
    let c = compare pivot first
    in 
    if c > 0 then
      p (first::left, right) rest
    else 
      p (left, first::right) rest
    in
    p ([], []) tl;;

let quicksort l =
  let sl = shuffle l 
  in
  let rec qs = function
    | [] -> []
    | l ->
      let (left, right, pivot) = partition l
      in 
      (qs left) @ pivot @ (qs right)
  in 
  qs sl;;

まず、パーティションを実装するためのより良い方法があると思います。List.partition頭に浮かんだのですが、自分でキー部分を実装したかっただけです

第二@に、私はソートで多くのことを使用しinefficientますよね?

助言がありますか？

編集

考えるべきもう 1 つの質問は3-way quicksort、OCaml での実装に影響するかどうかです。

4

2 に答える 2

2

試すことができるマイクロ最適化は List.concat[[qs left]; [pivot]; [qs right]]、リストを一度に追加することですが、これが役立つことを確認するには、いくつかのベンチマークを実行する必要があります。

于 2013-02-26T21:58:58.393 に答える
2

p関数がひどくインデントされています。inインデントといえば、次の行に a を付けるスタイルは、1 行の宣言ではやり過ぎだと思う傾向があるので、1 行の宣言の最後に配置します。

さらに重要なことは、リストのタプルを引数として取る必要がないということです。2 つの別個の (カリー化された) 引数を使用すると、構文的に軽いものになります。List.partition標準ライブラリの関数を使用することもできます。

于 2013-02-26T21:49:42.067 に答える