包装アルゴリズム - Mae向きなブログ
Blogopolisを見ていると，計算幾何について学んでみたくなります。ということで，凸包を求めるプログラムを作ってみました。 今回は，包装アルゴリズム(package wrapping algorithm)を使っています。以前，cairoを使ってみたことがあるので，今回も利用します。 wrapping.rb 包装アルゴリズムについては，以下を参考にしました。 凸包の計算と多角形の面積計算 『アルゴリズムC〈第2巻〉探索・文字列・計算幾何』 # -*- coding: utf-8 -*- require 'my_canvas' # 線分p1p2と水平な直線がなす角度を求める(0〜360) def theta(p1, p2) dx = p2[0] - p1[0]; ax = dx.abs dy = p2[1] - p1[1]; ay = dy.abs t = (ax + ay == 0) ?
Rubyでもカリー化 - 趣味的にっき
関数型言語ラブな人は、Rubyでもカリー化したくなってくると思います(特にHaskellラブな人はその傾向が強いように思います)。ということで、こんなメソッドを書いてみました。 module Kernel def curry(sym, *a1) f = sym.respond_to?(:call) ? sym : method(sym) lambda do |*a2| f.call(*(a1 + a2)) end end end 使い方はこんな感じです。mapの例を見てください。あぁ何て美しいのでしょう。 def add(a, b) a + b end p curry(:add, 2)[3] # => 5 p curry(method(:add), 2)[3] # => 5 p curry(lambda {|a, b| a * b}, 2)[3] # => 6 p (1 .. 10).ma
プログラマにとって「アルゴリズム」や「データ構造」の知識は必須ですか？ - OKWAVE
「作る」能力は必要はないかもしれませんが，「使う」ためにはアルゴリズムやデータ構造の存在を知っていて，理解している必要があると思います。 アクセスメソッドを例に取ると，B-treeを使った方がいい場合もあれば，ハッシュを使った方がいい場合もあります。データ集合の性質によっては，インデックス経由よりもフルスキャンした方が効率がいい場合もあります。それぞれのアルゴリズムがどういう原理で動作していて，従ってどういう特性を持っているかを理解していないと，実際に自分が使う段になって，そのアルゴリズムに適したケースなのかそれとも不適当なのか判断できないのではないでしょうか？ データ構造でも同じことで，あるアプリケーションのデータ構造として，ヒープがいいのか，配列がいいのか，リンクトリストがいいのかは，それぞれの構造の成り立ちと特性を理解していないと判断できないのではないかと思います。 ただ，場合によっ
遺伝的アルゴリズムとは (イデンテキアルゴリズムとは) [単語記事] - ニコニコ大百科
遺伝的アルゴリズム単語 イデンテキアルゴリズム 4.2千文字の記事 28 0pt ほめる 掲示板へ 記事編集 概要分かりやすい例具体的にやってみよう利点と欠点遺伝的アルゴリズムが深く関わる諸作品関連動画関連商品関連項目掲示板遺伝的アルゴリズムとは、生物群が環境へ適応するときの遺伝学的変化の諸概念（染色体の交叉・突然変異・自然淘汰）を問題解決方法に見立ててその解を探る手法である。英語ではGenetic Algorithm（略語でGA）。 概要 問題の解の候補を生物の各個体の遺伝子に見立て、ランダムに生成した各個体の遺伝子を交換や突然変異により解にふさわしい遺伝子を持つ個体を生み出すように処理を進めていく。各個体が環境にどの程度適応しているかを算出し、遺伝子の適応度が高い個体は子孫を残しやすく、適応度が低い個体は子孫を残しにくくすることから遺伝的アルゴリズムと呼ばれる。 厳密解よりも適度に厳密
![遺伝的アルゴリズムとは (イデンテキアルゴリズムとは) [単語記事] - ニコニコ大百科](https://cdn-ak-scissors.b.st-hatena.com/image/square/5bd1fac8d544d19340796767c18bdf23d7d3493d/height=288;version=1;width=512/https%3A%2F%2Fdic.nicovideo.jp%2Fimg%2Fog_b.jpg)
常識を覆すソートアルゴリズム！その名も"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 なん…だと
Ruby: The Little Rubyist TREE (Japanese)
■ Ruby 手習い tree コマンドをつくる 応用編では、Ruby の機能を使って便利な使えるツールを作っていきます。 プログラムの書き方やスクリプトの書き方を文法から勉強しただけでは、作るというときに目的を達成できないことがあります。 プログラミング/スクリプティングに役立つ考え方や、実現方法についても扱っていきます。 ここでは、Ruby の便利な「組み込みクラス」の「Dir クラス」を使います。 ディレクトリとそのディレクトリに所属するファイルを手軽に扱えるので、ぜひ活用してください。 また、プログラミングのテクニックとして、 =再帰的処理= を扱っていきます。 これで、 =ディレクトリ= をうまく扱えるようになります。 目的として tree というコマンドを作成します。 実行例(sample0.txt)は、tree.rb を使った Ruby のソースコードのディレクトリ構造です。
non-Negative Matrix Factorization (NMF) - naoyaのはてなダイアリー
以前に Latent Semantic Indexing (LSI) や HITS 絡みで SVD や主成分分析について少し書きました。 http://d.hatena.ne.jp/naoya/20090212/latent_semantic_indexing http://d.hatena.ne.jp/naoya/20090301/hits LSI では SVD を使って単語文書行列を分解し、低階数近似を行います。これにより、似たような次元をまとめたりといった効果が得られるのでした。自分の考察では HITS も同様のことを行っているという認識でした。 さて、集合知プログラミングを読んでいたら、第10章で "non-Negative Matrix Factorization" (非負値行列因子分解, 以下NMF) という手法が出てきました。NMF も SVD や主成分分析に同じく行列を分解
GoogleのMapReduceアルゴリズムをJavaで理解する
GoogleのMapReduceアルゴリズムをJavaで理解する：いま再注目の分散処理技術（前編）（1/2 ページ） 最近注目を浴びている分散処理技術「MapReduce」の利点をサンプルからアルゴリズムレベルで理解し、昔からあるJava関連の分散処理技術を見直す特集企画（編集部） いま注目の大規模分散処理アルゴリズム 最近、大規模分散処理が注目を浴びています。特に、「MapReduce」というアルゴリズムについて目にすることが多くなりました。Googleの膨大なサーバ処理で使われているということで、ここ数年の分散処理技術の中では特に注目を浴びているようです（参考「見えるグーグル、見えないグーグル」）。MapReduceアルゴリズムを使う利点とは、いったい何なのでしょうか。なぜ、いま注目を浴びているのでしょうか。 その詳細は「MapReduce : Simplified Data Proc
javascript - Mathを再発明してみた : 404 Blog Not Found
2010年09月14日06:30 カテゴリMathLightweight Languages javascript - Mathを再発明してみた 「基本というからには四則演算で三角関数実装しないとねー」と思いつつ書いていたら… C言語による最新アルゴリズム事典 奥村晴彦 [javascript]三角関数の基本 Math.random()を除いてMathを全部再発明しおえたので。 多倍長演算バージョンを作る時の下ごしらえにもなるかも。 下ごしらえ 仕様は Math - MDC アンチョコはもはや最新というにはあまりに古い、しかし代わりなき「C言語による最新アルゴリズム事典」。低レベルな車輪を再発明する人必携! 初期化と定数 定数の精度はおおげさに。 MyMath = {}; MyMath.E = 2.718281828459045235360287471352662497757; MyMat
PFI で2ヶ月のインターンシップに参加してきた - 肉とビールとパンケーキ by @sotarok
8月の頭から先週10月2日まで，Preferred Infrastructure (PFI) でインターンシップに参加してきました． 思えばあっという間でしたが，非常に濃い体験をし，多くのものを得た2ヶ月でした． インターンでなにをやったのか，何を得たのか，自分なりにまとめたいと思います．長文ですみません．結局うまくまとまらなかった．．． エントリー 日記風(w)に，エントリーから振り返りたいと思います．PFIでインターンの募集が始まった，と聞いたのは， @kzk_mover さんか @ichii386 さんの Twitter でのつぶやきからでした． で，まあPFIは太田さんを知ってたりして，素敵な会社だなーと思ってたこともあり，募集要項は「レベルが高い」とTwitterやブクマでも話題だったので受かるかどうか自信はなかったんですが，学生最後の年だし，今年やらなかったらもうインターンもで
Google検索アルゴリズムで生態系崩壊を予測 | WIRED VISION
前の記事 「飛行機からレーザーで地上攻撃」実験に成功 Google検索アルゴリズムで生態系崩壊を予測 2009年9月 8日 Hadley Leggett 写真：Flickr/fusion68k、イラスト：PLOS Computational Biology。サイトトップの画像は海藻を食べるマナティ。画像はWikimedia Commons 生物学者たちは、生態系を破壊する最も効率的な方法を見い出した――Google社の検索アルゴリズムに基づいてだ。 食物網の要になる生物種が絶滅すると、生態系全体の崩壊を引き起こす危険性があるということは、以前から科学者の間では知られていた。だが、種の相互作用は無数ともいえるほど存在するため、どの動物や植物がいちばん重要なのかを推測することは難しい。 [現在の群集生態学では「食物連鎖」という言葉より、食物網という概念の方が現実的なものとして重視されてきている
ダイクストラ法による最短路検索 - yasuhisa's blog
昨日までに書いていたグラフはコストとかそういうの考えていなかったんだけど、ダイクストラをやろうということでコストも考えることにしました。ダイクストラでedgeとそこまでの距離のhashを作りながら、そこまでのを記憶しておくhashも用意。最短路を探す時にはそれを逆向きに再帰で探していきます。 # -*- coding: utf-8 -*- require 'pp' class Graph def initialize(edges=[]) @edges = edges @nodes = Hash.new{|h,k| h[k] = []} @weights = Hash.new{|h,k| h[k] = {}} end def add_edge(edge) @edges.push edge unless @edges.index(edge) end def add_node(u, v) add
Ruby: Puzzle 8 Queen (Japanese)
■ Ruby で 8 Queen パズル 8 Queen は、コンピュータで扱うのも有名な題材になっています。 多くの参考文献にとり上げられているのでどこかで目にしていると思います。 ここでは、Ruby を使ってこの題材を扱ってみたいと思います。 ぜひ自分で作成してみてください。 パズル 8 Queen ヒント ソースコード 解説 スレッドを使う ■ パズル 8 Queen チェスの「Queen」は、将棋の「飛車」と「角」を合わせた効き筋をもっています。 このため「縦」「横」「ななめ」に自由に動けます。 ここで、チェスの盤上(8 Queen の場合には 8 x 8 の盤を想定)に、それぞれの Queen が、他の Queen の効き筋にぶつからないように、8 個の Queen を配置します。 この配置の方法は、いくつあるでしょうか? 次のものが実際の解答の一つです。 +--+--+--+-
ぼちぼち散歩 いろんな言語で連想配列を列挙
文字列操作の比較表: Ruby, Python, JavaScript, Perl, C++が面白かったのでマネしてわかる範囲でいろいろやってみた． 目次 Ruby PHP JavaScript Python C++ Java Objective-C + Cocoa まとめ Ruby コード hash = { "key1" => "value1", "key2" => "value2", "key3" => "value3" } hash.each() {|value, key| print value + " : " + key + "\n" } 実行結果 key1 : value1 key2 : value2 key3 : value3 Rubyはすべてがオブジェクトなので，配列もArrayクラスのインスタンスということになってる．で，eachメソッドにコードブロックを引数として与える
k近傍法 - Wikipedia
k近傍法（ケイきんぼうほう、英: k-nearest neighbor algorithm, k-NN）は、入力との類似度が高い上位 k 個の学習データで多数決/平均するアルゴリズムである[1]。 パターン認識（分類・回帰）でよく使われる。最近傍探索問題の一つ。k近傍法は、インスタンスに基づく学習の一種であり、怠惰学習 の一種である。その関数は局所的な近似に過ぎず、全ての計算は分類時まで後回しにされる。また、回帰分析にも使われる。 概要[編集] k近傍法は以下の手順からなる： 入力と全学習データとの類似度（距離）測定 類似度上位 k 個の選出 選出されたデータの多数決あるいは平均 すなわち「入力とよく似た k 個のデータで多数決/平均する」単純なアルゴリズムである[1]。 例えば環境（気温/湿度/風速）から天気（雨/曇り/晴れ）を予測する分類問題を考える。k=5 のk近傍分類では、過去10
研究に少し行き詰まったので再帰で遊ぶ - 元データ分析の会社で働いていた人の四方山話
未だに再帰がよく理解しきれていない若輩者なのですが・・・ 研究の気分転換に少し再帰を勉強する。 Algorithms with Python / 再帰定義 で、再帰の何が分かってないかよく分かっていなかったかだけど、根本的に再帰の動作が分かっていませんでした。 そのために、普通の再帰と末尾再帰の違いがよく分かっていなかったというしょうもない罠でした。 再帰呼び出しのあとに「後に続く処理」がなければ、情報を保存する必要がなくなるわけだ。 こういう呼び出しが「末尾呼び出し」であり、再帰呼び出しすべてが末尾呼び出しであれば「末尾再帰関数」というらしい。 http://http://d.hatena.ne.jp/jyukutyo/20081111/1226368924 実にわかりやすい解説だ。 というわけで、フィボナッチ数列を求めるプログラムの時間を計測してみる。 http://hamasta.g
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
将棋から観る人間とソフトの思考
http://www.sisutsuku.com/
IBM Developer
https://userweb.mnet.ne.jp/tnomura/algo/dijkstra.rb