The World's Simplest Lock-Free Hash Table
A lock-free hash table is a double-edged sword. There are applications where it can provide a performance improvement that would be impossible to achieve otherwise. The downside is that it’s complicated. The first working lock-free hash table I heard about was written in Java by Dr. Cliff Click. He released the source code back in 2007 and gave a presentation about it at Google that same year. Whe
wavelet行列で高速な「もしかして友だち？」検索 | 株式会社サイバーエージェント
業務経歴： Sierでのソフトウェア開発・大手メディアでのサービス運用を経て2012年サイバーエージェント入社。 アメーバ事業本部コミュニティサービスの開発責任者を経て、現在はアドテクスタジオで広告配信技術に注力。 好きな分野はグラフ探索とチューリングマシン。 ソーシャルサービスでは、ユーザ間のつながりやユーザ同士の類似性がとても重要です。 つながりの近いユーザや自分と似ているユーザを「もしかして友だち？」とサジェストすることでユーザ間のつながりを伸展させることができます。 そこで、ユーザの「つながり」具合が似ているユーザを「友だちかもしれないユーザ」としてサジェストを行うことを考えました。 しかし「つながり」のデータというのはユーザ数のベキ乗であるため、容量が大きくなりやすい性質があります。 即ち、「つながり」類似度の算出には時間がかかる、ということです。 この「つながり」類似度算出
GitHub - google/cityhash: Automatically exported from code.google.com/p/cityhash
CityHash, a family of hash functions for strings. Introduction ============ CityHash provides hash functions for strings. The functions mix the input bits thoroughly but are not suitable for cryptography. See "Hash Quality," below, for details on how CityHash was tested and so on. We provide reference implementations in C++, with a friendly MIT license. CityHash32() returns a 32-bit hash. CityHash
Data Structure Visualization
Currently, we have visualizations for the following data structures and algorithms: Basics Stack: Array Implementation Stack: Linked List Implementation Queues: Array Implementation Queues: Linked List Implementation Lists: Array Implementation (available in java version) Lists: Linked List Implementation (available in java version) Recursion Factorial Reversing a String N-Queens Problem Indexing
Lock-free Multi-producer Multi-consumer Queue on Ring Buffer
My article "Lock-Free Multi-Producer Multi-Consumer Queue on Ring Buffer" was published by Linux Journal more than 30 days ago, so now I can post it here. Work queue has always been one of the most hot points in server software. Here is how to scale it effectively to multi-core environment. I. INTRODUCTION Nowadays high performance server software (e.g. HTTP accelerator) in most cases runs on mult
ハミング距離の計算はホントに速いのか？
これは@sakanazensen君が主催する『Computer Vision Advent Calendar 2013』の12/8の記事です。今年はあまり活発でないようなので、小ネタですが参戦しました。 はじめに 昨今のコンピュータビジョン・パターン認識分野で特徴ベクトルのバイナリベースの記述法が流行っています。その利点の一つとして、特徴ベクトル間の距離としてコンピュータにとって計算が容易な「ハミング距離」が使える、というものがあります。これはXOR演算と PopCount演算（いくつのビットが1かをカウントする演算）で構成されており、特に近年のCPUにはまず搭載されているベクトル計算命令セットの一つ「SSE4.2」の専用命令「POPCNT」が高速演算の根拠としてよく引き合いに出されます。二つともかなりプリミティブな命令ですから確かに高速に計算できそうな感じはします。しかしながら、例えばL
Quick-sort with Hungarian (Küküllőmenti legényes) folk dance
Created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania. Directed by Kátai Zoltán and Tóth László. In cooperation with "Maros Művészegyüttes", Tirgu Mures (Marosvásárhely), Romania. Choreographer: Füzesi Albert. Video: Lőrinc Lajos, Körmöcki Zoltán. Supported by "Szülőföld Alap", MITIS (NGO) and evoline company. Click the link below to watch this visualization included in the
Replacement Selection Sort v. Selection Sort
This algorithm was described in 1965 by Donald Knuth, so it's designed to work in a very different computing environment than the one we're currently used to. Computers have very little memory (usually, some fixed number of registers), but have access to large external drives. It's common to build algorithms that would load some values into registers, process them there, then flush them directly b
マルコフ連鎖モンテカルロ法入門-１
※ここで解説しているお天気推移モデルはオリジナルなものですので、数値・計算等にミスがある可能性が否めませんので、もし間違いを見かけた方は優しく教えていただけると助かります。 お天気推移モデルで理解するマルコフ連鎖モンテカルロ法。２状態離散モデルの解説を中心に、メトロポリス法の解説まで行った。 次は連続モデルや熱浴法・メトロポリスヘイスティング法の解説資料も作成したい⇒完成。以下のLINKを参照下さい。http://www.slideshare.net/teramonagi/ss-5344006 誤字を修正（2010/11/01）Read less
)
トライ (データ構造) - Wikipedia
"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ木 トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。 キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語
Cache-oblivious algorithm - Wikipedia
In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An optimal cache-oblivious algorithm is a cache-oblivious algorithm that uses the cache optimally (in an asymptotic sense, ignoring constant factors). Thus,
文字列の類似度を測る(4) 置換の起こりやすさとDNA｜Colorless Green Ideas
文字列の類似度を測る際に置換という操作を考えるが、この操作の起こりやすさによって類似度を調整する仕組みがある。この仕組みは言語やDNAの分析にも役立つ。 はじめに 前に文字列の類似度を測る手法として編集距離について紹介した。これは、文字の置換などの編集がどれだけ必要かということに基づいて、文字列の類似度を測る手法である。 しかし、置換と言っても、起こりやすい置換とそうでない置換がある。前に紹介した手法では、置換の起こりやすさについて想定してこなかったが、もし想定したとしたらどうなるかということが今回扱いたい内容である。なお、置換の起こりやすさについての話は、DNAの塩基配列の変化のモデルを例とすると分かりやすいので、それを中心に見ていきたいと思う。 起こりやすい置換とそうでない置換 文字列の中の1文字が別の1文字に置き換わることが置換である。編集距離の1つであるレーベンシュタイン距離では、
文字列の類似度を測る(3) レーベンシュタイン距離の拡張｜Colorless Green Ideas
文字列の類似度を測る単純な尺度としてレーベンシュタイン距離というものがあるが、このレーベンシュタイン距離を拡張した様々な指標について見ていく。 はじめに 以前、文字列の類似度を測る手法として、レーベンシュタイン距離というものを紹介した。これは、ある文字列から別の文字列にする際に挿入・削除・置換を何回行うかに基づいて、文字列の類似度を測る尺度であった。レーベンシュタイン距離は簡便な指標であり、実際色々な分野で使われている。ただ、レーベンシュタイン距離だけでは捉えきれない問題もあって、そういう場合は、レーベンシュタイン距離以外の方法で文字列の類似度を測ることになる。 今回は、文字列の類似度を測るための尺度の中でも、レーベンシュタイン距離を拡張したものについて紹介していきたい。特に、Damerau–Levenshtein距離というものと、距離の標準化の話は重要になってくるので、おさえておくと何か
文字列の類似度を測る(2) 発音に着目する｜Colorless Green Ideas
文字列の表面上の形でなく、発音に注目したい場合に、文字列の類似度をどう測るかについて。具体的には、Soundex と Metaphone という手法を紹介する。 はじめに 前回、文字列の類似度を測る手法として、最小編集距離、なかんずくレーベンシュタイン距離について紹介した。この手法は、表層的な形しか見ていないということに注意することが必要である。言語データの場合、基本的には綴りだけしか見ていないということになる。英語の場合、綴りと音が大きくかけ離れているので、発音がよく似ていても綴りは似ても似つかないということが起こりうる。この場合、発音はよく似ているのに、距離は大きくなってしまうのである。 綴りに着目したい場合もあるが、発音に着目する必要がある場合も当然ある。このような場合、何らかの手法で発音を見える形にする必要がある。英語では、Soundex や Metaphone といったアルゴリズ
文字列の類似度を測る(1) レーベンシュタイン距離｜Colorless Green Ideas
ある文字列と別の文字列の類似度を測る手法の1つである、レーベンシュタイン距離について紹介する。文字列の類似度は検索エンジンやDNAの塩基配列の調査などにも使用されており、応用範囲は広い。 はじめに Googleの検索結果の訂正候補 検索サイトで検索語を間違えて入力してしまった場合、検索エンジンが訂正候補を出してくれることがある。図に掲げた例では、「マクドナルド」と入力しようとして、誤って「マクラナルド」と入力してしまっているが、Google は「マクドナルド」の検索結果を返している。誤ったものを入力すると、その誤ったものと似た正しいものを返しているのである。 このように訂正候補を出すには、まず入力されたものと似ているものを探し出すということが必要になる [1] 。そして、似ているものを探し出すには、何をもって似ているとするのかということを決めなくてはならない。つまり、類似度の尺度が必要とな
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Lock-free Data Structures. The Inside. Memory Management Schemes
Repair-Optimal MDS Array Codes over GF(2)
https://dl.acm.org/citation.cfm?id=1454171
https://dx.doi.org/10.1145/1807167.1807207
Open Source Database Software Support & Services | Percona
