完備辞書（簡潔ビットベクトル）の解説 - アスペ日記
以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。 LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。 また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。 この「簡潔ビットベクトル」「完備辞書」は、同じものを指しています*1。 今回は、このデータ構造*2について書いてみます。 完備辞書でできること ビット列に対する定数時間の rank と selectです*3。 rank()は、「ビット列の先頭から位置 k までに、1 のビットがいくつあるか」*4。 select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」*5。 それぞれ例を挙げます。
簡潔データ構造 LOUDS の解説（全12回、練習問題付き）
「日本語入力を支える技術」（通称「徳永本」）や「高速文字列解析の世界」（通称「岡野原本」）で紹介されている LOUDS というデータ構造を、12回に分けて解説しました。 友達に教える時に使ったもので、練習問題付きです。 実際に紙に書いてやってみるとわかりやすいと思います。 詳解 LOUDS (1) LOUDS とは 詳解 LOUDS (2) ビット列を作ってみる 詳解 LOUDS (3) 0番ノード 詳解 LOUDS (4) ビットの意味 詳解 LOUDS (5) 木構造の復元 詳解 LOUDS (6) インデックスでノードを表す 詳解 LOUDS (7) ノード番号からインデックスを得る 詳解 LOUDS (8) インデックスからノード番号を得る 詳解 LOUDS (9) 子ノードから親ノード 詳解 LOUDS (10) 親ノードから子ノード 詳解 LOUDS (11) 木の検索 詳解
Apple Podcast内のIntroduction to Algorithms (2005)
This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; an
Smoothsort - Wikipedia
In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981.[1] Like heapsort, smoothsort is an in-place algorithm with an upper bound of O(n log n) operations (see big O notation),[2] but it is not a stable sort.[3][self-published source?][4] The advantage of smoothsort is that it comes closer to O(n) tim
プログラミングコンテストでの乱択アルゴリズム
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
6.006: Introduction to Algorithms - Massachusetts Institute of Technology
Lecture 1 – Introduction & Document Distance (1 Feb 2011) notes | code | data | recitation notes | readings: 1, 3, D.1 Lecture 2 – Peak Finding (3 Feb 2011) notes | recitation notes | readings: 4.1, 4.3, D.1 Lecture 3 – Binary Search Trees (8 Feb 2011) notes | recitation notes | readings: 10.4, 12.1, 12.2, 12.3 Lecture 4 – AVL Trees (10 Feb 2011) notes | code | recitation notes | readings: 13.2, 1
デッカーのアルゴリズム - Wikipedia
デッカーのアルゴリズムはオランダ人数学者 T・J・デッカーの考案した相互排他のためのアルゴリズムである。これにより、共有メモリによる通信のみで、2つのプロセスが1つのリソースを競合することなく共有することができる。 厳密に交互にとっていく素朴なアルゴリズムを避けて発明された世界初の相互排他アルゴリズムの1つである。 ふたつのプロセスが同時に同じクリティカルセクションにアクセスしようとしたとき、このアルゴリズムはどちらのプロセスがアクセス権を得るかを決定する。もしもう一方のプロセスが既にクリティカルセクションに変更を加えていたら、その完了を待つ。 f0 := false f1 := false turn := 0 // or 1 p0: f0 := true p1: f1 := true while f1 = true { while f0 = true { if turn ≠ 0 { if
コーディングに役立つ！ アルゴリズムの基本 － ＠IT
本連載ではアルゴリズムとデータ構造を学ぶ、または学び直すことで、プログラミングのスキルを深めていきます。アルゴリズムは学問として取り扱われることが多いですが、この連載では開発の現場に役立つスキルを身に付けることを目的とします。 機械学習／Deep Learningが気になる人も要注目、「アルゴリズム」の基本が学べる無料の電子書籍150ページ 人気連載まとめ読み！ ＠IT eBook（29） 人気過去連載を電子書籍化して無料ダウンロード提供する＠IT eBookシリーズ。第29弾では「コーディングに役立つ！アルゴリズムの基本」10回分を1冊のPDFとしてまとめた。アルゴリズムとは何か？ なぜ学ぶべきなのだろうか？
Delphiアルゴリズムトレーニング － ＠IT
TListの実装と性能 Delphiアルゴリズムトレーニング（1） オブジェクト指向により、アルゴリズムは隠ぺいされることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるか
NLP2010 言語処理学会チュートリアル - DO++
今日から開催されている言語処理学会のチュートリアルで ”超高速テキスト処理のためのアルゴリズムとデータ構造” というタイトルで発表させていただきました。 チュートリアル資料はこちら(pdf)です。（出典などは適宜追加します） 今までいろいろなところで話してきた、オンライン学習、文字列、疎ベクトルデータ構造を最新の話を追加して、さらに乱択化（Hash Kernel, 乱択化SVD)を解説しています。 発表自体は途中でブルースクリーンが出るということもありましたが、なんとか終えられてよかったです。 これに付随していろいろツールを公開する予定だったがまにあわなかった。そのうち公開します
Alcor の Abbreviation Scoring - steps to phantasien(2009-09-12)
同僚の生産性ツール愛好家が熱に浮かされて言った. "QuickSilver の検索がすごいんだよ!" どう凄いのかというと, たとえば "Skype を検索するのに <sp> でいい!" らしい. それは凄いのかも. 私もいちおう QuickSilver を使っているけれど, 素敵機能の類はまったく活用していない. だいたい私の使うアプリケーションはどれも一文字で特定できる. Firefox, Emacs, iTerm, Activity Monitor... そういえば iTunes は iTerm と被ってる. ためしに <iu> と打ってみたら iTunes にマッチする. なんとなく凄い気がしてきた. 同僚はこのアルゴリズムが気になるらしい. 編集距離の仲間かとも思ったけれど, 違う気がする. とりあえずぐぐってみたところ, QuickSilver は 2007 年に オープンソー
軽量データクラスタリングツールbayon - mixi engineer blog
逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。 クラスタリングとは クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。 例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。 様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下の
きまぐれ日記: Schwartzian Transform でランダムシャッフル
Schwartzian Transform を使って配列をシャッフルする話をみて、なるほどな～と思いつつも、よくよく考えてみるとこれは2つの意味で駄目です。 1. 計算量が O(n * log(n)) であること。 2. ランダムにシャッフルできない。 1. は説明するまでもないので、2の理由を考えてみます。 まず、rand() が 0..k-1 までの k種類の整数から 1 つ数値を返すものとします。配列のサイズが n の場合、 weightの並びの場合の数は k^n 通り存在します。ところが、配列の順列の場合の数は n! です。 ここで何か矛盾点があるように思えてきます。 実際に k = 2, n = 2 の場合を考えて見ましょう。この場合、サイズ2の配列をシャッフルするんですから、 要素を入れ替える場合と入れ替えない場合が 1/2 の確率で出現するのが正しいシャッフルです。 k =
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とか） 赤黒木というのは動的データ構造
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
IDEA * IDEA
PathFinding.js
Top | ヒープの正体
GitHub - clever-algorithms/CleverAlgorithms: Clever Algorithms: Nature-Inspired Programming Recipes
The WHATWG Blog — Sniffing for RSS 1.0 feeds served as text/html