高速なキューを作る話（前編） - Qiita
私が以前Haskellで作成した（割と自己満足な）kazura-queueという比較的高速なキューのライブラリがあります。 このライブラリを作るときに考えたアレコレを書いてみたいと思います。 前提 ここでいうキューって何？ データ構造としてのキュー（Sequenceみたいな）や分散処理用のキュー？（RabbitMQみたいな）ではなく、並行処理のためにスレッド間の部品として使うようなキュー（Chan（やTQueueやTChan）みたいな）を意図しています。 ここではChanが持っているキューとしての性質をざっと書き出してみましょう。 キューに入るデータの型は任意 Chan aという型で表現できる範囲で好きなデータを入れることができる。 FIFO キューなのだから当たり前といえば当たり前かもしれませんが一応。 スレッドセーフ 複数のスレッドが同時に書き込もうとしても問題が起きない。1 複数のス
なぜ Haskell ではキューが軽んじられているか？ - あどけない話
Haskell ではキューが欲しくなったら Data.Sequence を使えと言われる。Seq は両端キューだし、シーケンスとして使えば、連結(><)や分割(splitAt)が、ならし計算量で O(log N) という優れものである。しかし、内部がfinger treeなのでコードが複雑なのと、計算量が「ならし」なところが玉に傷である。 もっと単純で、最悪計算量を保証する(両端でない)キューが標準で提供されてもいい気がする。その候補には、リアルタイムキューがある。どうして標準でキューが提供されないのだろう？ 僕なりの答えは「需要がない」だ。 問題を解くときにスタックはよく使うが、キューが必要な問題はそんなに思いつかない。僕はネットワーク屋なので、もちろんルータにはキューが必要なことは知っているが、それ以外で有名どころと言えば幅優先探索ぐらいだ。 幅優先探索 でも、Haskellではキュー
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
