ruby
1.重複順列を数え上げる array.repeated_permutation(n) {|arr| block } 2.配列からブロック戻り値が最大となる要素を返す enum.max_by {|item| block } 最小はmin_by。 enum.min_by {|item| block } 3.配列からインデックスと要素を取り出す enum.each_with…
1.コンパイルに必要なものをインストール yum -y install gcc zlib-devel openssl-devel sqlite sqlite-devel2.rubyをダウンロード cd /usr/local/bin wget http://cache.ruby-lang.org/pub/ruby/2.1/ruby-2.1.5.tar.gz3.解凍する tar xvfz ruby-2.1.5.tar.g…
配列の等価比較 a = [1, 2, 3] b = [1, 2, 3] a == b #=> true 配列の出力 [4,5,6].join(' ') #=> "4 5 6" 配列の合計 [1,2,3,4,5,6,7,8,9,10].inject(:+) #=>55 文字をすべて数字に置換 ["1","2","3"].map(&:to_i) #=>[1, 2, 3] 要素を選択 [1,2,3,4,5,6,7,…
ハッシュと挿入ソートを組み合わせたソートである。 ハッシュ関数により、要素をいくつかの小さいバケツに分ける。 そして、それぞれのバケツの中で挿入ソートを行う。 挿入ソートはO(n^2)なので、それぞれのバケツ中の要素数が少ないほど高速。したがって、…
別名「数え上げソート」と呼ばれ、その名のとおりそれぞれの要素がいくつあるかを数えていく。 数え上げた結果の累積分布表と原配列を参照し、要素の挿入を行うことでソートが完了する。 そのため、数値を比較する必要がなく高速にソートを行える。今回は累…
10/28-11/4 スタック キュー リスト 解説(11/4 14:00-16:00) 11/5-11/10 二分木 解説(11/10 14:00-16:00) 11/11-11/17 セット 解説(11/17 14:00-16:00) 11/18-11/24 ソート 解説(11/24 14:00-16:00) 11/25-11/30 探索 解説(11/30 14:00-16:00) 12/1-12/14 グ…
ソート済みの２つの配列をマージ（結合）することでソートを行う。 配列を２つに分割するため、分割統治法を用いているソートとなる。 計算量はO(nlogn)であり、傾向はヒープソートと同じである。 しかし、配列の左部分をバッファに退避するため、要素数に比…
中央値ソートをベースに処理を簡単にしたソート。 平均計算量はO(nlogn)であるが、最悪時はO(n^2)となる。 アルゴリズムとしては分割統治法に分類される。今回は高速化のため、以下の点に取り組んだ。 ・再帰処理を省くためループで実装 ・3つの値から中央値…
単純挿入ソートの発展版。 整列されていればされているほど高速になるため、 部分的に単純挿入ソートを繰り返すことで性能を向上させる。クイックソート登場前は最速のソートだったらしい。 #rubyでループをうまく書けず簡潔でないコードになっている #挿入…
2番目の要素から先頭に向かって適当な位置に挿入をしていく。 計算量はO(n^2)。 最良時はそれぞれの要素が適当な位置に収まっていることを確認するためのO(n)。 ソート済みの部分が多いときは高速だが、要素を１つずらすコストが高い。 したがって、ランダム…
最小の値を選択して、先頭から順番に交換していく。 計算量はO(n^2)。離れた要素の交換が発生する可能性があるため 安定ではない def selectionsort!(array) 0.step(array.size - 1, 1) do |head| indexOfMin = array.size - 1 (array.size - 1).step(head, …
となりの要素が大きければ、となりの要素と交換を繰り返す。 計算量はO(n^2)。 安定的なアルゴリズム。 #最後に入れ替えが発生した場所を記憶しておくことで、 #それより前の場所では入れ替えの必要がないことが分かる。 #今回は実装していない。 def bubble…
ポインタではなく配列を利用した単方向リスト。 空き領域の管理が面白かった。
ポインタを利用した単方向リスト。 容易に可変長のリストが作れるかわり、メモリ消費量が増えます。 操作を限定すればキューとしても、リストとしても使用できます。 発展版として、双方向リストや循環リスト、二分木が存在します。
First In First Outのデータ構造です。 リングバッファ版は空き領域を埋めるためにずらす処理が不要となるため、通常の配列を使用した実装より高速です。
Last In First Outのデータ構造。 データを取り出すと最後に追加したデータが取り出されます。
10/28-11/4 スタック キュー リスト 解説(11/4 14:00-16:00) 11/5-11/10 二分木 解説(11/10 14:00-16:00) 11/11-11/17 セット 解説(11/17 14:00-16:00) 11/18-11/24 ソート 解説(11/24 14:00-16:00) 11/25-11/30 探索 解説(11/30 14:00-16:00) 12/1-12/14 グ…
メソッド メソッド 処理 Object#methods メソッド一覧出力 Comparable#between? 引数で与えられた値の間にあるか判定 Numeric#coerce 型を変換して配列にして返す Numeric#eql? 型が等しく、かつ、値が等しいか判定 Numeric#nonzero? 自身がゼロのときnil,そ…
Rubyで簡単なCGIを作った際にしょっぱいミスが多かったので、メモを残しておく。 数値と文字列を連結する際には、数値をto_sで文字列に変換する 行末のセミコロンは不要 入力末尾の改行コードはchompで捨てる ループのための構文は loop do N.times N.times …
