キャッシュフレンドリーな二分探索 ー データ構造を再考する | POSTD
現代のコンピュータのアーキテクチャに搭載されている高速のキャッシュメモリは、 参照の局所性 に優れた(＝一連のものとしてアクセスした要素が、互いに近いメモリのアドレスに配置されている)データ構造を好みます。これは、 Boost.Containerの平坦な（ツリー状ではない）連想コンテナ のようなクラスを陰で支えている理論的根拠です。要素を連続的に（かつ順序だてて）保存すると同時に、標準的なC++ノードベースの連想コンテナの機能性をエミュレートします。以下にあるのは、要素が0から30の範囲の時、 boost::container::flat_set の中で 二分探索 がどのように行われるのかを示した例です。 探索で目的の値を絞り込むにつれて、アクセスされる要素は次第に近くなっていきます。そのため、最初のうちは大きな距離を飛び越えていくような感じであっても、参照の局所性は このプロセスの最後の
The Implementation of epoll (1)
In this series of blog posts, I will be taking notes about the internals and implementation details of the Linux event poll (epoll) subsystem. Prerequisites Please note that I am assuming the audiences of those articles are familiar with epoll APIs and usages. I will be focusing on the actual kernel implementation of the epoll subsystem, not it's usages. If you are not familiar with the usage of e
Left-leaning Red-Black Trees (PDF)
Robert Sedgewick is the founding chair and the William O. Baker Professor in the Department of Computer Science at Princeton University. He was a member of the board of directors of Adobe Systems from 1990 to 2016, served on the faculty at Brown University from 1975 to 1985, and has held visiting research positions at Xerox PARC, IDA, and INRIA. His research expertise is in algorithm science, data
Java8からはHashMapの性能のためにComparableを実装しておいた方がいい - interprism's blog
こんにちは、andoです。 ついにJava8がリリースされたのでさっそくインストールしてみました。 Java8になってラムダ式を始め、多くの機能が追加されたのですが、既存機能についても性能改善が行われています。 人気がありそうな新機能の紹介は他の人にお任せして、今回はHashMapの変更点について確認したいと思います。 はたして既存のプログラムはJava8で実行するだけで、その恩恵を享受できるのでしょうか。 java.util.HashMap HashMapといえば使用頻度1、2を争うコレクションクラスでデータの検索、追加がO(1)で行え、 辞書的に使える事から簡易的なDTOやキャッシュ、データベースのレコード構造、さらにはListですむところでさえ数値をキーにして使う兵もいるというくらい良くも悪くも色々使えます。 それが速くなるのであれば、既存のプログラムも速くなるはず、ということでさっ
Left-leaning Red-Black Trees - やた＠はてな日記
いろいろなところで引用されています．実装が楽な赤黒木で，以下のスライドを見れば（むしろ，ほとんどコピーする感じで），簡単に実装できます． 論文 http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf スライド http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf 以下は，少し普通じゃない感じで，とりあえず追加のみを実装してみたものです．64 ビット環境だとポインタに割り当てられる領域も無視できないことがあったりなかったり，という思いが反映されています．ただし，試作品なので少しだけ…． template <typename ValueType, typename IndexType = unsigned, typename LessThanType = less<ValueType>,
DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう 赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか） 赤黒木というのは動的データ構造
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.
Google Code Archive - Long-term storage for Google Code Project Hosting.
Introduction to Citrusleaf | DBMS 2 : DataBase Management System Services