高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
![quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream](https://cdn-ak-scissors.b.st-hatena.com/image/square/f9103c273a45047a455a47c2322a4ec545cd77ee/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127143682567%2F17680117127143702106%2F1558185862)
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
ボイヤー-ムーア文字列検索アルゴリズム - Wikipedia
テキスト T = "ANPANMAN" に対して k = 3 から k = 8 までパターン P = "PAN" を配置した様子。この場合、k = 5 の位置で一致する。 文字列 S に対する操作を以下のように表す： S[i]： 文字列 S の i 番目の文字 S[i..j]： 文字列 S の i から j 番目までの部分文字列（i 文字目、j 文字目をそれぞれ含む） 文字列 S に含まれる文字の個数を文字列の長さと定義する。また、文字列 S の先頭を含む部分文字列をプレフィックス、末尾を含む部分文字列をサフィックスと定義する。 len(S)：S の長さ S[1..i], 1 ≤ i ≤ len(S)：S のプレフィックス S[i..len(S)], 1 ≤ i ≤ len(S)：S のサフィックス 検索文字列をパターンと呼び、P で表す。被検索文字列をテキストと呼び、T で表す。また T
文字列検索（BM法）
Boyer-Mooreのアルゴリズム BM法の原理 KMP法は『理論的には優れているが，実戦には弱い』 というアルゴリズム でした。 これに対して，BM法は『理論的にも優れていて，実戦にも強い』 と いう頼もしいアルゴリズムです。 実用的には，BM法は最も速い文字列探索ア ルゴリズムだということができます。パターンとテキストを重ね合わせて，末尾から先頭に向かって順番に文字を 比較していき，パターンとテキストの不一致が見つかったら，不一致の原因に なった文字に応じてパターンをずらす分量を決める，というのがBM法の考 え方です。 たとえば，左の図のようにテキストabdefghにパターンabcを重ね合わ せて比較することを考えましょう。 まずパターンの最後の文字をテキストと比 較します(左図(1))。 パターンの最後の文字はcで，対応するテキストは dになっています。
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
Preferred Infractractureサマーインターン2011問題 - 唯物是真 @Scaled_Wurm
サマーインターン2011問題 | Preferred Research ↑が面白そうだったので考える． O(n)の計算量で配列中に最も多い要素(ただしn/2回以上出現)を見つける． 記憶に使っていい容量はc log n bits． 1つ目 参考:API Only - Stack Exchange 現在の文字と同じ文字ならカウントを1足す 違う文字なら カウントが1以上なら1減らす カウントが0なら現在の文字を入れ替えて1足す given = "abcadbeca" count = 0 cur = given[0] for c in given: if cur == c: count += 1 else: if count == 0: cur = c count += 1 else: count -= 1 print cur 2つ目 乱択アルゴリズムかなあ？と思うけど微妙． 3つ目 思いつか
エラトステネスの篩 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "エラトステネスの篩" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2019年6月) エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がついている。
はてなブログ | 無料ブログを作成しよう
念願の資生堂メイクレッスンに行った かしら、かしら？ご存知かしら？ 資生堂のメイクレッスン、美容に興味のある女性はたいてい知っていそうだが一応そこから説明しておく。 世の中にはメイクを教えてくれるサービスがいろいろある。ドラッグストアのカウンター、デパートのカウンター、専門のサロンエト…
差分符号化 - Wikipedia
差分符号化（さぶんふごうか、英: Delta encoding）とは、データの格納や転送を完全なファイルとしてではなく、シーケンシャルなデータの差分の形式で行う方式である。特に変更履歴の保存を目的とする場合（ソフトウェアプロジェクトなど）、差分符号化は差分圧縮（英: Delta compression）とも呼ばれる。デルタ符号化、デルタ圧縮とも呼ばれるが、デルタ符号とは異なる。 例えばUNIXのファイル比較ユーティリティである diff などで「差分」または「デルタ」を作成し、個別にファイルとして記録する。差分は一般に元のファイルよりも小さいので、差分符号化によってデータの冗長性を大幅に削減できる。一連の差分ファイルの方が各バージョンのそのままのファイル群よりも大幅に記録容量が節約できる。 論理的観点から言えば、2つのデータの差分があれば、一方のデータからもう一方のデータを得ることができる
アルゴリズムクイックリファレンス
George T. Heineman、Gary Pollice、Stanley Selkow 著、黒川 利明、黒川 洋 訳 TOPICS クイックリファレンス , Programming , C/C++ 発行年月日 2010年04月 PRINT LENGTH 396 ISBN 978-4-87311-428-6 原書 Algorithms in a Nutshell FORMAT 障害に強い、問題が起こりにくいコードにはまず正しいアルゴリズムの選択から。理論だけでなく実践的側面を重視した、新しいタイプのアルゴリズムの書籍です。適切な問題解決、性能改善という、現場が求める2つの大きな要求に応えるため、どのアルゴリズムを使うべきか、どう実装するのか、さらに性能を向上させる方法はあるのかを、C、C++、Java、Rubyなど、さまざまな言語を使って説明します。図、表、サンプルコードがふんだんに盛
アルゴリズム行進こそ至高のアルゴリズムである - chokudaiのブログ
NHKで大人気の教育番組「ピタゴラスイッチ」における、アルゴリズム行進やアルゴリズム体操はあまりにも有名です。知ってる人も知らない人も、まずはこの動画を見ていただきましょう。 これが実際にNHKで放送された番組中の動画です。この動画を見ていただければ、タイトルの通りであるという説明をするまでもないとは思いますが、蛇足となることを覚悟しつつ、あえて、『なぜアルゴリズム行進が至高のアルゴリズムであるか』、その一部分を説明しようかと思います。 アルゴリズム行進から見える並列処理 皆さん、コンピュータがどう動いているかはご存知でしょうか？このブログを見てくれている方はかなり詳しく理解されている方が多いかとは思いますが、そうでない方も非常に多いのではないでしょうか？ここで少し難しい話をしますが、コンピュータの頭脳である、CPUがどのような働きをしているかを解説しようと思います。 CPUの場合 CPU
アルゴリズマーのそだてかた - chokudaiのブログ
日本発の「Topcoderトレーニング講座」は最強最速アルゴリズマーへの最短経路 こんな記事も出して貰えたところですし、凄く簡単に、自分の中での教育論みたいな部分を少し話してみようかと思います。 ある物事を習得するのに必要なのは何か？という話をした時に、僕が絶対に必要だと思っているのは、「すげぇ！！」ってなることだと思っています。当然だとは思いますが、せっかくなので具体例を見ていきましょう。 Wikipediaにおける、動的計画法の記事を見ると、このようになっています。 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法である。分割統治法がトップダウン的な手法であるのに対し、
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
さいころを使った１〜Ｎまでの完全な乱数の作り方 ２≦Ｎ≦２０ - chokudaiのブログ
人生ゲームとかやる時用に 手軽になるように作ってみました。振る回数の期待値は全て３以下です。 振る必要のある回数の期待値も併記しています。これより減らせる場合はコメントによろしくお願いします。回数はおそらくΣ[k=1..∞](6^(k-1)%n)/6^(k-1)になるだろう、という予測が経ちましたが、全ての明記はちょっと複雑になるので止めておきます。n=13,14,16,17,19,20が最善でないです。 N=2 (1回) 方法１ さいころを１回振り、偶数の場合１、奇数の場合２ 方法２ ３以下なら１、４以上なら２ N=3 (1回） 方法１ さいころを１回振り、３で割った余りに１を足す 方法２ １〜２が１、３〜４が２、５〜６が３とする N=4 (1.5回) ５以上が出たら振りなおす 別解法 N=2を２回利用する(2回) 追記 omeometoさん提供(1.333333回） １〜４が出たらその
Twitterを利用した男女間マッチングシステム「社会主義的彼女ったー」 - chokudaiのブログ
はじめに 今このブログを読んでいる貴方。貴方には、現在恋人はいますか？ いるわけありませんよね？ 一般的に、彼女や彼氏といった、恋人がいる状態は、恋人がいない状態と比べて、幸せである、という認識を持っている人が多いのではないかと思います。ですが、実際恋人がいる人は、非常に少ないでしょう。これはどうしてか？答えは簡単です。男性と女性を上手くマッチングさせる方法が、確立されていないからです。 こうした、きちんとした制度が確立されていない状態でマッチングを行った結果が、今の惨状です。イケメン、高学歴等の、生まれ持った武器を持った人ばかりに女性が集まり、一般の男性の元には人っ子一人として集まらない。万一彼女が居たとしても、何かしら不満を抱えていることが殆どでしょう。女性サイドだとしても、これは同様かと思います。不平等。非効率。この現状を言い表すのに、最も適した単語でしょう。 ああ、何と嘆かわしいこ
ブルームフィルタ - Wikipedia
この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
Cuthill–McKee algorithm - Wikipedia
CSLapack