MultiQueues: Simpler, Faster, and Better Relaxed Concurrent Priority Queues
Priority queues with parallel access are an attractive data structure for applications like prioritized online scheduling, discrete event simulation, or branch-and-bound. However, a classical priority queue constitutes a severe bottleneck in this context, leading to very small throughput. Hence, there has been significant interest in concurrent priority queues with a somewhat relaxed semantics whe
0x5f3759df
This post is about the magic constant 0x5f3759df and an extremely neat hack, fast inverse square root, which is where the constant comes from. Meet the inverse square root hack: float FastInvSqrt(float x) { float xhalf = 0.5f * x; int i = *(int*) &x; // evil floating point bit level hacking i = 0x5f3759df - (i >> 1); // what the fuck? x = *(float*)&i; x = x * (1.5f - (xhalf*x*x)); return x; } What
Binary Search *eliminates* Branch Mispredictions
Searching in a short, sorted vector is a fairly common task. Lots of time, data sets are just small enough that it’s quicker (and simpler) to store them in a sorted vector than to use an alternative with asymptotically faster insertions. Even when we do use more complex data structures, it often makes sense to specialise the leaves and pack more data in a single node. How should we implement such
Bloom Filters
Everyone is always raving about bloom filters. But what exactly are they, and what are they useful for? Operations The basic bloom filter supports two operations: test and add. Test is used to check whether a given element is in the set or not. If it returns: false then the element is definitely not in the set. true then the element is probably in the set. The false positive rate is a function of
Cuckoo Filters
My take on computer science -- algorithms, networking, information theory -- and related items. An upcoming paper appearing at CoNext will be of interest to any Bloom Filter user or aficionado: Cuckoo Filter: Practically Better than Bloom (Bin Fan, David Andersen, Michael Kaminsky, Michael Mitzenmacher) Let me describe a cuckoo filter and some of what's in the paper for you. If you want to avoid
A New Provable Factoring Algorithm
Factoring, factoring, the whole day through, keeps on my mind—apologies to Hoagy Carmichael and Stuart Gorrell Michael Rubinstein is an expert on number theory, who is on the faculty of the University of Waterloo. He is one of the organizers of a 61-birthday symposium being held December 15–19 in Princeton for my friend and former colleague, Peter Sarnak. I guess it is a matter of taste for a numb
木の直径を求めるアルゴリズムの証明 - あんまり見ないでください
非負の距離（重み）を持つ無向の木について，最も遠い頂点間の距離（最遠頂点間距離）を木の直径という．この直径を求めるアルゴリズムは意外と簡単だが，参考サイトの証明ではすっきりできなかったので，自分なりに証明を考えてみる． 参考サイト：http://www.prefield.com/algorithm/graph/tree_diameter.html ＜アルゴリズムの説明＞ 適当な頂点sを選び，sからの最遠頂点uを探索する．次にuからの最遠頂点vを探索する．このとき，(u,v)は木の最遠頂点対となっており，木の直径はuとvの距離と等しい． ＜自分なりの証明＞ uが少なくとも一つの最遠頂点対に含まれることを証明する．基本的な方針は参考サイトと同じ．サイトで理解できなかったところを自分なりに考える． s：任意の頂点 u：sからの最遠頂点 (x,y)：とある最遠頂点対 t：sからuに向かう経路でuと
UpCoder coding blog
Another custom container post for my Vectors and Vector Based Containers series. In this post I'll look at an alternative implementation of the humble bit vector, designed specifically for optimising zero fill operations. It's not a new technique, and not particularly complicated to implement, but it's not completely obvious, and it's something that gave us some noticeable speedups when applied to
"Efficient Graph-Based Image Segmentation"の手法と実装 - IrohaLog
記事概要 1. Felzenszwalbらの提案したEfficient Graph-Based Image Segmentation *1の手法と実装を解説 2. 手法：画像中の各画素を1つのノードとした木から、輝度が類似なノードをまとめていきセグメンテーションを行う 3. 実装：Union-Findを用いることでo(nlogn)となる Felzenszwalbらの提案したEfficient Graph-Based Image Segmentation を解説してみる。 画像のセグメンテーション*2は1枚の画像を同じような特徴(明るさ、色、テクスチャなど)を持つ複数の領域に分割する処理で、基本的な画像処理技術の1つである。画像合成処理、物体認識、ジェスチャ認識などの前処理として幅広く利用されている。 中でも、2004年にFelzenszwalbらが提案したEfficient Graph-B
クワイン・マクラスキー法の実装 - うつし世はゆめ / 夜のゆめもゆめ
誰が興味あるのか知らないけど、諸事情によりPythonでクワイン・マクラスキー法を実装したので公開してみるよ。 https://github.com/takada-at/makurasan クワイン・マクラスキー法とは何か? 論理式を簡単にするアルゴリズムです。詳しくはwikipediaを(日本語の記事わかりにくいけど)。 http://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%AF%E3%82%A4%E3%83%B3%E3%83%BB%E3%83%9E%E3%82%AF%E3%83%A9%E3%82%B9%E3%82%AD%E3%83%BC%E6%B3%95 偉大な哲学者クワインが昼寝をしている内に思いつきました(嘘です)。 一応クワインの原論文もダウンロードしてみたので暇なときに読むかもしれない。 http://www.jstor.org/stable
Trees as Linked Lists in Common Lisp
If you are starting to learn Common Lisp, and have already read the chapter about “Cons” from an introductory book (also called cons cells), then you could try the following exercise. How to represent a tree using nothing but conses; and abstract that implementation with functions to create and traverse the tree. PLEASE NOTE, that if you need to represent trees in a production program you shouldn’
Typical DP Contestまとめ - simezi_tanの日記
これで全部の問題に解説をつけられた。 解くより解説書くほうがめんどい…… りんごさんが主催した全問DPのコンテストの、全問題の解説＆ソースコード記事へのリンクです。 コンテストのページはhttp://tdpc.contest.atcoder.jp/ Typical DP Contest A コンテスト - simezi_tanの日記 Typical DP Contest B ゲーム - simezi_tanの日記 Typical DP Contest C トーナメント - simezi_tanの日記 Typical DP Contest D サイコロ - simezi_tanの日記 Typical DP Contest E 数 - simezi_tanの日記 Typical DP Contest F 準急 - simezi_tanの日記 Typical DP Contest G - 辞書順
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Cuckoo Filter: Practically Better Than Bloom
Binary Trees and Traversals: Everyday Algorithms
Digraphs, Dags, and Trees in Java
Of Berlekamp factorization algorithm
Linked Lists with wait-free reads in C++ (LRLinkedList and LRLinkedListSingle)
Geometric Madness with Jason Davies
Radix Trees Explained: Structure, Applications, and Benefits
http://nuclearhorsestudios.com/