現場プログラマーのアルゴリズム再入門本（勝手に付けた副題）、アルゴリズム・クイックリファレンス第2版を読んだ。今年の2月に訳者の @hydrakecat さんから献本いただいていたのだが、感想を書くのが遅くなってしまって申し訳ない。 ちなみにこの本を読んでいる自分の背景を説明すると、一応大学は情報系だが、アルゴリズムや理論寄りの話は苦手。仕事ではスマートフォンアプリのコードを書くことが多く、アルゴリズムに直接触る機会はほとんど無いという人間である。 内容 第1版をぱらぱら読んだことはあり、コンパクトで読みやすい本だなと感じていた。第2版では赤黒木が削られたり、Pythonのコードが追加されたりしたようだが、受ける印象はそんなに変わってなかった（と言いつつ第1版と比較してみると、C言語の箇所が減っている）。 前の版から引き続き、とにかく実際に動くコード、実際の計算機での動き方にページが割かれ
Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them. Over the last few years, I
qSPCの開発も山場を越えた感があるのでたまには進捗報告以外の話を…… 多分、普段は宇宙語が書いてあるブログだと思って見てない人が多いと思うので前提知識を手短に書いておくと: スーパーファミコンにはメインのCPUと別にサウンド用のCPUが乗っている オーディオデバイスにはサウンドCPUからしか触れない サウンドCPUはメイン側とは独立したメモリを抱えている このメモリは64KBしかない メインCPUとサウンドCPUのやり取りには、あまり速くない通信路を使う必要がある という制約があるので、いかにデータをコンパクトにして、最低限の物だけをサウンドCPUに送るかという所で開発者の腕が試されることになる。で、プロの技はどんなもんだろうかと、メモリダンプを見ながら定番のグラディウスIIIをやってみると…… ボスを倒して、ステージが変わるタイミングで一瞬画面が止まるので、ここで曲を入れ替えていると思
この前から、このブログでは、なんとなく特定の分布、特に正規分布の疑似乱数を生成する方法について書いているわけだが、 manieth.hatenablog.com manieth.hatenablog.com Ziggurat アルゴリズム 正規分布作成にZigguratアルゴリズムというのがあるらしい。 Ziggurat algorithm - Wikipedia, the free encyclopedia で、こいつが速い。だが However, since the ziggurat algorithm is more complex to implement it is best used when large quantities of random numbers are required. って書いてあるんだけど、実装なんて一回してしまえばあとは使うだけなんで、複雑もクソもある
乱数チューニングによる動きのコク 1. 一様乱数 いわゆるMath関数による乱数。 雑味や臭みが強く、そのままでは使い物にならない。 2. 雑味を取り除いた乱数 下処理として臭みや雑味を取り除いた状態。一様乱数特有の発作的なガタツキがないのがわかるだろうか？ 過去2フレームに、距離33%以内の重複数が出ないようになっている。 シャッフルやスロットのアニメ処理など、2連続で同じ数字が重なるとバグって見える表現に有効。 3. コクのある乱数 乱数の旨味が濃縮された状態。中心極限定理により、自然な風合いに濃縮されている。 加算式による天然の正規分布は、ボックスミューラー法の養殖された乱数と違い、加算回数で生産者ごとの味わいが出せる。 パーティィクルや自然シミュレーションと相性が良い。 4. 芳醇なまろ味を出した乱数 口に含んだ後に、豊かな香りが広がる乱数。移動平均により連続性を出すことで、揺らぎ
Elasticsearchを使おうとしているとAnalyzerという概念が出てくるが、このAnalyzerという概念は最初理解することが難しかった。全文検索の仕組みを理解すれば分かるだろうと思い、https://speakerdeck.com/johtani/elasticsearchru-men?slide=5 やhttp://www.atmarkit.co.jp/ait/articles/1111/18/news148.html の記事などを読んで勉強してみたものの、こちらもいろんな言葉が出てきて非常に混乱した。例えば転置インデックス、tf-idf、トークナイズ、ストップワード、N-Gram、正規化などといった言葉が出てくる。 いろいろ調べてみて整理すると、全文検索の技術には、なぜ検索ができるかの話以外に、類似度の話、検索を高速に行うための話、あいまいな検索に対応する話など、いろんな話
「しりとり」は経験者人口が極めて多いゲームだけど、鬼神のごとき強さで他を圧倒するしりとりプレイヤーを私は知らない。ちょっと真剣に戦ってみたところで、 そんな程度のレベルで満足していやしないか。 さいしょは「る」の同字返しでガッチリ組み合う。先に「る→る」のストックが切れて、「る」で返せなくなったほうがひたすら「る攻め」で投げられ続ける。 小学生の時から進歩していないような、こんな大雑把でマンネリな「る攻め」戦略から脱却できないものか。 攻撃防御比最大の最強文字「る」 復習。周知の事実だが「る」は強い。 下の表は、[A](文字Ｘで終わる単語)と、[B](文字Ｘではじまる単語)をその比[A/B]の高いものから順にリストしたものである。標本の単語数は２０万語であり豚辞書から、伸ばし棒をトリムした上で抽出した。*1 文字X[A]Xで終わる単語[B]Xで始まる単語[A/B] １位る43235208.
Part 1 Task の依存関係の解決 Part 2 Workflow の冪等性 Part 3 Task 間でのデータのやり取り Part 4 Task の並列実行 Workflow Engine って何？ Workflow Engine と言っても多機能なものから、シンプルなものまで様々なものがあります。そこで、主旨がぶれないように、この記事での Workflow Engine は、以下の要件を満たすソフトウェアとします。 Workflow Engine とは、依存関係のある複数の Task を、意図した順番通りに実行するもの この記事では、この要件を満たす Workflow Engine を Ruby でつくる方法について解説します。 依存関係を記述する 依存関係を解決するコードを書く前に、依存関係を記述する方法をまず決めましょう。 依存関係を記述するには、luigi のように Ta
Overview PNG is an image format that has a history of development beginning in 1995, and it is still a popular, long living format. Generally, it is known for its features such as lossless compression and the ability to handle transparent pixels. However, we do not look at image formats from a general point of view, but rather think of ways to glitch them. When we look at PNG from the point of vie
2015年Apr6日レベルデザインに遺伝的アルゴリズムを活用する こんにちは。オインクゲームズの新藤です。 先日、弊社のデジタルゲーム第二弾となる「OLYM」がリリースされました。OLYM はターン制限のあるパズルゲームで、各ステージごとに決められたターン数が設けられてています。このターン数以内に目標を達成できないと、クリア失敗になってしまいます。そのため、このターン数をどう決めるかが、難易度に大きく影響する一因となっています。OLYM では、ステージごとのターン数を決定するのに遺伝的アルゴリズムを活用したので、今日はそれをご紹介します。 最終的にやったことは非常にシンプルです。端的に言えば、AI に実際にパズル解かせて、何手で解けたかをレベルデザインの参考にするということです。この AI を作る際に、遺伝的アルゴリズムを活用しました。そもそもは「自動でパズル解いてくれる AI がいたら面
あけましておめでとうございます。白ヤギの物理担当、シバタアキラ(@punkphysicist)です。 皆様はどんなお正月を過ごされましたか？日本の正月といえば、おせち、日本酒、おばあちゃん、そしてパズル、ですよね。私の正月はそんな感じでした。お節をたらふく食べ、美味しいお酒でほろ酔い気分になっている私の横で、黙々とおばあちゃんがパズルをやっているのに気づいたのです。部屋中をフワフワしている私とは全く対照的に、微動だにせずパズルを続けるおばあちゃん。御年迎えられると辛抱強さが半端ない。 そんなおばあちゃんがやっていたのはかわいいチョコレートのピースとは裏腹にこんな挑発的な文言の書かれたパズルです（この記事はアフィリエイトではありませんが、写真をクリックすると買えます） 何時間たっても答えが出ないおばあちゃん、辛抱強さは人一倍強いですが、私も何とか助けてあげたいと思いトライ。しかし日本酒が・・
39. 実際の使用イメージ 試行数 アーム1期待値 アーム2期待値 アーム3期待値 活用or探索 0(0/0) 0(0/0) 1 1(1/1) 0(0/0) 2 1(1/1) 0(0/1) 3 1(1/1) 0(0/1) 4 1(2/2) 0(0/1) 5 1(2/2) 0.5(1/2) 6 1(2/2) 0.5(1/2) 7 8 0.66(2/3) 0.5(1/2) 9 0.5(2/4) 0.5(1/2) 10 0.4(2/5) 0.5(1/2) 0(0/0) 0(0/0) 0(0/0) 0(0/1) 0(0/0) 0(0/0) 0(0/2) 0(0/2) 0(0/2) 0(0/2) ・・・最も期待値の高いアーム 39 探索 探索 探索 探索 探索 探索 活用 活用 活用 活用 ランダム選択 引くアーム 結果 1 2 3 1 2 3 - アーム1 アーム2 アーム3 アーム1 アーム2
映画:タイタンの逆襲 10680:[2012 04/30 23:43]～[2012 04/30 23:57] : (映画) タイタンの続きだったので一応チェック。 やっぱり、ペガサス萌えの威力がでかいが量が少ない。 がきんちょが玩具の剣を作るのに使った材料が、偶然、宿り木だったりするんですね、分かります、とか先読みしつつ見てたけど、神話違いだった。 どうも展開を練る気が無いようで、冒険活劇と言うよりはコント。 その場面でやることが終わったら、それがどうであれ、画面がワイプして次のシーンへ、みたいな。 もしくは、クリア条件が明確じゃ無いステージ制のゲームを、各ステージ時間切れしてくプレイ動画でも見てるようなすっきりしなさ。 メインとなる大迫力の映像はそれだけで見る価値ありだけど、いまいち、添え物がぱっとしない。 ・・・厳ついおっさんカップリング萌えの人らをメインターゲットに据えてるのか? ・
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回なんて宇宙が消滅するまでに終わらないので、試した
勤務先の社内勉強会で、機械学習を用いた文書推薦*1に関する基本的なことがらについて説明しました。その資料を公開します。 プログラマのための文書推薦入門 from y-uti 数学やコンピュータサイエンスを専門的に学んでいないエンジニアでも理解しやすいように、できるだけ数式を使わずに説明したつもりです。厳密性にはこだわっていないので、専門家からはあちこちツッコミを受ける内容かもしれません。 プログラマ向けということで、実際にコンピュータ上で動作を確認できるように、Wikipedia のデータを対象にして類似文書検索を行うスクリプトを作成しました。GitHub に置いてあります。 y-uti/document-recommendation · GitHub *1:推薦というより情報検索、類似文書検索という方が適切だったかもしれません。
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、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関数として利用できます）。本稿ではこの実装
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Amazon.co.jp: アルゴリズムデザイン: Jon Kleinberg (著), Eva Tardos (著), 浅野孝夫 (翻訳), 浅野泰仁 (翻訳), 小野孝男 (翻訳), 平田富夫 (翻訳): 本
