「アルゴリズム」の記事一覧

• リザーバーサンプリングとは何か

  2025-05-08 17:02

  科学・技術

  リザーバーサンプリングは、データ総数が事前に分からない場合でも、公平にランダムサンプリングを行うアルゴリズムです。1件ずつ流れてくるデータから一定数をメモリ効率良く選ぶことができ、ログ収集などにも応用可能です。仕組みは、n番目の要素が選ばれる確率を1/nとすることで、すべてのデータに均等な選択機会を与えます。複数の要素を選ぶ場合も拡張可能です。

• 強化学習の古典技法をPythonで実装

  2025-05-06 22:43

  科学・技術

  このGitHubリポジトリでは、Sutton著『強化学習入門』に基づいた様々な強化学習アルゴリズムがPythonで実装されています。マルチアームバンディットからモンテカルロ法、TD学習、方策勾配、Actor-Critic法まで網羅的に収録。基本的な遷移関数を定義することで各手法を実行可能であり、学習目的の利用に適しています。プロダクション用途ではないものの、強化学習の学習や実験には有用なリソースとされています。

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

  2025-05-05 09:25

  科学・技術

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

• メモリアクセスがプログラム性能に与える影響とは

  2025-05-05 03:29

  科学・技術

  アルゴリズムの性能を評価する際に使う「Big O」記法は便利ですが、メモリアクセスの違いまでは考慮しません。現代のCPUは階層的なキャッシュ構造とプリフェッチ機能を備えており、アクセス順によって処理速度が大きく異なります。この記事では、メモリを連続して読む場合とランダムに読む場合での処理時間の差を実験を通じて検証。配列の使い方やデータ構造の選択が、性能に大きな影響を与えることを示しています。

• 浮動小数点乱数を正確に生成する新アルゴリズム

  2025-05-04 14:56

  科学・技術

  多くのプログラミング言語で使われている乱数生成アルゴリズムは、浮動小数点数を正確には扱えず、[0, 1)の範囲でも一部の値しか生成できない問題があります。この記事では、全ての浮動小数点数の範囲をカバーし、ビットごとの偏りもなく、丸めモードにも対応した新しいアルゴリズムを紹介しています。計算効率も高く、シミュレーションや数値計算における乱数の精度向上に貢献するものです。

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

  2025-05-02 03:46

  科学・技術

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