タグ

関連タグで絞り込む (0)

  • 関連タグはありません

タグの絞り込みを解除

AlgorithmとALgorithmとRubyに関するagwのブックマーク (8)

  • ハッシュは頻繁に参照する値を最後に入れると高速 - まめめも

    明日から RubyKaigi なので、ちょっとした小ネタを一つ。 例えば、0 から 9999 までをハッシュに順に入れます。 h = {} 10000.times do |n| h[n] = true end このとき、h[9998] や h[9999] は、h[0] や h[1] より高速です。 どのくらい高速かというと、 1_000_000_000.times { h } # 40.8 sec (ループ自体の速度) 1_000_000_000.times { h[9999] } # 57.2 sec 1_000_000_000.times { h[0] } # 89.1 sech[0] は 89.1 - 40.8 = 48.3 nsec 、h[9999] は 57.2 - 40.8 = 16.4 nsec ということになります。なんと 3 倍も速い。*1 なぜこんなことが起きるのか ハ

    ハッシュは頻繁に参照する値を最後に入れると高速 - まめめも
  • algorithm

    奥村晴彦さんの「C言語による最新アルゴリズム事典」技術評論社、1991年、の C 言語プログラムの Ruby への翻訳に挑戦します。プログラムの説明は同書を読んでください。変換はできるだけ逐語的に行っています。プログラムの動作は原作の C プログラムのそれと比較してチェックしていますが、うまく動作しないときは C から Ruby への変換のさいに起きたものです。バグレポートは tnomura@mnet.ne.jp までお願いします。 この Ruby 翻訳版はできるだけレイアウトも含めて原作の C プログラムを変更しないようにしたため、必ずしもRuby らしいコーディングスタイルとは言えないかもしれませんが、プログラムがきちんと動作することを優先しました。C から Ruby への翻訳の著作権に関しては Ruby のライセンスに準じます。配布、改変は自由です。ただし、プログラム体には原作者の

  • Rubyで最短経路を探索しよう! - hp12c

    人生を書き換える者すらいた。: 人材獲得作戦・4 試験問題ほか 次に同じ質問がきたときに 「1時間いらないっしょ、こんなの」 と是非ともほざくために 今から勉強します ダイクストラ法による最短経路探索 図におけるS点からG点に到達するための最短経路を求めたい 各ノードを結ぶエッジを糸としてS点をゆっくりと持ち上げた場合 緊張する糸が変移しながら最終的にS−B−D−Gを結ぶ糸が緊張して これが最短経路と分かる*1 計算機上でこの現象をシミュレートしたものを ダイクストラ法というらしい 今各ノードとそこから伸びるエッジの情報(コストと接続先)を渡して その最短経路および総コストを出力するプログラムを考えてみよう data = { :s => [[5, :a], [4, :b], [2, :c]], :a => [[5, :s], [2, :b], [6, :g]], :b => [[4, :s

    Rubyで最短経路を探索しよう! - hp12c
  • Rubyでもっとも重要なライブラリは何か?PageRankで計算してみた - aike’s blog

    最近、PageRankを計算するPHPソースコードを公開している人がいたので、Rubyで書き直してみました。 PHPからRubyへは移植というよりほとんど写経のような感じでそのままポーティングできます。 pagerank.rb #!/usr/bin/ruby # original PHP source http://phpir.com/pagerank-in-php def calculatePageRank(linkGraph, dampingFactor = 0.15) pageRank = Hash.new tempRank = Hash.new nodeCount = linkGraph.length linkGraph.each {|node, outbound| pageRank[node] = 1/nodeCount tempRank[node] = 0 } change =

    Rubyでもっとも重要なライブラリは何か?PageRankで計算してみた - aike’s blog
    agw
    agw 2010/01/18
    結果が面白い。
  • コサイン距離ベースのLSHをRubyで - <s>gnarl,</s>技術メモ”’<marquee><textarea>¥

    参考文献:Web+DB press vol.49 レコメンド特集のPart3など。 アルゴリズムの概要 詳細(特に数学的な)はぐぐれ。 モチベーションとしては、高次元における近傍点探索を高速で行いたい。まじめにやるとどう工夫しても計算量がすごいことになるので、近似で。 どうするかというと、「距離が近いと同じような値になるハッシュ関数」を使う。あるベクトルの近傍を求めたい場合、そのベクトルのハッシュと同じ(もしくは近い)値のハッシュを持つベクトルをテーブルから引いてきて返す。計算量がどうなるかはややこしいけど、とりあえず全部探すよりは速い。 で、どういう関数をハッシュとするのか。これは距離の定義によって異なる。ハミング距離、コサイン距離、ユークリッド距離などにはそういった関数の存在が知られている。 コサイン距離の場合、ランダムなベクトルをいくつか用意して、入力されたベクトルがそれらと似ている

    コサイン距離ベースのLSHをRubyで - <s>gnarl,</s>技術メモ”’<marquee><textarea>¥
  • Rubyの浮動小数点数リテラルの扱いは正しいのか - hnwの日記

    題名の通りなんですが、前回の記事「PHP以外全員不正解」に対して「ダウト!」を頂戴したのでまとめてみます。 Cのこの動作が、唯一無二絶対のものであるとする根拠はどこにあるのでしょうか? strtod によれば、 If the subject sequence has the decimal form and at most DECIMAL_DIG (defined in ) significant digits, the result should be correctly rounded. If the subject sequence D has the decimal form and more than DECIMAL_DIG significant digits, consider the two bounding, adjacent decimal strings L and

    Rubyの浮動小数点数リテラルの扱いは正しいのか - hnwの日記
    agw
    agw 2007/08/04
    大変ためになるエントリ。コメントがまた秀逸。
  • h-index を Ruby で書いてみた - まちゅダイアリー (2007-07-19)

    次世代ゲーム機と21世紀のレゴブロック 2005年の東京ゲームショウでPS3のデモ(MGS4とか)を見たときは、グラフィックは綺麗だけどゲームの面白さがどう変わるのかが分からなかった。 でも、この Little Big Planet というゲームからは新しい面白さを感じる。 【ソ… h-index を Ruby で書いてみた 最近 Ruby のプログラムを書いていなかったので、話題のはてブ指数で使われているH指数を求めるメソッドを書いてみた。 H指数は、配列のなかから「N以上の数がN個以上含まれる」場合の最大のNを求めるもの。 例えば、「5,4,3,2,2,1」…

    h-index を Ruby で書いてみた - まちゅダイアリー (2007-07-19)
  • 配列のシャッフル - 趣味的にっき

    配列のシャッフルについては[ruby-list:40891] 配列をシャッフルからのスレッドが詳しいです。 id:ha-tan:20060517:1147877215では、 class Array def randomize self.sort_by{rand} end endのアルゴリズムを採用しました。

    配列のシャッフル - 趣味的にっき
  • 1