バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート - Line 1: Error: Invalid Blog('by Esehara' )
はじめに 恐らく、プログラマの中で配列内の要素を整列させたりするソートにお世話にならなかった人、というのは余り考えられないのではないでしょうか。しかし、とはいえ、大抵はソートを自前で実装せず、組み込み関数であったり、あるいは何らかのライブラリで済ませることが殆どだと思う。 車輪の再発明というよりも、バグとか、自分が考慮していなかった挙動などを避けるために、自前でソートを組むことは余りないのですが、とはいえ、自分なりにソートを実装して見ると、それがどういう特徴を持ったソートであるか、というのがわかりますし、また、ソートというのはいったいどういう操作で実現されるのかという洞察が深まってくるなあ、という実感があったりする。 なので、今回はあるソート二つについての話を書くのが趣旨です。 最高のアルゴリズムはある、だが最悪のアルゴリズムは何か 一口にソートといったところで、ソート自体にも銀の弾丸があ
遅いソート - 鍋あり谷あり
http://bugrammer.hateblo.jp/entry/2014/08/16/014212 ( バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート ) を読んで。 ちゃんと終わるけどもっと遅いソートがあるので書いてみた。 たぶん名前がついていると思うんだけど、調べてないので名称不明。 こういう奴。 def try_all_sort(s) s.permutation(s.size){ |x| return x if x.each_cons(2).all?{ |a,b| a<=b } } end typical case では bogo sort と同じオーダー。 bogo sort と違って、worst case は有限。O((N+1)!)だと思う。 で。ベンチマーク。 100要素を1000回なんて宇宙が消滅するまでに終わらないので、試した
Damerau-Levenshteinは並べ替え機能付き : mwSoft blog
先日、レーベンシュタイン距離のコードを見ていて思ったのだけど、この手法には1つもの足りない点がありました。 例えば以下の2つの文字を比べた場合です。 あした あたし 2つ目のポジションの「し」を削除し、3つ目のポジションに「た」を挿入するという2回のアクションで文字列を一致させられます。 これは、以下の文字列を比べた場合と同じコストです。 あした あたい 1つ目のパターンの方は、3つとも全て同じ文字が使われているというのに、文字列の近さは同じと判定されてしまうわけです。 レーベンシュタイン距離は「挿入」「削除」「置換」の3パターンしかサポートしていません。 これを解決するには「し」と「た」を「並べ替える」という処理が必要になります。 この処理を追加サポートしているのが、「Damerau-Levenshtein」（カタカナ表記ではなんと書けばいいのだろう）。並べ替え処理は、英語版Wikipe
http://swatmac.info/?p=942
See related links to what you are looking for.
Damn Cool Algorithms: Levenshtein Automata - Nick's Blog
Posted by Nick Johnson | Filed under python, tech, coding, damn-cool-algorithms In a previous Damn Cool Algorithms post, I talked about BK-trees, a clever indexing structure that makes it possible to search for fuzzy matches on a text string based on Levenshtein distance - or any other metric that obeys the triangle inequality. Today, I'm going to describe an alternative approach, which makes it p
大規模グラフアルゴリズムの最先端
東京大学 松尾研究室が主催する深層強化学習サマースクールの講義で今井が使用した資料の公開版です． 強化学習の基礎的な概念や理論から最新の深層強化学習アルゴリズムまで解説しています．巻末には強化学習を勉強するにあたって有用な他資料への案内も載せました． 主に以下のような強化学習の概念やアルゴリズムの紹介をしています． ・マルコフ決定過程 ・ベルマン方程式 ・モデルフリー強化学習 ・モデルベース強化学習 ・TD学習 ・Q学習 ・SARSA ・適格度トレース ・関数近似 ・方策勾配法 ・方策勾配定理 ・DPG ・DDPG ・TRPO ・PPO ・SAC ・Actor-Critic ・DQN（Deep Q-Network） ・経験再生 ・Double DQN ・Prioritized Experience Replay ・Dueling Network ・Categorical DQN ・Nois
Tumblr
「JPEG Tilt」というページを公開しました。MotionJPEG Builder を作った時に、JPEG のヘッダを読み込む処理を作ったので（結局これは使わなかったんですが）圧縮データの読み込み部分も作ってみようか、という気になって作ったのがこれです。JPEG ファイルで画像が圧縮される様子を視覚的に表現する…… という目標だったのですが、どうでしょうか。まあ内容が内容なので説明無しではさすがに意味が分からないと思います。 ということで、JPEG Tilt の見方を以下で簡単に説明します。 図1は、JPEG Tilt の画面です。画像が iTunes の CoverFlow のように並んでいますが、これの左側は画像の低周波成分のみを抜き出した物で、右に行くとより高周波の成分も含めるように並んでいます（低周波、高周波という言葉の意味はこの先で出てきます） 画像の上にマウスカーソルを乗せ
麻雀ゲームが弱い理由（書きかけ放置版） - マッタリプログラミング日誌
先日、将棋界では、米長永世棋聖vsボンクラーズの対局が行われ、ボンクラーズの勝利でおわりました。このことは、各メディアでニュースとして取り上げられ、ネット上の電子掲示板などでも話題になっていたようです。その話題のなかで、他のゲームはどうなんだ、麻雀はどうなんだ、という話がでてきます。そういった場でよくでてくる話は大体こんな感じです。「麻雀は、イカサマが可能なのであまり真剣に思考ルーチンの研究開発がなされていない。金にならないから誰もやらない。だから弱い」のだと。まあこれも確かにその通りなのですが、麻雀は将棋とは違った難しさがあるのです。 まったり麻雀は、他のコンピュータ麻雀ソフトよりは頑張ってる方だと自負していますが、人間のトップクラスの人から見ればまだまだな部分も多いでしょう。 コンピュータ将棋は、全幅探索、後方枝刈り、棋譜をベースにした教師あり機械学習をセットとしたいわゆるボナンザメソ
人力検索はてな - 二枚の画像が似ているかどうかを高速に判定するアルゴリズムを探しています。
二枚の画像が似ているかどうかを高速に判定するアルゴリズムを探しています。 通常は画素ごとに差分をとって平均二乗誤差やSN比を計算するのが一般的だと思いますが、これだと2乗計算を画素数分行うため計算量が多くなってしまい、比較する画像が複数ある場合だと計算時間が多大に増えてしまうことが問題になります。そこで画像比較の計算時間を削減できるアルゴリズムを探しています。 例えば、文字列処理では正規表現を用いることで高速に文字列探索が行えると聞いたのですが、画像処理の場合にはこのような強力な手法はあるのでしょうか？ 一つ画像にモザイクをかけて比較する画素数を減らして計算時間を削減する手法を行ったのですが、これだと計算時間は削減されるものの比較精度が落ちることが問題でした。あまり精度を落とすことはできません。 私は現在大学生でして、ある自作のソフトウェアを作成している所なのですが、上記の問題のため先に進
Akinator アキネータの仕組み : 研究開発
総合研究大学院大学 複合科学研究科 情報学専攻 卒 博士（情報学） 自然言語処理や機械学習、データ分析に関する研究内容とwebシステムの開発と運用について書いています。 シリコンバレーベンチャーみたいに深い技術の事業化をしたいと思っています。 ご興味ある方はご連絡ください。 あれはどうやってるのでしょうか？ [iPhoneアプリ] Akinator（アキネイター）が答えを当てる仕組みを考えてみました プログラマがランプの魔人の中身を分析してみる という感じに考えた人はたくさんいますが.... これでも全然Akinatorの本質には迫ってないと思います。 ○たった２０〜４０問の質問しかしない。 登録されてる質問の総数は、当然もっと多いのですが、そもそもAkinatorは質問を十分に選定してるのです。 この点に触れて考えている人が居ないようなのですが、おそらく、これこそがAkinatorの本
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
マルチキークイックソート - sileのブログ
「Sorting and Searching Strings」で説明されているマルチキークイックソートの実装。 詳細はリンク先を参照。 マルチキークイックソート 文字列の配列のソートが高速に行える URL("http://...")の配列のような接頭部分の重複率が高い文字列配列の場合でも性能が低下しにくい クイックソート + 基数ソート、のような感じ？ ソート方法 基本的には通常のクイックソートと似ていて「ピボット要素*1を選んで、配列を分割する」といったことを繰り返す。 ただし、クイックソートは各段階で配列を二分割(ピボット要素よりも大きいか小さいか*2 )し、そのための比較には要素(文字列)全体を用いるのに対して、マルチキークイックソートでは、配列は三分割(ピボット要素よりも大きいか小さいか、それとも等しいか)され、そのための比較には文字列全体ではなく(各段階で)一文字のみ、が用いられ
A* - Wikipedia
A*探索アルゴリズム A*（A-star、エースター）探索アルゴリズム（エースターたんさくアルゴリズム）は、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、さらにf値として「現時点までの距離」g と「ゴールまでの推定値」h の和を採用したもの[1]。h は ヒューリスティック関数と呼ばれる。 概要[編集] A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。h は各頂点 n からゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまな h を設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、h としてユークリッド距離 を使うことができ、この値は道に沿った実際
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
FF12の乱数について
概要 FF12が内部でどのように乱数を扱っているか調べたので、分かったことを書くよ。 目次 概要 表記 注意 導入 生成器Aの特徴 A系列のよくある利用パターン A系列を使う処理 銃 素手 斧、ハンマー、ハンディボムによる攻撃のダメージ計算 ケアル、ケアルダ ポーション、ハイポーション、エクスポーション、エーテル、ハイエーテル トレジャーの開封 セーブデータのロード A系列の乱数を消費しない行動 応用例 乱数位置の特定 5hits法の原理 "セロビ台地/交差ヶ原"のトレジャーPOP法則 分かっていないこと 表記 この文章では以下の規則に従う。 ⌊x⌋で、x以下の整数のうち最大のものを表す。 x % yで、xをyで割った余りを表す。x % y = x - y * ⌊x / y⌋ 注意 この文章では、FF12内の乱数の規則性を観察し、それを制御する方法について述べている。こういうプレイははおそ
Alcor の Abbreviation Scoring - steps to phantasien(2009-09-12)
同僚の生産性ツール愛好家が熱に浮かされて言った. "QuickSilver の検索がすごいんだよ!" どう凄いのかというと, たとえば "Skype を検索するのに <sp> でいい!" らしい. それは凄いのかも. 私もいちおう QuickSilver を使っているけれど, 素敵機能の類はまったく活用していない. だいたい私の使うアプリケーションはどれも一文字で特定できる. Firefox, Emacs, iTerm, Activity Monitor... そういえば iTunes は iTerm と被ってる. ためしに <iu> と打ってみたら iTunes にマッチする. なんとなく凄い気がしてきた. 同僚はこのアルゴリズムが気になるらしい. 編集距離の仲間かとも思ったけれど, 違う気がする. とりあえずぐぐってみたところ, QuickSilver は 2007 年に オープンソー
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Amazon.co.jp： 珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造: 本: ジョン ベントリー,Jon Bentley,小林 健一郎
Amazon.co.jp: アルゴリズムデザイン: Jon Kleinberg (著), Eva Tardos (著), 浅野孝夫 (翻訳), 浅野泰仁 (翻訳), 小野孝男 (翻訳), 平田富夫 (翻訳): 本
Codelogy: C++の std::unique と、Ruby の Array#uniq の本質的な違い