問題タブ [circular-buffer]

Cに循環型の静的に割り当てられたバッファーがあり、これを幅優先探索のキューとして使用しています。キューの上位N個の要素を並べ替えてもらいたいのですが。通常のqsort（）を使用するのは簡単ですが、循環バッファであり、上位N個の要素がラップアラウンドする可能性があります。もちろん、モジュラー演算を使用し、配列をラップする方法を知っている独自のソート実装を作成することもできますが、ソート関数を作成することは良い演習であると常に考えていましたが、ライブラリに任せたほうがよいでしょう。

私はいくつかのアプローチを考えました：

1. 別の線形バッファーを使用します。最初に循環バッファーから要素をコピーし、次にqsortを適用してから、コピーして戻します。追加のバッファーを使用するということは、追加のO（N）スペース要件を意味します。
   • qsortを使用して「上」と「下」の半分を並べ替えてから、追加のバッファーを使用してそれらをマージします
   • 2.と同じですが、インプレースで最終的なマージを実行します（インプレースマージについてはあまりわかりませんが、私が見た実装では、スペースの複雑さを軽減する価値はないようです）

一方、25行（またはそれ以上）を追加する代わりに、自分のクイックソートをエレガントに作成しないようにする方法を1時間かけて検討することも、最も生産的ではない可能性があります...

訂正： DFSとBFSを切り替えるという愚かな間違いを犯しました（私はDFSを書くことを好みますが、この特定のケースではBFSを使用する必要があります）。混乱して申し訳ありません。

元の問題の詳細：

私は幅優先探索を実装しています（15パズルと同じように、より複雑で、各状態で4ではなく約O（n ^ 2）の拡張が可能です）。「ブルートフォース」アルゴリズムは実行されますが、「愚か」です。各ポイントで、すべての有効な状態がハードコードされた順序で展開されます。キューは循環バッファ（unsigned queue [MAXLENGTH]）として実装され、整数インデックスを状態テーブルに格納します。インデックスをキューに入れたりデキューしたりする2つの単純な関数を除けば、カプセル化はありません。これは、静的に割り当てられた符号なしの単純な配列です。

次に、ヒューリスティックをいくつか追加します。私が最初に試したいのは、拡張後に拡張された子の状態を並べ替えることです（「より良い順序で拡張する」）。これは、単純なベストファーストDFSをプログラミングする場合と同じです。このために、キュー（最新の展開された状態を表す）に参加し、ある種のヒューリスティックを使用してそれらをソートしたいと思います。状態を別の順序で展開することもできます（したがって、この場合、キューのFIFOプロパティを壊してもそれほど重要ではありません）。

私の目標は、 A *、または深さ優先探索ベースのアルゴリズムを実装することではありません（すべての状態を拡張する余裕はありませんが、実装しないと、状態空間での無限サイクルの問題が発生し始めるため、反復深化のようなものを使用する必要があります）。

これよりも循環バッファーの残りのスペースを計算する簡単な (単一の) 方法があるかどうか疑問に思っていましたか?

この宿題を誰かにやってもらうように頼んでいるわけではありませんが、C# とスレッド化の実用的な入門書として非常に優れているので取り上げますが、同時に、少し単純すぎると感じています。

これは本当にスレッドを教える最良の方法ですか? この演習で「失われた」主要なスレッド化の概念は何ですか?初めてスレッドを使用する新しいプログラマーが観察できない可能性があるものは何ですか?

私はスレッド化について多くの理論的知識を持っていますが、過去に自分で多くのことをする必要はありませんでした.それを書くときに誰かが私に警告がありますか?

ここに元の課題へのリンクがあります

目標のテキストは次のとおりです。

1) スレッドセーフな汎用循環キュー クラスを作成し、それを使用する GUI を作成します (次のセクションを参照)。このコンテキストでは、スレッド セーフとは、データの破損を避けるために、キューの内容を変更する各操作 (メソッド) を一度に 1 つのスレッドだけで実行する必要があることを意味します。循環キューは、キューの先頭と末尾が配列内のインデックスである固定サイズの配列として実装されます。キューがいっぱいになると、要素が追加されるにつれてキューの最初と最後がより高い値にシフトし、最終的には配列の最初のインデックスにラップアラウンドしてメモリを再利用します。このクラスは、操作が無効な場合、呼び出し元に例外 (以下で指定) もスローする必要があります。

