RINGバッファー-2Dケース

RING（リング）バッファー-2Dケース。

！ガイド付きのフル機能の新しいモジュール、記事の最後にあるgithubへのリンク！



長い間、私はHabrにデモシーンの趣味やアルゴリズムを使った実験から集めたいくつかのアルゴリズムトリックを書いていました。 私にとってHabrはまさにそのような記事に興味があるので、興味深いアルゴリズムの異常な使用の古い学校の精神でそれが判明することを願っています。



データ構造RINGバッファー（リングバッファー）は、ネットワークプロトコルの実装および同時実行構造（ストリーム間のデータ同期）で最もよく見られます。



この記事では、クライアント側のJavaScriptでの実装を解析したいと思います。 この言語は非常に人気があり、私はそれを使って多くの練習をしています。 例として、これは実際のエリアまたはゲームのエリアのマップを操作するために適用できます。



循環バッファとは何か、抽象アルゴリズムとして提供するものから始めましょう。





1.リングバッファを使用すると、メモリの動的な再配布から逃れることができますが、同時に、データの効果的な順次追加と削除を整理できます。 特に、JS（およびガベージコレクタを備えたすべての言語）の場合、これは後者の作業を削減することを意味し、パフォーマンスにプラスの効果があります。



2.リングバッファーを使用すると、データ配列全体をシフトする必要がある場合に、データの実際の動きから逃れることができます。

配列push（elem）を操作するJSメソッドの場合、elem = pop（）がネイティブに実装され、配列の末尾から要素を追加および取得し、unshiftをシフトします。 残念ながら、配列の先頭を操作する場合、メソッドは基本的にデータの実際の変更を処理します。これは、JSデータ処理がハッシュマップに基づいているためです。 また、曖昧さのために、コンパイラは常に構造を最適化できるとは限りません。 実際、ほとんどの場合、最新のコンピューターの速度はそのような実装に十分です。 しかし、以下で分析する例では、もう少し先に進みます。



ここで何が面白いと思う？ 事実、標準的なリングバッファーアルゴリズムは、分析する2Dの場合（3Dおよび一般的に配列の任意の次元）に著しく適応します。



このような構造の一般化は新しいものではないと確信していますが、インターネットでその説明を見つけられず、自分で実現しました。



-バッファオブジェクトは、実際のデータのストレージをカプセル化し、一定サイズの2次元配列として提示します。

-問題のアルゴリズムは、2次元データ（たとえば、場所のシームレスな読み込みを伴うゲームカードの表面上のデータ）を追加/読み取りできます。

-プッシュメソッドは、方向に関係なく、実際に読み込まれた要素の数O（n）のみに依存し、バッファーO（n ^ 2）には依存しない時間で機能します。nは正方形バッファーの辺の長さです。 必要に応じて、マルチパス（ストリーミング）バッファーを埋めても、追加の負荷はかかりません。



最初に、外部から（「スライディングウィンドウ」から）バッファがどのように見えるかを見てみましょう。







この図は、バッファと同じサイズのウィンドウがスライドに対してスライドする様子を示しています。



このウィンドウの下にあるのは、空間の範囲を指します。 より大きなバッファ用に実装することもできます。 （これは、位置データのストリーミングプリロードに関連するため、データはウィンドウ内の実際の表示より先にロードされます）。 ウィンドウには、ゲームワールドの座標内に位置点X0、Y0があり、幅Wと高さH（この実装では、2の累乗に等しく、互いに等しくなります）があります。 赤い線は、バッファの「継ぎ目」を示します。 図では、わかりやすくするために中央に配置されています。 インデックスを見ると、バッファ内の実際のデータ位置がわかります。 ウィンドウがシフトされると、データはバッファ内のセルを移動せず、代わりに「シーム」が配置されます。



このような操作と同時に、データが不要になったウィンドウの視野から出たデータセルは、ウィンドウが移動する側にあり、新しいデータセルを発行する側にあることがわかります。 これは、1つの操作で古いデータを削除し、新しい=を書き込むプロセスをリンクします。 ウィンドウに新しいデータを書き込むことは残っています。 シームの場所に関係なく、バッファAPIはメモリ内の正しいマッピングを処理します。 実際には、データを自動的に「プッシュ」するプッシュ（データ）操作の4つのモードを実装します。



実装：



任意のバッファーサイズをサポートする方法を含め、さまざまな方法でアルゴリズムを作成できますが、最適化のためにこれをすべて開始したので、ビット単位の操作による実装を示します。 オーバーヘッドの唯一の制限は、2の累乗に等しいバッファのサイドのサイズを使用する必要があることです。 これは、ゲームエンジンでは非常に一般的な方法です。



次のパターンに注意して厳密に定義します。



表示ウィンドウが移動しても、バッファは移動しませんが、隣接するゾーンからのデータで徐々に補充されます。 これらのゾーンは、バッファーのサイズの倍数であるグリッドによって空間に配置されます。



