KMCの例会講座で用いたスライドを一部編集したものです。 ビット演算を組み合わせたトリッキーな方法で様々な操作を高速に行う方法を紹介します。
研究動向から考えるx86/x64最適化手法
KMCの例会講座で用いたスライドを一部編集したものです。 ビット演算を組み合わせたトリッキーな方法で様々な操作を高速に行う方法を紹介します。
Sort Benchmark Home Page
New: We are happy to announce the 2023 winners listed below. The new records are listed in green. Congratulations to the winners! Background Until 2007, the sort benchmarks were primarily defined, sponsored and administered by Jim Gray. Following Jim's disappearance at sea in January 2007, the sort benchmarks have been continued by a committee of past colleagues and sort benchmark winners. The Sor
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
w.l.o.g. ギャップバッファ
04:40 04/06/04 ピーステーブル PieceTable とも言う。文字列の Piece（小片）を繋げて、 一つの巨大な文書を表現する方式。 検索すると引っかかる文書のほとんどが AbiWord 関係なので、 このワープロソフトの主要な内部データ構造ということなのかな。 他に、MS-WordやOpenOffice.org関連の文書にも登場していて、 基本的に単なるテキストエディタよりは、文字に付加情報をくっつける系の 編集ソフトに使われる場面が今のところ多いみたいです。 余談ですがAbiWordは、綱渡り的にですがBeOS版の開発が続いている貴重なワープロソフトなのです。感謝感謝。 概要 ファイルを読み込んだとしましょう。ABCDEFG、という７文字のファイル。 とりあえず、７文字分のOrigという名前のバッファを用意して、そこに格納します。 それと別に、Addという名前の空のバ
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
Preferred Research サマーインターン2011問題を解いてみた - ブログ執筆中
http://research.preferred.jp/2011/07/intern2011_problem/ 基本方針: 異なる種類の文字同士を見つけて消去して、最後に残った文字の種類を出力する。 出現回数が最大の文字をaと呼ぶことにする. aの出現回数はn/2より大きい、別の言い方をすれば、a以外の文字の出現回数の合計はaの出現回数よりも小さい。そのため、異なる種類の文字同士を見つけて消去していくと、仮に消去の組み合わせの一方が全てaだったとしても、文字種が1種類になるときには必ずaが残る。 文字列をstrとすると、回答は以下: i = 0 j = 1 while j != n if str[i] == str[j] j += 1 else str[i] = ILLEGAL_VALUE str[j] = ILLEGAL_VALUE while str[i] == ILLEGAL_VA
検索の歴史 一文字進化するのに掛かった年数は、なんと… - 当面C#と.NETな記録
文字列の高速検索の歴史を年表にしてみたんだけど、年表にしたらめちゃくちゃおもしろいことに気づいてしまいました！今日のエントリーは必見ですよ！ id:siokoshou:20060323 に書いた EXACT STRING MATCHING ALGORITHMS に各論文の発表された雑誌が載ってたので、年表に並べてみました。いろいろ検索しててあちこちでみかけた名前だけ並べてます。 1977 KMP 1977 BM (Boyer-Moore algorithm) 1980 BMH (Horspool algorithm) 1990 Sunday Quick Search algorithm 1992 Shift Or algorithm 1992 Turbo-BM algorithm (繰り返し対策.DNAのように文字種の集団が小さい場合に有効) んで、注目のポイントはここ。 1980 BMH
簡潔データ構造(Succinct Data Structure)で最初に読むと良さそうな論文 - EchizenBlog-Zwei
最近、簡潔データ構造(Succinct Data Structure)まわりの論文を色々読んでいる。その中で良さそうなものをいくつかピックアップしてみた。まだ調査中なので他に良いものがあったら教えてもらえると嬉しいです。 (1) Space-efficient Static Trees and Graphs(link) G. Jacobson; IEEE1989 まずはLOUDS論文。簡潔データ構造の元祖なので最初に読むと良さげ。 (2) Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees and Multisets(link) R. Raman, V. Raman, and S. S. Rao; SODA2002 簡潔ビットベクトルは通常n+o(n)なんだけど、これをnH0+o(n)にしたよ、
<4D6963726F736F667420506F776572506F696E74202D208FEE95F1926D8EAF836C83628367838F815B834E93C1985F817595B68E9A97F18FC68D878341838B8353838A83598380817691E6825289F12E707074>
1 北海道大学 Hokkaido University 「情報検索とパターン照合」 情報科学研究科 コンピュータサイエンス専攻 情報知識ネットワーク研究室 情報知識ネットワーク特論 喜田拓也 2005/10/18 情報知識ネットワーク特論 講義資料 第３回 第３回 Suffix型アルゴリズム Boyer-Moore アルゴリズム アルゴリズム Galil アルゴリズム Horspool アルゴリズム Sunday アルゴリズム アルゴリズム 3 北海道大学 Hokkaido University Naïve アルゴリズム 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 テキストT: a b a b b a b a b c b a a b a b c パターンP: a b a b c パターン出現！ パターン出現！ at posit
Vector clock - Wikipedia
A vector clock is a data structure used for determining the partial ordering of events in a distributed system and detecting causality violations. Just as in Lamport timestamps, inter-process messages contain the state of the sending process's logical clock. A vector clock of a system of N processes is an array/vector of N logical clocks, one clock per process; a local "largest possible values" co
Dictionary of Algorithms and Data Structures
absolute performance guarantee abstract data type (a,b)-tree accepting state Ackermann's function active data structure acyclic directed graph: see directed acyclic graph acyclic graph adaptive heap sort adaptive Huffman coding adaptive k-d tree adaptive sort address-calculation sort adjacency-list representation adjacency-matrix representation adjacent admissible vertex ADT: see abstract data typ
BIRCH - 機械学習の「朱鷺の杜Wiki」
Balanced Iterative Reducing and Clustering using Hierarchies (BIRCH)† 限定された主記憶で大規模データをクラスタリングする手法．データの走査は1回だけなので，データストリームの処理にも使える．データを圧縮して保持する部分はデータスカッシングとも見なせる． ↑ CF木 (Clustering Feature tree)† CF木は，BIRCHで使うデータの圧縮表現．基本的には，直径がしきい値以内のデータを部分クラスタにまとめる．この部分クラスタ内のデータは，以後の大域クラスタリングではひとまとまりにして扱い，同じ最終クラスタに分類される． この部分クラスタはCF(Clustering Feature)によってあらわす．これは，部分クラスタ中のデータ数，総和，2乗和の三つ組．この部分クラスタを木構造で格納したものがCF木．新た
Dynamic time warping - Wikipedia
Dynamic time warping between two piecewise linear functions. The dotted line illustrates the time-warp relation. Notice that several points in the lower function are mapped to one point in the upper function, and vice versa. Two repetitions of a walking sequence recorded using a motion-capture system. While there are differences in walking speed between repetitions, the spatial paths of limbs rema
LZO vs Snappy vs LZF vs ZLIB, A comparison of compression algorithms for fat cells in HBase
LZO vs Snappy vs LZF vs ZLIB, A comparison of compression algorithms for fat cells in HBase Now and then, i talk about our usage of HBase and MapReduce. Although i am not able to discuss details further than what writes on my linkedin profile, i try to talk about general findings which may help others trying to achive similar goals. This post is about a recent research which tries to increase IO p
[プログラミング] Google Sparsehashを使うときの注意点 - tsubosakaの日記
持橋さんの書かれたgoogle-sparsehashと自作のsplay-treeとの速度比較をした結果の記事を読んで、さすがに速度に200倍近くの差がでるのはおかしいだろうということで原因を探ってみた。 結論としてはGoogle Sparsehashを使うときに__gnu_cxx::hashを使わない方がよいということが分かった。 時間の測定に用いられているコードは概ね以下のコードと同じである。 #include <iostream> #include <google/sparse_hash_map> #include <cstdio> #include <cstring> #include <ext/hash_map> using namespace std; using google::sparse_hash_map; typedef __gnu_cxx::hash<const cha
![[プログラミング] Google Sparsehashを使うときの注意点 - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/c541ea2500c0318fc6e5834b084376f4a70f360f/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124030230%2F1557332439)
Googleページランクの初期モデルの限界とGoogleが加えた2つの重要な調整 | Moz - SEOとインバウンドマーケティングの実践情報
GoogleのPageRank（Googleツールバーが表示する小さな緑のインジケータではなく生の値）の裏にある「ランダムサーファー」について知っている検索マーケティング担当者は多い。Google自身の表現を借りれば、以下のようになる。 PageRankは、ユーザーの挙動を表した1つのモデルと考えることができる。たとえば、無作為にウェブページを訪問して片っ端からリンクをクリックし、決して「戻る」ボタンをクリックせず、最終的にはそこに飽きて別のページで同じことを繰り返す「ランダムサーファー」がいると仮定する。そうしたランダムサーファーがページを訪問する可能性を示すのがPageRankである。 別の言い方をすれば、あるページに対するリンクが多ければ多いほど、そのページはたくさんの「票」を獲得し、その結果PageRankも高くなるというわけだ。もう少し深く掘り下げて言うと、票の重さはリンク元の各
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
定兼 邦彦 (Kunihiko Sadakane) - 簡潔データ構造講義資料 - researchmap
GrowCut algorithm - Wikipedia
Horspool algorithm
Glibc malloc internal
