Rubyでバブルソートを書いてみる
バブルソートのアルゴリズム
- 作者: 紀平拓男,春日伸弥
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/03/30
- メディア: 単行本
- 購入: 15人 クリック: 255回
- この商品を含むブログ (31件) を見る
書籍を参考にバブルソートのアルゴリズムをRubyで書いてみる。
（この書籍にはCとJavaのコードが載っている）
バブルコードの解説は以下のページも丁寧。
Oyster Harbor | バブルソート(Bubble sort)
簡単に流れを説明すると
配列の先頭から、二つの要素を比較する。順序が不正であれば入れ替える。
最後まで辿り着いたら、再び先頭から。
一度も入れ替えが発生しなければソート完了。
Rubyのコード
配列を引数に取る関数として書くと
def bubble_sort(ary) begin swapped = false 0.upto(ary.size - 2) do |i| if (ary[i] > ary[i + 1]) ary[i], ary[i + 1] = ary[i + 1], ary[i] swapped = true end end end while swapped ary end
だが、このやり方は「ループが1回終了するごとに、配列の後方がソート済みになってくる」ので、 この部分は調べる必要がない。
def bubble_sort(ary) k = 0 # k: 配列後方、ソート済み要素の数 begin swapped = false 0.upto(ary.size - 2 - k) do |i| if (ary[i] > ary[i + 1]) ary[i], ary[i + 1] = ary[i + 1], ary[i] swapped = true end end k += 1 end while swapped ary end
実行例。
[2] pry(main)> ary = [*1..10].sort_by {rand}
=> [7, 3, 5, 6, 2, 10, 4, 8, 1, 9]
[3] pry(main)> bubble_sort(ary)
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
計算量
Oyster Harbor | バブルソート(Bubble sort) によると、
時間計算量
まず一つのデータの位置を確定するのに、 (n-1) 回の比較が必要です。 次は比較回数が1回少なくなるので、 (n-2) 回の比較が必要です。 これの繰り返しが平均時間計算量になります。...（中略）...
O(n2) であることがわかります。
空間計算量
空間計算量は内部ソートなので、外部メモリを使わずにソートできます。 必要なメモリはデータn個を格納するための領域のみです。 つまり、空間計算量は O(n) であることがわかります。
参考情報：
- 作者: 紀平拓男,春日伸弥
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/03/30
- メディア: 単行本
- 購入: 15人 クリック: 255回
- この商品を含むブログ (31件) を見る
ufwでファイアウォール設定、管理
ufwとは
ファイアウォールの設定、管理はiptablesコマンドを用いるが、よりシンプルなufwコマンドを利用することもできる。
ufwはPythonで書かれたiptablesのフロントエンド。内部的にはiptablesを利用し、iptablesよりも単純なインターフェースを提供している。
インストール
Ubuntuにはパッケージがある。
CentOS用のufwパッケージは存在しないが、ソースコードからインストールできる。
wget https://launchpad.net/ufw/0.35/0.35/+download/ufw-0.35.tar.gz
tar zxf ufw-0.35.tar.gz
cd ufw-0.35
sudo python ./setup.py install
sudo chmod -R g-w /etc/ufw /lib/ufw /etc/default/ufw /usr/sbin/ufw
最後のコマンドは、ufwコマンド実行時に「WARN: /etc/default/ufw is group writable!」という警告が表示されないように実行。
ufwを利用する場合は/lib/ufw/ufw-initスクリプトを利用するので、iptables ip6tablesサービスは停止して、自動起動設定を解除する。
sudo service iptables stop
sudo service ip6tables stop
sudo chkconfig --del iptables
sudo chkconfig --del ip6tables
...CentOS 7以降は以下かもしれない（未確認）
sudo systemctl stop firewalld
エディタで/etc/rc.localを開き（要sudo）
/lib/ufw/ufw-init start
と追記。これでCentOSブート時にufwで設定したパケットフィルタリングが自動的に有効になる。
初期設定
sudo ufw default reject # まず「外部からの通信は拒否する」というデフォルトルールを設定する
sudo ufw allow 22 # ssh接続を許可するため22番ポートを解放
sudo ufw enable # 設定を有効化
その他の設定例
sudo ufw allow 80 # httpのために80番を開ける
sudo ufw allow http # 上記と同じ意味
sudo ufw allow 80/tcp # tcp80番だけ開ける（udpは開けない）
sudo ufw allow 80,443/tcp # コンマ区切りで複数ポート指定
sudo ufw allow 8080:8083/tcp # コロンで範囲指定
ルール設定のシンタックス
前述のような書き方（シンプルシンタックス）の他にフルシンタックスがある。
sudo ufw allow 80/tcp # シンプルシンタックス
sudo ufw allow proto tcp to any port 80 # フルシンタックス
IPアドレスを指定する場合は、上記のto anyをto xxx.xxx.xxx.xxxとしてやれば良い。
またfromを用いて接続元IPを指定してルールを追加することもできる。
sudo ufw allow proto tcp from 192.168.0.101 to any port 3306
状態とルール一覧確認
$ sudo ufw status
Status: active
To Action From
-- ------ ----
1337 ALLOW Anywhere
22 ALLOW Anywhere
1337 (v6) ALLOW Anywhere (v6)
22 (v6) ALLOW Anywhere (v6)
sudo ufw satus numberedとすると番号付きでルール一覧を表示する。
ルール削除
sudo ufw delete 2 のようにufw deleteコマンドにルール番号を渡す。
ルールの優先度と挿入
ufw status numbersで一覧を表示した際により上にあるルールの方が優先される。
優先度を変えて新しいルールを挿入したい場合はufw insert 番号として、新しいルールを挿入する。
sudo ufw insert 1 reject from 192.168.179.4 to any port 1337
参考書籍
Ruby on Rails環境構築ガイド, Chapter13 ファイアウォール
- 作者: 黒田努
- 出版社/メーカー: インプレス
- 発売日: 2013/03/22
- メディア: Kindle版
- この商品を含むブログを見る
vagrant sshでの接続情報を~/.ssh/configに書く
vagrantで立ち上げた仮想マシンにsshログインするには通常vagrant sshコマンドを使うが、
vagrant ssh-configコマンドを実行すると、
Host default
HostName 127.0.0.1
User vagrant
Port 2222
UserKnownHostsFile /dev/null
StrictHostKeyChecking no
PasswordAuthentication no
IdentityFile "/Users/xxx.../.vagrant/machines/default/virtualbox/private_key"
IdentitiesOnly yes
LogLevel FATAL
とのように出力されるので、この内容を~/.ssh/configに書くと、
この場合であれば、ssh defaultと打てばログイン可能。
ファイル転送であれば scp file_name vagrant@default:~ のようにして可能。
/vagrantの共有ディレクトリで用が足りるならそれで。
参考サイト weblabo.oscasierra.net
ssh公開鍵認証の設定
Webに溢れている情報ではあるがメモしておく。 ssh通信時にパスワード入力が不要になる。
SSH鍵ペア作成
ssh接続元の環境で、
~/.ssh/id_rsa, id_rsa.pub が存在しないなら
ssh-keygen
で公開鍵、秘密鍵を制せする。パスフレーズを入力が求められる。
公開鍵をリモートマシンに設置
scp ~/.ssh/id_rsa.pub user_name@host_name:~
リモートマシンにログインして.ssh/authorized_keysに公開鍵を書き込む。
モードの設定も適切に。
mkdir -p -m 700 .ssh
cat id_rsa.pub >> .ssh/authorized_keys
chmod 600 .ssh/authorized_keys
rm id_rsa.pub
認証エージェント(ssh-agent)に秘密鍵を覚えさせる
ssh-agentはOSX, Ubuntuの場合、OSにログインした時から常駐している。 起動させるには
eval `ssh-agent`
ssh-addコマンドで、ssh-agentに秘密鍵を覚えさせる。
コマンドを実行すると秘密鍵を解くためのパスフレーズ入力を求められる。
以上設定すると、以後、sshでリモートホストにログインする際にパスワード入力が不要になる。
期待通り動作しない場合は、.sshディレクトリの所有権やモードが正しいか調べてみる。
リモートホストのユーザ認証関連のログを調べてみるのも良い。
安全のためにPCの前から離れる時はssh-add -Dで全ての秘密鍵を忘れさせると良い。
SSHクライアントの設定ファイル(~/.ssh/config)
Host example.com
User your_name
Port 22 # デフォルト22なのでこれは書かなくても良いが
Host *
ForwardAgent yes
ServerAliveInterval 300
ForwardAgentをyesにすると、リモートホストから更に別のリモートホストに接続、を繰り返しても認証エージェントを引き継げる。リモートホストには公開鍵を設置しておけば、秘密鍵を設置する必要はない。
ServerAliveIntervalはSSHクライアントからリモートホストに返答を要求するメッセージを送る感覚を指定する（秒単位）。デフォルトは0で、メッセージは送られない。ネットワーク環境によりssh接続が切れやすい場合、設定しておくと良い。
参考書籍
Ruby on Rails環境構築ガイド, 黒田努, 2013
- 作者: 黒田努
- 出版社/メーカー: インプレス
- 発売日: 2013/03/22
- メディア: Kindle版
- この商品を含むブログを見る
