2

queue.ml は、リンクされたリスト (変更可能なフィールドを含む) に基づいて実装されているため、かなり遅くなる傾向があることに気付きました。

たとえば配列のような、より高速な構造を持つキューを構築することは可能ですか?

または、より良いパフォーマンスを達成する方法はありますが、それでも機能的な方法ですか?

編集 : 1 ミリ秒未満で数万のエンキューおよび配信操作を行うパブリッシュ サブスクライブ ソリューションを実装したいので (グラフィック インタラクティブ アプリケーションの場合)、非常に高速なものが必要であり、ocaml キューの実装ではパフォーマンスのニーズが満たされませんでした。

4

2 に答える 2

5

リンクリストベースの実装が遅いと思う理由を知ることは興味深いでしょう. これはキューの古典的な実装です。挿入と削除は、私が想像できるほど高速です (1 つまたは 2 つの参照フィールドを更新します)。あなたが話しているコードを見ていないことに注意してください。

配列を使用してリング バッファーを実装できます。いくつかのこと（すべての要素をトラバースするなど）では高速かもしれませんが、最大サイズがあります（最も簡単な実装の場合）。配列の初期化にも複雑さがあります。

一般的に言えば、データ構造の関数型 (不変) の実装は、対応する命令型 (可変) のバージョンよりも少し遅くなります。優れたパフォーマンスを発揮する非常に優れた関数型キューの実装があります。基本的なトリックは、キューの半分を正順 (高速削除用) に、半分を逆順 (高速挿入用) に保つことです。私が言ったように、逆転のための余分なパスは小さなペナルティをもたらします.

メモリ (割り当てと GC) を見ている場合、不変のアプローチが最も多く割り当て、従来の方法は中程度の量であり、リング バッファーはほとんど割り当てません。しかし、適切な FP 実装 (OCaml など) では、メモリの割り当てが非常に高速になり、オブジェクトの寿命が短い場合でもメモリの再利用が遅くなりません。

編集：ラップトップ（3.06 GHz Intel Core 2 Duo）で非常に大雑把なタイミングテストを実行したところ、標準の OCaml Queue モジュールを使用して 70 ミリ秒で 100 万の値をキューに入れたり取り出したりすることができました。したがって、10,000 を実行するのに約 0.7 ミリ秒かかります (これが正しければ)。あなたの CPU が私のものよりも速くなければ、あなたが望むことをするのに十分な速さではないようです。

編集 2:値をキューに入れるために使用できる既存の参照フィールドが値にあると想定するコードを手書きしました。これにより、キューイングコードでの割り当てが回避されますが、それ以外は標準の Queue モジュールに似ています (ただし、はるかに洗練されていません)。上記と同じラップトップでは、100 万回のキューとデキューに約 48 ミリ秒かかります。なので少し早いです。

編集 3:今では答えが得られている可能性が非常に高いですが、上で概説した純粋なキューの実装を使用して大まかなタイミング テストを実行したところ、100 万回のキューとデキューを実行するのに約 18 ミリ秒かかりました。そのため、かなり高速です。OCamlは純粋な計算用に調整されているため、これはもっともらしいです。これが私のコードです。エラーがないか確認できます。

type q = {
    head: int list;
    tail: int list;
}

let q_add q i =
    { q with tail = i :: q.tail }

let q_take q =
    match q.head with
    | [] ->
        begin
        match List.rev q.tail with
        | [] -> raise Not_found
        | h :: t -> (h, { head = t; tail = [] })
        end
    | h :: t -> (h, { head = t; tail = q.tail })

let main () =
    let q = q_add { head = []; tail = [] } 0
    in let now = Unix.gettimeofday ()
    in let rec go q i =
        if i > 1_000_000 then
            q
        else
            let (_, q') = q_take (q_add q i)
            in
                go q' (i + 1)
    in let _ = go q 1
    in let duration = Unix.gettimeofday () -. now
    in
        Printf.printf "%f\n" duration

let () = main ()

私が言ったように、これは大雑把なテストです。キューは、長さが 1 要素と 2 要素の間で交互に繰り返されます。結果があなたの環境で保持されるかどうかはわかりません。しかし、それは興味深いです。

于 2012-05-06T14:55:44.700 に答える
4

キュー操作の特定の実装がどれほど非効率的であるかを実際に定量化するには、操作を測定する必要があります。

とはいえ、さまざまなキューシナリオに対応する代替データ構造があります。特に、永続キューまたは純粋キュー、あるいは並行キューに関心がある場合は、いくつかのオプションがあります。

純粋なデータ構造

並行キュー

パブリッシュサブスクライブ

パブリッシュ/サブスクライブメカニズムを検討している場合は、zeromqへのバインドを検討してください。

それは間違いなく高周波操作を目的としており、FPコミュニティ（http://www.zeromq.org/bindings:haskell ）を支援しています。

ZeroMQへの2つの異なるOCamlバインディングがあります：http ：//www.zeromq.org/bindings：ocaml

于 2012-05-06T17:37:07.803 に答える