Movatterモバイル変換

riocampos id:riocampos

algorithmに関するriocamposのブックマーク (4)

プログラミング言語RubyのArray#sortは何というソートアルゴリズムで実装されていますか？ - 現在の最新版であるruby1... - Yahoo!知恵袋
現在の最新版であるruby 1.9.3-p125のソースコードを読みました。結論から言うと、クイックソートだと思います。 http://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88 以下、詳細を書きます。 Arrray#sortはArray#sort!を用い(array.c)、Array#sort_by!はEnumerable#sort_byを用いています(enum.c)が、実際にソートを行なっているのはutil.c内の voidruby_qsort(void, const size_t, const size_t, int (*)(const void*, const void*, void*), void *) ですね。 qsortという名前はquicksor
riocampos2014/12/08
クイックソートで実装されてるらしい。
algorithm
Ruby
資料
リンク
多項式時間素数判定アルゴリズム
ＡＫＳアルゴリズムと PRIMES is in Pに関する解説のページです以下の説明は、元論文を参照しながらお読みください。元論分のサイト：Manindra Agrawal, Neeraj Kayal and Nitin Saxena, PRIMES is in P, the original version of the paper. アルゴリズムの基本となるアイデアアルゴリズムの概要 AKS アルゴリズム使用する用語と記号アルゴリズムの動作概要アルゴリズムの正当性の証明概要アルゴリズムの正当性の証明の蛇足説明アルゴリズムの正当性の証明詳細のための準備 PRIMES is in P セクション３の解説 Lemma 3.1. Lemma 3.1.(fact 1) Lemma 3.1.(fact 2) Lemma 3.1.(fact 3) Lemma 3.1.(fact 4
riocampos2014/09/01
『多項式時間の素数判定アルゴリズムとしては史上初のもの』そうなんだー
algorithm
資料
リンク
計算機プログラムの構造と解釈第二版
[ 目次, 前節, 次節, 索引 ] 2014-03-06 更新 [ 目次, 前節, 次節, 索引 ]
riocampos2014/06/19
programming
資料
科学
algorithm
リンク
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。はじめに PowerPC 系やAlpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
riocampos2014/05/26
ループせずにビットカウントできる方法はすばらしいですね。ビットシフトというものが強力なツールであるということ。
programming
tips
資料
algorithm
リンク
1