バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート - Line 1: Error: Invalid Blog('by Esehara' )
はじめに 恐らく、プログラマの中で配列内の要素を整列させたりするソートにお世話にならなかった人、というのは余り考えられないのではないでしょうか。しかし、とはいえ、大抵はソートを自前で実装せず、組み込み関数であったり、あるいは何らかのライブラリで済ませることが殆どだと思う。 車輪の再発明というよりも、バグとか、自分が考慮していなかった挙動などを避けるために、自前でソートを組むことは余りないのですが、とはいえ、自分なりにソートを実装して見ると、それがどういう特徴を持ったソートであるか、というのがわかりますし、また、ソートというのはいったいどういう操作で実現されるのかという洞察が深まってくるなあ、という実感があったりする。 なので、今回はあるソート二つについての話を書くのが趣旨です。 最高のアルゴリズムはある、だが最悪のアルゴリズムは何か 一口にソートといったところで、ソート自体にも銀の弾丸があ
A Very Brief Introduction to the Pi-Calculus (in Japanese)
π-calculus 超入門 π-calculus は、80 年代の終わりごろに Milner らによって提案された並行計算のモデルの一つです。そこでは、プロセスと呼ばれる複数の独立した主体が、通信チャネルと呼ばれるデータの通り道を介して値をやりとりしながら、計算を行っていきます。π-calculus にはいろいろな変種があるのですが、ここではとりあえず次のような構成要素からなるものを考えましょう。 new x . P 新しいチャネル x を作ってから、プロセス P を実行する (channel creation) x![v1, ..., vn] チャネル x に値 v1, ..., vn を送る (asynchronous output) x?[v1, ..., vn] . P チャネル x から値 v1, ..., vn を受け取って、P を実行する (input guard) P |
Ramer-Douglas-Peucker algorithm - Wikipedia, the free encyclopedia
The Ramer–Douglas–Peucker algorithm, also known as the Douglas–Peucker algorithm and iterative end-point fit algorithm, is an algorithm that decimates a curve composed of line segments to a similar curve with fewer points. It was one of the earliest successful algorithms developed for cartographic generalization. It produces the most accurate generalization, but it is also more time-consuming.[1]
Red Blob Games: Introduction to A*
In addition to finding a shortest path, these algorithms can be used for distance maps, flow field pathfinding, connected components, map analysis, garbage collection algorithms, flow networks, and procedural map generation. There are many optimizations and specializations of these algorithms. Representing the map# The first thing to do when studying an algorithm is to understand the data. What is
動的計画法の問題を機械的に解く方法 - yukobaのブログ
情報オリンピックという中高生向けの競技プログラミングの大会があります。国内予選・選抜が3回あり、最後に世界大会があります。アルゴリズムの問題が出題されます。予選の毎年のパターンは問1, 2は問題文をコードに起すだけの問題で、問3はアルゴリズムの問題だったり、中学受験的な算数の問題だったりします。問4はいつも動的計画法の問題が出ます。競技プログラミングでは動的計画法が一番の入門であり、これがスタートラインです。これが解けないと始まりません。動的計画法の問題、機械的に解けるのかなと思い色々と考えたのですが、できそうなので、このブログ記事にまとめます。 動的計画法 動的計画法ですが、やはり一番しっかり書かれているのが、書籍「アルゴリズムイントロダクション」 http://www.amazon.co.jp/dp/476490408X です。動的計画法の章は熟読に値すると思います。「動的計画法」とい
Visualizing Algorithms
The power of the unaided mind is highly overrated… The real powers come from devising external aids that enhance cognitive abilities. —Donald Norman Algorithms are a fascinating use case for visualization. To visualize an algorithm, we don’t merely fit data to a chart; there is no primary dataset. Instead there are logical rules that describe behavior. This may be why algorithm visualizations are
Throw away the keys: Easy, Minimal Perfect Hashing
I know how to make and sell software online, and I can share my tips with you. Email | Twitter | LinkedIn | Comics | All articles CORRECTION: In this article, I incorrectly state that an acyclic finite state automata (aka a DAWG) cannot be used to retrieve values associated with its keys. I have since learned that it can. By storing in each internal node the number of leaf nodes that are reachable
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
幅優先探索 | アルゴリズム[Ruby/Python][AOJ 0129]
『幅優先探索』をRuby/Pythonで解いてみました。AIZU Online Judgeで対応している問題は『Seven Puzzle』です。 🏀 概要深さ優先探査の説明は『通勤・通学中に理解する深さ優先探索と幅優先探索』、 『アルゴリズム図鑑：iOS & Androidアプリ』が分かりやすかったです。 要点は次のとおり。 根ノードで始まり隣接した全てのノードを探索。階層(根ノードからの距離が近い順)にルートを調べる 🐯 サンプル問題(AOJ)Seven Puzzle Aizu Online Judge。1-7までの数字と、1つ空白のあるパズルをとく問題。 😀 Rubyコード 01234567がそろった状態(ゴール)からスタートして、0を移動させる 幅優先探索で過去に到達していない状態になったら、手数(移動数)を記録 すでに到達済の状態であれば、スキップ(幅優先探索なら手数が同等か
![幅優先探索 | アルゴリズム[Ruby/Python][AOJ 0129]](https://cdn-ak-scissors.b.st-hatena.com/image/square/c2ea7e72d0d7f3ba6c237909f321e67ffbdaa24e/height=288;version=1;width=512/https%3A%2F%2Fmorizyun.github.io%2Fimg%2Fog_image.png)
平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
同人版 Magic: the Gathering のAIルーチンが興味深い | ず＠沖縄
Magic: the Gathering という時間と金を食い尽くすゲームがある。 私が知ったのは日本語第４版発売後なので1996年ごろ。REXAに改築される前のベスト電器那覇店が扱い始めたのがきっかけ。 JAVY地下の大会の決勝でカウンターポストに負けたんだよなあ。 カードゲームというジャンルが M:tG 以前と以後に分けられるほど画期的なゲームで、ポケモンカードゲームや遊戯王などの派生ゲームがワラワラ誕生したのも懐かしい記憶だ。 コンピュータ版 Magic: the Gathering沖縄には碁会所や雀荘は多く存在するのだが、マイナーゲームは対戦相手を探すのが一苦労。将棋ですら道場は少ない。まして舶来のゲーム。人間の相手は探しづらいので、コンピュータに相手をさせたくなるのは自然の成り行きだ。 さらにTCG自体が金食い虫のゲームなので、コンピュータで代行できれば安上がり。私も市販のソフト
linuxカーネルのセマフォについて - lxyuma BLOG
アルゴリズムとデータ構造についてOSSから勉強する会 という勉強会に行ってきた。 これは、とある掲示板の書き込みにOSSで使われてるアルゴリズムが書かれている物があって、 これを元に、皆で読み解いて行こうという企画。 カーネル読むという意味でも、アルゴリズムの勉強という意味でも、 とても良い勉強会。 面白かった。 まとめ 自分のチームはセマフォやった。 まあ、色々と不慣れだったし分からない所も多かったが、勉強になった。 以下、発表したメモに加筆した。 概要 セマフォ(semaphore)とは 複数プロセスによるアクセス制御に使われる仕組みの事 任意の個数の資源を扱うcounting semaphoreと、値が0,1しかないbinary semaphoreがある。 今日見たのは前者のcounting semaphore。この話を書いて行く。 ちなみに、後者がMutexになる（同等の機能を持つ
Core algorithms deployed
Algorithms that are the main driver behind a system are, in my opinion, easier to find in non-algorithms courses for the same reason theorems with immediate applications are easier to find in applied mathematics rather than pure mathematics courses. It is rare for a practical problem to have the exact structure of the abstract problem in a lecture. To be argumentative, I see no reason why fashiona
Binary Indexed Tree のはなし
Binary Indexed Tree のはなし 保坂 和宏 (東京大学理学部数学科) 第 13 回 JOI 春合宿 2014/03/19 概要 Binary Indexed Tree とは 何ができる？ 何が嬉しい？ 具体的な実装 応用範囲 区間に足す問題 多次元 二分探索 目標 実装できるようにする 「普通に Binary Indexed Tree を使うだけ」の部 分で詰まらないようになる 補助的な道具としてぱっと使えるように Binary Indexed Tree とは Binary Indexed Tree Binary Indexed Tree (Fenwick Tree) Peter M. Fenwick, "A New Data Structure for Cumulative Frequency Tables" (199
文法圧縮入門：超高速テキスト処理のためのデータ圧縮（NLP2014チュートリアル）
言語処理学会第２０回年次大会（2014/3）のチュートリアル講義資料です。 - 要旨 - 文法圧縮とは，入力テキストをよりコンパクトな文脈自由文法（CFG）に変換する圧縮法の総称である． 文法圧縮の強みは圧縮テキストを展開すること無く，検索等のテキスト処理を効率よく行える点にある． 驚くべきことにその処理速度は，元テキスト上での同じ処理を理論的に，時には実際にも凌駕する． また近年，ウェブアーカイブやログ，ゲノム配列等の大規模実データを高効率に圧縮できることで注目を集めている． しかしながら，文法圧縮についての初学者向けの解説資料はまだまだ少ない． そこで本チュートリアルでは，文法圧縮の歴史的背景から最新動向までを幅広く紹介する． 具体的には文法変換アルゴリズム，圧縮テキスト上での文字列パターン検索，文法圧縮に基づく省メモリデータ構造等の解説を行う．
Spotify: 曲をシャッフルするのは単純にランダムではいけない - ワザノバ | wazanova
http://labs.spotify.com/2014/02/28/how-to-shuffle-songs/ 1 comment | 0 points | by WazanovaNews ■ comment by Jshiike | 約4時間前 SpotifyのLukáš Poláčekがプレイリストをシャッフルするロジックを改善した取り組みを紹介しています。 以前のロジック ランダムアルゴリズムには、Fisher-Yates shuffleを利用。 順次再生する曲を選ぶロジック同士には依存関係がなく、完全にランダムに選択される。よって、同じアーティストとの曲が連続して再生されることも可能性としてはある。 これはギャンブラーの誤謬と呼ばれる現象。例えば、コイントスで表が連続してでると、次は裏が出ると思いがちであるが、常に確率は1/2である。従前の結果が次の結果に影響を与えると考えてし
Netflixはどのように映画をジャンル分けしているか - 不可視点
映像コンテンツのストリーミングといえばNetflix、現在4400万人のユーザー（有料会員）がいる成熟したサービスですが、現在もすごいペースで成長しています。 Netflix、第4四半期決算で大幅増益--加入者数は400万人増 - CNET Japan 利用できる地域は限られますが、日本でもレコメンデーションのコンテストNetflix prizeの開催や、AWSをいち早く活用した企業として知られています。 Netflixは先に紹介したNetfix Prizeでレコメンデーションの性能向上に懸賞金をかけたほど、レコメンデーションがサービスの重要な位置を占めています。 視聴された映画の2/3はレコメンデーション経由らしいです。 Todd Yellin(Vice President of Product Innovation at Netflix)は、「映画をピッタリの人にピッタリのタイミングで
Deflate (gzip) のアルゴリズムを視覚化してみた
のような感じにエンコードされることが分かります。 自分の好きなデータで試すことができて便利！という話でした。 PS. 以下は実行結果です。 % make % gzip < alice.txt > alice.txt.gz % ./puff -10 alice.txt.gz puff() succeeded uncompressing 1328 bytes 8 compressed bytes unused inpos=406,inbits=224,outpos=0,outbytes=45 41 6c 69 63 65 20 77 61 73 20 62 65 67 69 6e 6e 69 6e 67 20 74 6f 20 67 65 74 20 76 65 72 79 20 74 69 72 65 64 20 6f 66 20 73 69 74 74 A l i c e w a s b
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
A* Pathfinding Algorithm Visualization