2) プロデューサー/コンシューマー方式で 2 つのスレッドを制御する GUI を作成します。GUI は、プロデューサー スレッドとコンシューマー スレッドの両方を開始、開始、停止し、GenericCircularQueue を変更する速度を制御できます。

あらゆるタイプのオブジェクトを保持できる固定サイズ（コンパイル時ではなく、実行時に選択可能）の循環バッファーが必要であり、非常に高性能である必要があります。マルチタスクの組み込み環境ではありますが、タスク自体がそれを管理できるように協調的な環境であるため、リソース競合の問題は発生しないと思います。

私の最初の考えは、タイプ（単純な列挙型/定義）とペイロードへのvoidポインターを含む単純な構造体をバッファーに格納することでしたが、これをできるだけ速くしたいので、バイパスを含む提案を受け入れますヒープ。

実際、私は生の速度のために標準ライブラリのいずれかをバイパスすることを嬉しく思います-私が見たコードから、それはCPU用に高度に最適化されていません：彼らはちょうどそのようなもののためにCコードをコンパイルしたようですstrcpy()、手作業でコーディングされたアセンブリ。

コードやアイデアをいただければ幸いです。必要な操作は次のとおりです。

• 特定のサイズのバッファを作成します。
• 尻尾に置きます。
• 頭から取得します。
• カウントを返します。
• バッファを削除します。

Ring Buffer のウィキペディアのエントリには、メモリの一部に隣接する仮想メモリが同じ物理メモリにマップされ、 memcpyなどを必要とせずにリング バッファを実装するUNIXシステムのハックを示すサンプル コードがあります。 Windowsで似たような方法がある場合は?

ありがとう、フレイザー

CircularBuffer IDictionary が必要です。誰かが私に良いオープンソースの実装を教えてくれますか?

したがって、最大容量を持つ IDictionary は、たとえば 100 項目に構成され、項目 101 が追加されると、元の最初の項目がディクショナリからポップ/削除されるため、項目数が 100 を超えないようにします。

ありがとう

JavaScript で循環バッファを実装した人はいますか? ポインタなしでどうやってそれをしますか？

私の主な目的は、転送に使用できる汎用データ バッファーを用意することです。

XCopy が行ったことに沿った何かを考えています。

すでに作成されているもの、または従うことができる良い例はありますか?

さまざまな長さのアイテムをフラッシュチップの循環キューに格納する必要があります。各アイテムにはカプセル化されているので、アイテムの大きさと次のアイテムの始まりを把握できます。バッファに十分なアイテムがある場合、最初にラップされます。

フラッシュチップに循環キューを格納するための良い方法は何ですか？

何万ものアイテムを保管したい可能性があります。したがって、バッファの最初から最後まで読み取ることは、最後まで検索するのに時間がかかるため、理想的ではありません。

また、円形なので、最初のアイテムと最後のアイテムを区別できるようにする必要があります。

最後の問題は、これがフラッシュに保存されることです。そのため、各ブロックの消去には時間がかかり、各ブロックに対して設定された回数しか実行できません。

Javaで、イベントのストリーム上にスライディングウィンドウを実装しています。したがって、次のことを実行できるデータ構造が必要です。

1. 新しいイベントが発生したときにデータ構造の最後に追加します。

2. 古いイベントが処理されるときにデータ構造の先頭から削除します。

3. データ構造の要素への標準のランダムアクセス（size()、 ）を取得します。get(i)一般に、一般的なリストの「読み取り」操作。

4. 上記のすべての操作に効率的です。

5. 無制限です。

他のアクセスは必要ありません。また、スレッドセーフは必要ありません。

私は現在、物事を稼働させるために、 ArrayListを使用してこれを行っています。しかし、私はもっと効率的なものが欲しいです。方法（上記のremove(0)2.）は、。を使用すると非効率的ArrayListです。

番号1と2は、標準のキュースタイルの操作です。ただし、QueueJDKでの実装（ArrayDequeなど）では、3では許可されていませんget(i)。

ですから、そのような実装があり、商用利用に適したライブラリが世の中にあるのではないかと思います。

そうでなければ、私は自分で書くことに頼ると思います...