OCamlの私のプログラムでは、巨大な文字列からランダムに文字列を選択する必要があります。私は今までこれを行う2つの異なる方法を試しましたが、それぞれほとんど成功しませんでした。私が最初にリストにすべての文字列を格納し、その後、無作為にリストから要素を選択します：Ocamlで要素をランダムに選択する方法はありますか？
let randomelement l =
List.nth l (Random.int (List.length l))
しかし、それは、リスト内の1000番目の文字列を選択した場合、これは長い時間がかかります。だから、私はすべてをセットに入れて、Set.chooseがセットからランダムな要素を返すだろうと考えました。しかし、それは動作していないようです。私は2つの質問があると思います...どうすればSet.chooseが動作し、Ocamlの要素をランダムに選択するより良い方法がありますか？
選択速度が気になる場合は、別のコンテナを使用する必要があります。 ArrayをO（1）で、つまり一定の時間で使用できる場合、O（n）またはO（log n）でアクセスできるリストを使用するのはなぜですか？あなたの例を調整する
：
let randomelement arr =
let n = Random.int (Array.length arr) in
Array.get arr n;;
まず、ヘルパー機能を置き換えるList.nth関数があります。
let n = Random.int (List.length lst) in
List.nth n lst ;;
（私はそれだけで、あなたのヘルパー関数が行うように同じことを行いますかなり確信しているので、これは任意の速くないだろうが）限り、これを行くスピードアップなど
：多くの場合あなたが持っている文字列が固定されている場合、配列のアクセス時間が一定であるため、かなり高速化する配列を使用することができます。
ええああはList.nth' 'を忘れてしまった...ありがとう！ – Travis
いいえ、Set.chooseは確定的です。ドキュメントに指定されていると思います。現在の実装では、最小要素を返すと思います。
どのデータ構造が最初に格納された文字列のセットですか？ランダム要素を取得する簡単な方法は、あなたが持っている異なる文字列の数を数え、その間にある乱数Kを選んで、あなたが持っている "K番目の文字列"を得ることです。これは、いくつかのデータ構造（配列の場合は一定時間操作）では効率が良く、他のデータ構造では効率が悪い場合もあります。
ああ、私は配列が一定の時間を持っているか分からなかった...ありがとう！ – Travis
Set.chooseはSet.min_eltの別名です。将来はそうではないかもしれないが。
List.nthあなたは非常に頻繁にそれをしなければならない場合は確かに吸うでしょう。
配列は素晴らしいですが、要素を追加したり、要素を削除したりする必要がある場合は、ブックを保存する悪夢となります。
Random Access Listsの実装を見てみましょう。これらの実装は、配列に制約を受けることなく、挿入、削除、参照、および基数の最適な時間を持っています。
私はもともとこの問題に遭遇したとき、とMapの実装をrandomとnthに拡張しました。モジュールを拡張するには、構造体を再実装し、その2つの間で変換するID関数を追加する必要があります。私は、次の定型で、XSetと呼ばれる、新しいモジュールを書いた：
module Make (Ord : Set.OrderedType) =
struct
include Set.Make(Ord)
type impl = Empty | Node of impl * elt * impl * int
external impl_of_t : t -> impl = "%identity"
external t_of_impl : impl -> t = "%identity"
...
end
あなたは、通常のSet関数を呼び出すためにimpl_of_tおよびその逆を使用する必要があり、または渡さ--what渡された引数からあなたの個人的なものを呼び出します。あなたの関数にSet.Makeの実装tではなく、implする必要があります。
標準ライブラリを拡張する興味深い手法ですが、集合の 'nth'の実装はO（n）ですか？ （あなたも 'iter'を使うかもしれません） –
ええ、私はそうだと思います。私は要素を数えるために順序通りのトラバースを使用しました。 'Map'構造体の'カーディナリティ 'を見つける必要があるときに' Map'モジュールと同様のコードを持っていましたので、物事を取得するのは非常に簡単で、最終的にRALデータ構造に変更されました。 – nlucaroni
コードをもう少し思い出した後、私はO（n）を持たない意図でランダム関数を書いていましたが、結論に至りませんでした。何か案は？ – nlucaroni
Set.chooseは、与えられたセットのたびに同じ要素を選択することを保証します。選択する要素は指定されていませんが、ソースコードを見ると最小要素が返されます。
あなたの最善の策は、配列を使用することです。代わりに不変のデータ構造が必要な場合は、整数をキーとするマップを提案します。
あなたの質問は、文字列を含む構造体を準備しておき、セットを変更することなくランダムに何回も選択することを意味します。
これが正しい場合は、配列に格納することをお勧めします。ランダムな要素に素早くアクセスできるようになります（ランダムなインデックスを選んだら直ぐ）。セットとリストの実装は、あなたがランダムなインデックスiを選んだら、i番目の要素にアクセスするのに不便です（ただし、セットの場合、ランダム性が悪いランダムな選択に気をつけなければ、バイナリツリーでランダムなパスを選ぶことができます実装の外からはできませんが、コピーして貼り付けてモジュール内に関数を追加することができます）。
ああ、私は配列がO（1）時間だったのか分からなかった。それは素晴らしいです、そして、それは私がすることです。ありがとう！ – Travis