このグリッドが世界地図上の（0,0）を通過するように、世界座標からバッファーの初期位置を決定することに同意します。



私の雄弁さにあまり依存していないので、説明の写真を同封しています。





（太い赤い線はワールドゼロを示します）



この追加の抽象化の有用性は、それだけではありません。



-セルに分類されるデータの世界座標は常に同じ場所に分類されますが、

-座標は指定されたゾーンに相対的であるため、このデータを格納する際の柔軟性が高まります。 これらは、モノリシックに格納することも、クラスタサーバーの実装まで部分的に格納することもできます。



実際、サーバー上のカードが非常に大きい場合、確かに同様のものが必要になります。 したがって、これは優れた拡張性ブックマークです。



しかし、主な理由に戻ります。 辺のサイズが2の倍数であるバッファーの場合のこのような実装により、世界座標の相対座標への変換、またはその逆の変換が簡単になります。 この場合の相対座標が常に絶対の最下位ビットにあるためです。 また、上位ビットにはゾーンの座標があります。



通常、低レベルのアルゴリズムでは、ビット単位の演算が最も高速であるため、ビット単位の演算による実装に努めることが非常に望ましいです。 一部のアーキテクチャでは、追加よりもさらに高速です（これはほとんどの場合、マイクロコントローラに当てはまります）。

<script> var Buffer2d = function(side){ //   (! !)  . var x0 = 4, y0 = 4, //   ,   .1 (4,4) msk = side - 1, //  ,      buffer = []; while( buffer.push( new Array(side) ) < side ); //  ...  JS     . //     ,          . for(var y = 0; y < side; y++) // DEBUG:       : for(var x = 0; x < side; x++) buffer[y][x] = x + ',' + y; return { get : function (x,y){ return buffer[y + (y0 & msk) & msk][x + (x0 & msk) & msk]; } } } var side = 8; var myBuf = Buffer2d(side); for(var y = 0, n = 0; y < side; y++, console.log(str)) // DEBUG:       .1 for(var str = ++n + '\t\t\t', x = 0; x < side; x++) str += myBuf.get(x,y) + '\t'; </script>
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この段階で、ベンチマークは、API関数Buffer2d.get（x、y）を介したバッファーへの順次アクセスを使用して、図1の類似物をコンソールに発行します。



ここで、新しいデータをバッファにプッシュする機能を直接追加します。 まず、ダイナミックレンダーが必要です。

 onkeydown = function(e){ var vect = { 37 : -1, //lookup table -         38 : -side, 39 : +1, 40 : +side}[ (e || window.event).keyCode ]; if(vect===undefined) return; for(var data = [], n = 0; data.push(n++) < side;); myBuf.push(data, vect); console.log('\n'); for(var y = 0, n = 0; y < side; y++, console.log(str+'')) for(var str = ++n + '\t\t\t', x = 0; x < side; x++) str += myBuf.get(x,y) + '\t'; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

vectパラメーターとは何ですか？



変位ベクトルは、変位ビットの水平および垂直の合計として記録されます。

-この形式により、単一の変位だけでなく、別のベクトル、たとえば斜めにさらに明確に示すことができます。



次に、最も難しい部分を記述する必要があります（ただし、適用されたアルゴリズムのビット操作が「ファッショナブルではない」ために複雑に見えるかもしれませんが）。



コードのこの部分では、バッファシフトにより値が不要になるセルにすべての受信データを配置する必要があります。 ここでは、ビット演算の動作メカニズムについては説明しません。このトピックでは、別の記事を取り上げます。

このコードを理解するには、「マスクでビットを取る」などの操作を理解することで十分であり、この実装では、2の累乗を「モジュロを取る」ことに似ていると言えます。



Buffer2dコンストラクターによって返されるオブジェクトにメソッドを追加します。

  push : function(data, vect){ // vect   +-1  right|left, +-side  down|up var dx = ((vect + side / 2) & msk) - side/2, dy = (vect - dx) / side; x0 += dx; y0 += dy; for(var y = Math.min(0, -dy), y2 = Math.max(0, -dy), n = 0; y < y2; y++, n += side) buffer[y0 + y & msk] = data.slice(n, side); //     for(var x = Math.min(0, -dx), x2 = Math.max(0, -dx), y2 = y + side; x < x2; x++) for(; y < y2; y++) buffer[y0 + y & msk][x0 + x & msk] = data[n++]; //    }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードを実行してみたい場合は、ブラウザで開発者ツールを開くことを忘れないでください。

コードがテストされ、すべてが機能し、バッファーがコンソールに表示されます！ キーボードの矢印コントロール。



バッファ用に記述されたAPIが一度に複数のセルをシフトできることに気づいた場合-このケースではユニットテストを実施しませんでしたが、可能です！



それがおそらくすべてです。 私は明確に書き込もうとしました。 コメントに書いてください。エラーに気づかなかった場合、私はアドバイスにとても満足しています。 記事があなたを喜ばせることを願っています



githubの 新機能