「データ構造」の記事一覧

• CRDTは“セミラティス”でできている

  2025-05-23 02:29

  科学・技術

  この記事では、分散システムで使用されるCRDT（Conflict-Free Replicated Data Types）の内部設計を、数学的に信頼性のある「セミラティス」構造に基づいて説明しています。仮定や依存性を暗黙にせず、必要な因果関係や状態の圧縮もセミラティス内に明示的に組み込むことが求められます。例としてOR-Setの安全な状態削除手法やバージョンベクターの利用が紹介され、正しい設計によって確実な収束性が保証されることが強調されています。

• VS Codeのテキストバッファ再実装の舞台裏

  2025-05-20 09:34

  IT・ネット

  Visual Studio Codeは、バージョン1.21で新たなテキストバッファ実装を導入しました。旧来の行配列方式では大規模ファイルに対応できず、Out-Of-Memoryエラーが頻発していました。新実装は“ピースツリー”と呼ばれるデータ構造を用い、複数バッファ＋赤黒木を活用することで、読み込み速度とメモリ使用量を大幅に改善。ネイティブコードではなくTypeScriptでの最適化を選択した経緯や、実装上の課題と工夫も詳細に述べられています。

• Wavelet Tree入門：ランククエリと圧縮の両立

  2025-05-15 15:27

  科学・技術

  Wavelet Treeは、複雑な文字列に対してランククエリを高速に実行しながら圧縮も可能にするデータ構造です。アルファベットを階層的なビットベクトルに分解することで、ログ時間で任意の文字の出現回数を取得できます。この記事では構造の再帰的構築法、ランククエリの実行手順、さらに圧縮手法RRRとの併用によりメモリ効率も確保できる点をわかりやすく解説しています。

• Rustで実装するロックフリー配列の極限設計

  2025-05-13 16:43

  科学・技術

  本記事はRustで固定長のロックフリー配列を実装する詳細な技術解説です。AtomicPtrやAtomicUsizeを用い、freelistによるインデックス管理を実現。メモリオーダリングの選定やABA問題の回避手法にも触れ、スレッド間で高速に値の挿入・削除が可能な構造を構築しています。ロックによる待機を排除することで、Mutexと比較して平均83％高速化される結果も示されています。安全性と性能を追求する上級者向け内容です。

• コンパクト・エラスティック・バイナリーツリーの設計と応用

  2025-05-05 09:25

  科学・技術

  cebtreeは、最小限のメモリ使用で高速なデータ構造を実現するために設計された、新しい形式のバイナリーツリーです。ノードに親ポインタを持たず、わずか2つのポインタで構成され、空間効率に優れています。重複キー対応、タグ付きポインタ、相対ポインタなどの実装を経て、haproxyの変数や設定における検索効率を向上させる実用性が確認されました。今後は並列処理対応やさらなる汎用性の拡大が期待されています。

• 高速なデータ照合を可能にするBloomフィルターの仕組み

  2025-05-02 03:46

  科学・技術

  Bloomフィルターは、ある要素が集合に含まれているかを高速かつ省メモリで確認できる確率的データ構造です。ビット配列と複数のハッシュ関数を使い、否定の確認には確実性があり、肯定の場合にはごく稀に誤判定が含まれます。Go言語での実装例も紹介され、1秒間に数千万件の検査も可能です。特にアクセスの大半が否定となる用途で真価を発揮します。