functional-programming - OCamlのソート機能は、不変または可変のデータ構造を使用しますか?

Question

OCamlはソートの実装にデータ構造を使用しますmutableか?immutable

多くの並べ替えアルゴリズムでは、リストや配列などの位置間でデータを交換する必要があります。

immutable data structuresOCaml が常に を使用することを意図している場合、交換操作ごとに新しいコピーが作成されるのではないかと思っています。

それは影響しperformanceますか？

Answer 1

多くのソートアルゴリズムでは、リストや配列などの位置の間でデータを交換する必要があります。

必ずしも。

OCamlが常に不変のデータ構造を使用することを意図しているのかどうか疑問に思っています

いいえ、OCamlには可変と不変の両方のデータ構造があります。ただし、一般的には不変のデータ構造を使用することをお勧めします。

次に、各交換操作で新しいコピーが作成されますか？

それは問題のデータ構造に依存します。しかし、一般的に、不変のデータ構造を操作するときに個々の要素を交換するという観点からソートアルゴリズムを表現したくないでしょう（そして、上で示したように、確かにそうする必要はありません）。

List.sortたとえば、不変のデータ構造（リスト）で機能し、完全に効率的です。マージソートアルゴリズムを使用します（OCamlの現在の実装では）。