タグ

algorithmとGoogleに関するcrafのブックマーク (3)

  • GoogleがB-tree実装のSTLコンテナを公開

    C++ containers that save memory and time cpp-btree - C++ B-tree - Google Project Hosting Googleが、B-tree実装のSTLコンテナー(map, set, multimap, multiset)を発表した。 多くのSTLの実装では、map, set, multimap, multisetは、Red-Black treeで実装されている。Googleの発表によれば、B-tree実装のコンテナーは、赤黒木実装に比べて、速度が上がり、しかもメモリ消費量も削減できるとしている。 紹介まで。 B木は一つのノードに複数の要素を格納する。これにより、ポインターなどのオーバーヘッドを低減でき、メモリ消費量の削減につながる。また、複数の要素を一括してノードに詰め込むため、速度向上もあるのかもしれないが、そのへんはよ

  • Hadoop Streaming - naoyaのはてなダイアリー

    id:naoya:20080511:1210506301 のエントリのコメント欄で kzk さんに教えていただいた Hadoop Streaming を試しています。 Hadoop はオープンソースの MapReduce + 分散ファイルシステムです。Java で作られています。Yahoo! Inc のバックエンドや、Facebook、Amazon.com などでも利用されているとのことです。詳しくは http://codezine.jp/a/article/aid/2448.aspx (kzk さんによる連載記事)を参照してください。 Hadoop Streaming 記事にもあります通り、Hadoop 拡張の Hadoop Streaming を使うと標準入出力を介するプログラムを記述するだけで、Hadoop による MapReduce を利用することができます。つまり、Java 以外

    Hadoop Streaming - naoyaのはてなダイアリー
  • MapReduce - naoyaのはてなダイアリー

    "MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること

    MapReduce - naoyaのはてなダイアリー
  • 1