Spaghetti Source - Union Find
説明 Union Find は互いに素な集合を扱うための道具である．Union Find を用いると以下の操作を高速に行うことができる． union_set(x,y): x が入っている集合と y が入っている集合を併合する． find_set(x,y): x と y が同じ集合に入っているかを判定する． make_set(x): x のみが入る集合 {x} を作る． アルゴリズムは次の考え方による．集合を多分木で管理し，木の根を集合の代表元とみなす．集合の併合は木の併合，二つの要素が同じ集合に入るかどうかは代表元が等しいかどうかの比較で行う． これらの走査を単純な木で行った場合，検索や併合に最悪 O(n) かかってしまう．そこで平衡操作を取る．具体的には木の要素を手繰ったとき，それらの親ポインタをすべて根に張り替える．このときの計算量を見積もるのは複雑だが，ならし解析によって O(A(n
最短経路問題（ベルマンフォード法・ワーシャルフロイド法） - アルゴリズム講習会
最短経路問題 ベルマンフォード法とワーシャルフロイド法について解説します。 ダイクストラ法と比べて構造が単純（プライオリティキューがいらない）なので、多少は理解しやすいと思います。 入力の形式について このページで使用しているサンプルコードの標準入力は、全て下記の形式で与えられます。 n m $$[f_1 \ t_1 \ c_1]$$ $$[f_2 \ t_2 \ c_2]$$ ... $$[f_m \ t_m \ c_m]$$ nは頂点数、mは辺の数を示し、続くm行の \([f\_i, t\_i, c\_i]\) はそれぞれi番目の辺の始点、終点、重みを示します。 ベルマンフォード法 ベルマンフォード法は、２点間の最短路を見つけるアルゴリズム。 ダイクストラ法はうまく頂点を選ぶことで効率を上げているが、ベルマンフォード法では全ての辺に対して距離が短くなる経路があるか判定する。 基本的には
Publications of Kazuhiro Inaba
Books 理論計算機科学事典 (5.4 MSO 論理とMSO 変換) 純粋関数型データ構造 (Japanese Translation of "Purely Functional Data Structures" by C. Okasaki) Google Maps API 徹底活用ガイド Boost C++ Libraries プログラミング Papers Papers on the same line of research are colored by the same color. See also DBLP / GoogleScholar / MS-AcademicSearch / CSAuthors. Unpublished Drafts and Preprints [arXiv] Quick Brown Fox in Formal Languages K. Inaba [P
Sorting algorithms used in the CL implementations
Jorge Tavares Notes Personal bits around AI, Programming and other things I might find interesting Which sorting algorithm should one implement when developing a program? The best answer is probably none. Use the sort provided by your system/library/etc. Unless you know your input data has some special properties that you can take advantage of, the provided sort should be enough for your needs and
AAAI'15 論文採択：Top-k 最短経路クエリとネットワーク構造予測への応用 - iwiwiの日記
国際学会 AAAI 2015 に論文が採択されました．AAAI は人工知能分野の最も有名な会議の 1 つです．発表は来年の 1 月にアメリカのオースティンです．AAAI への論文採択は 2 年連続となります． 今回の論文は "Efficient Top-k Shortest-path Distance Queries on Large Networks by Pruned Landmark Labeling" というタイトルで，研究室後輩の林くん，京大の則さん，研究室同期の岩田，NII の吉田さんとの共著です．内容は，グラフにおける Top-k 最短経路を高速に計算するためのスケーラブルなインデクシング技法の提案，及びそのネットワーク構造予測への応用です．特に，応用面のインパクトを示す試みを論文内に入れることができたのが大変気に入っています． 背景：ネットワーク上の 2 点間の関連度推定に
Memory Layouts for Binary Search
The first round of experiments is over, but you can still help out with the second round. Binary search is a wonderful algorithm: theoretically optimal, fast in practice, and discoverable by school children playing guessing games. Usually we think of binary search as being applied to a sorted array, and we teach it this way. It turns out that, because of cache effects, sorted order is usually not
読むべきアルゴリズムの本
勉強しなければならないのである。 長くなるので、ここで折り畳んでしまう。 【有料・和訳有】Introduction to Algorithms おそらく一番有名なアルゴリズム本。MITの教科書。 日本語版もあるが、上記は第３版なのに対して、日本語版は第２版までが出ている。 しかも３分冊されていて、３冊目は第１版のものしかないため、私が買い漁った時でも絶版。 アルゴリズムイントロダクション（改定２版） 第１巻 数学的基礎とデータ構造 アルゴリズムイントロダクション（改定２版） 第２巻 アルゴリズムの設計と解析手法 アルゴリズムイントロダクション 第３巻 精選トピックス 【有料・和訳有】Algorithm Design ２番目に有名なアルゴリズム本か。こっちはコーネル大学の教科書。 なんとタイムリーなことに、今年の１０月に第２版が出るらしい。 リンクはその第２版へのもの。 買ってないのだが、1
Data-Oriented Hash Table – Nathan Reed’s coding blog
January 12, 2015 · Coding · Comments In recent years, there’s been a lot of discussion and interest in “data-oriented design”—a programming style that emphasizes thinking about how your data is laid out in memory, how you access it and how many cache misses it’s going to incur. With memory reads taking orders of magnitude longer for cache misses than hits, the number of misses is often the key met
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
JavaのTimSortがバグってる件について | さにあらず
Python で実装され、その後 Java にも移植されたソートアルゴリズムである TimSort が盛大にバグっていることが発見されました。 このバグがどのようにして発生するのかについては、以下のドキュメントを精査して下さい。 TimSort fails with ArrayIndexOutOfBoundsException on worst case long arraysOpenJDK’s java.utils.Collection.sort() is broken: The good, the bad and the worst caseどんなことが起こるのか#通常の利用では想定しえない場所でArrayIndexOutOfBoundsExceptionが発生します。 例えば、以下のようなスタックトレースになります。 Exception in thread "main" java.l
リード・コピー・アップデート - Wikipedia
リード・コピー・アップデート（read-copy-update、RCUと略記）とは、オペレーティングシステムにおいて一種の排他制御[note 1]を実装する同期機構であり、リーダー・ライターロック（英語版）の代替手段として使われることがある。参照において待ち状態が生じず、極めてオーバーヘッドが低い。しかしRCUにおけるデータ更新は、既存の参照者のために古い版のデータ構造を保持しつつ行うため、時間と空間（メモリ）をより多く必要とする。古い版のデータ構造は、既存の参照者が全てアクセスを完了した後で回収される。 RCUでは「参照側クリティカルセクション」という概念があり、通常 rcu_read_lock() と rcu_read_unlock() で挟まれた部分がそれにあたる。参照側クリティカルセクション内にない文は「不活性状態」と呼ばれ、RCUで保護されたデータ構造への参照を保持することは許さ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google
haskell splay tree zipper - Google 検索
Google
Reddit - Dive into anything
似ている文字列を探す - umeajiの日記
目次 - アルゴリズム講習会
ギークアカデミー：先端を走る技を、ギークに学ぶ
日立製作所が試作した新型コンピュータについて(2/24更新)(2/25更新)(2/26更新)（2/27更新）
open source c++ algorithm data structure - Google 検索