python3はじめました：とりあえずフィボナッチ数列を書いてみる
ふと読み返してみると、いつからこのブログは旅行記になったのだろう、という感じである。
最近マンネリ気味だったので仕方がない。
さて、なんとなく仕事も閑散期を抜けそうな気がするので、私も心新たに新しい言語を試してみている。
python3である。
とりあえず、python tutorialというサイトが充実しているので、これを見ながら勉強している。
4.6関数定義で出てくるフィボナッチ数列の定義が、ちょっとテクニックを使っていて「おっ」と思った。
そこで、自分でも複数パターン、フィボナッチ数列を返す関数を書いてみたので晒してみることにする。
本家のfib関数は、
# write Fibonacci series up to n
ということで、標準出力含めた形のプロシージャとなっているが、ここでは、
引数nに対して、フィボナッチ数列の第n項を返す関数として定義する。
つまり、副作用のない関数にしておく。
こうしたほうが違いがはっきりするだろう。
この形で本家のfib関数と同じロジックで書くと、次のようになる。
def fib_ver1(n): a, b = 0, 1 for i in range(n): a, b = b, a + b return a
いっぽう、ふつう教科書とかにありそうなのは、次のような再帰的な記述だ。
def fib_ver0(n): if n == 0: return 0 elif n == 1: return 1 else: return fib_ver0(n-1) + fib_ver0(n-2)
これは数学的にも、すっきりしていて美しい。
のだが、何回も同じ関数を呼び出すことになり、スタックが有限であるコンピュータの処理的には良くない。
メモ化を使うと次のようになるだろう。
memo = [0, 1] def fib_ver2(n): global memo if len(memo) > n: return memo[n] else: ans = fib_ver2(n-1) + fib_ver2(n-2) memo.append(ans) return ans
グローバルで定義されたリストに、計算結果をメモしておくわけである。
メモリを効率的に使い、ver0で何回も同じことをしていたのを回避している。
for文が死んでもいやであるという純粋主義者がver1を再帰的に書くには、
第n項を返すというインタフェースは諦めて、第n項と第n+1項からなるリストを返すということになるだろう。
def fib_ver1_rec(n): if n == 0 : return [0, 1] else: a, b = fib_ver1_rec(n-1) return [b, a+b]
これを見ると、ver0では再帰呼び出しを2つ行っているのに対して、ver1では再帰呼び出しを1つに済ませているのがよくわかる。
python tutorialの4.6ではさらっと書かれているが、そういう工夫がされていることには、注意を払うべきポイントだと思う。
勉強用サーバ兼ファイルサーバの構築(samba/Ubuntu16.04/Windows10)
思ったより簡単にできてしまったのでメモ。
機材
小さなノートPC（1kg以下。使いやすい。HDD容量30GBくらい）
大きなノートPC（重い。使いづらい。HDD容量500GBくらい）
今までの環境
どっちもOSはWindows10。
小さな方にMS-Officeを入れてexcelで遊んだり、2chみたり、YouTubeみたり。
大きな方にVirtualBox上にUbuntu16.04を入れて、PerlとかC++とかで戯れる。
問題点
「勉強するぞ」ってならないと勉強しない。
Linux上で勉強しててかつexcel使いたいときに、PCを行き来する必要。
VirtualBoxがもっさりしててイライラする。
Ubuntu16.04をインストール(サーバ側)
DVDに焼いて、普通にインストールするだけと思いきや。
デフォルトで「Windows Boot Managerとは別にインストール」という選択肢があり、これでデュアルブートになるらしい。
あまり前の環境に未練はないけど、せっかくなのでデュアルブートにしてみた。
sambaのインストール・設定(サーバ側)
このままTeraTermで全部操作してしまってもOK。
sambaをインストール。
sudo apt-get install -y samba
ログインユーザを追加。
sudo pdbedit -a [追加するユーザ名]
sambaの設定ファイルを編集。
sudo vim /etc/samba/smb.conf
須藤さんに登場してもらわないと、編集できません。
[homes]の下がコメントアウトされているので、有効にする。
readonly属性はnoにしておく。
これでクライアント側からログインすると、/home/[ユーザ名]の下を見られるようになるっぽい。
readonly属性がyesだと見られるだけだね（書き込めない）。
sudo systemctl restart smbd nmbd
クライアント側からディレクトリを見る。
エクスプローラでネットワークを見ると、サーバのPC名が表示されているので、ダブルクリックしてログインする。
あるいは、\\[IPアドレス]と直打ちしてログインしてもOK。
感想
あまりに簡単だったので拍子抜けした。
クライアントサーバシステムとか名前からして凄そうだし、敬遠していた。
まだ分からないけど、捗りそう。
活用していこう。
2017年の目論見
あけましておめでとう。
年は明けて2017年。
今年もよろしくお願いします。
年頭よろしく、今後の目論見なんかを作ってみる。
ブログの更新頻度向上
アウトプットの場としてのブログの利用価値を見直す。
応用情報技術者
4月の試験はこれ。
ネットワークスペシャリスト
10月の試験はこれかな。
正直ネットワークにはあまり興味がないのが辛いところ。
でもネットワーク知らないと、環境構築とかできないし。
機械学習
最近はやり。
やっぱりちょっと興味持っちゃうよね。
C++
結局かじっただけになっているオブジェクト指向言語。
たぶん今後も仕事で付き合うことになる。
コンピュータアーキテクチャ
基本だけど、表面的にしか理解していないことが多い分野という感じ。
今年の終わりには「実感」を持てるようになりたい。
perlで順序を保つグルーピング ～優先度からの解放～
excelでちょっと複雑なソート - studies
perlでちょっと複雑なソート - studies
perlでちょっと複雑なソート2 - studies
perlでちょっと複雑なソート3 - studies
ワンライナーでちょっと複雑なソート - studies
今までタイトルに「ソート」と付けていたように、この問題を「ソート」の問題として解いてきた。
今回は別の視点でこの問題を解いてみよう。
「別の視点で」と書いたが、実は最初からこの問題は必ずしもソートの問題として定義されていたわけではない。
私の書いた問題文はこうだった。
これを、次の条件でソートするのが本日の課題であった。
１．基本的な順番は変えない。
２．同じ都道府県どうしをまとめる。
たとえば、上の例のデータでいえば、次のようにソートすることになる。
１．第4行まではすべて異なる都道府県なので、とりあえずここまでは何もしない。
２．第1行で京都府京都市がでてきたあと、第5行で京都府宮津市が出てくる。同じ都道府県同士をまとめるので、第1行と第2行との間に、この第5行目のデータを挿入する。
重要なのは２の「同じ都道府県同士をまとめる」というところだ。
つまり、この問題はソートの問題ではなくグルーピングの問題であると考えてもよい。
（正確に言えば、グルーピング＋ソートの問題なのだが、どちらに重点を置くか、ということで少し解き方が変わってくるように思う）。
この問題は、グルーピングした結果を表示するときに、元の順序をできるだけ保つようにする、というだけなのだ。
ここでいう「順序を保つ」というのは、最初に出てきたグループを優先し、次にグループ内では最初に出てきたメンバを優先する、ということだ。
これまで、条件１の「基本的な順番は変えない」という点に注目していたが、今回は条件２に着目してみよう。
アルゴリズム的には「たとえば」以下で書かれた方法をほぼそのまま採用する。
このアルゴリズムは優先度を全く使っていないのが特徴だ。
優先度を設定して、その優先度順にソートするというのは、おそらくプログラム的には早いのだが、必ずしも人間にわかりやすいものとは言えない。
今回は、優先度を設定せずに書いたので、直観的なコードになったと思う。
次のようになる。
#! /usr/bin/perl -a push @groups, $F[1] unless grep {$_ eq $F[1]} @groups; push @{$members{$F[1]}}, $_; END { print @{$members{$_}} for (@groups); }
説明する。
最初に@groupsという配列に、第2フィールドの要素（つまり都道府県）をpushしている。
ただし、これを行うのは都道府県が最初に現れた時だけだ。
その判定を、unless grepで行っている。
次に、各都道府県の市区町村（本当は行）を、都道府県から決まる配列にpushしている。
ここで、配列のリファレンスに値を持つハッシュ%membersを使い、それを@でデリファレンスして使っているのがポイント。
リファレンスを使っているのでややこしいが、配列に値を持つハッシュを作っていると思えばOK。
最終的には、こんな感じのハッシュが作られるわけである。
%members =
(
京都府 => [ 京都市 京都府, 宮津市 京都府, 宇治市 京都府 ],
東京都 => [ 千代田区 東京都, 渋谷区 東京都, 新宿区 東京都 ],
.....
)
そして、groupごとに配列を展開してprintして終わり、というのが上のコードの意図するところである。
下のようにkeys関数でグループを求めたくなるが、「Perlでは、ハッシュの要素の順序が保存されない」(『初めてのPerl』, p142)ため、この方法だと、どの順序でグループが現れるかわからなくなってしまう。この方法は使えない。
#! /usr/bin/perl -a push @{$members{$F[1]}}, $_; END { print @{$members{$_}} for (keys %members); # しまった！ }
また、毎回unless grepという条件判定を行うのは重いので、とりあえずpushして、最後に順序を保ちながら重複を取り除く、という考え方もできる。
そのときは、下のように"grep {!$seen{$_}++} @groups"という呪文を唱えることになる。
これは有名なイディオムだが、コード全体の直観性を重視した今回の方針から言えば、ちょっと避けたい書き方ではある。
#! /usr/bin/perl -a push @groups, $F[1]; push @{$members{$F[1]}}, $_; END { print @{$members{$_}} for (grep {!$seen{$_}++} @groups); }
追記：
unless grepという条件判定が遅いことに対しては、exists関数を使って下のように対処するのが良さそう。
grepの計算時間はO(N)だが、ハッシュを使った下の書き方なら計算時間は定数時間O(1)になるハズ。
#! /usr/bin/perl -a push @groups, $F[1] unless exists $members{$F[1]}; push @{$members{$F[1]}}, $_; END { print @{$members{$_}} for (@groups); }
ワンライナーでちょっと複雑なソート
早く目が覚めてしまった。
これは午後眠くなるぞー。
最後の仕上げ？として、perlを使わず、ワンライナーでやってみる。
（もしかしたらまだ続くかも）。
awk '{p[$2] || (p[$2]=NR); print p[$2], $0;}' city.txt | sort -snk1 | sed -E 's/^\S+\s+//'
まず、awkの連想配列を使って、優先度を頭につける。
そのあとsortでソート。
sオプションは、安定ソートにするオプション
（デフォルトはおそらくクイックソートで不安定）。
nオプションは、数値としてソートするオプション
（デフォルトは文字列としてソート）。
kオプションは、特定のフィールドをキーにするオプションで、ここでは第1フィールド、つまり、awkで設定した優先度を指定している。
最後にsedで優先度を削除する。
Eオプションは拡張正規表現を使うオプションで、ここでは1回以上の繰り返しを表す量指定子を\+ではなく単に+と書くために指定している。
個人的には、sortコマンドに、こんなにいろいろなオプションがつけられるというのが発見。
perlの宇宙船演算子<=>を使ったソートルールの指定も感心したけれど、sortコマンドでもこんなにいろいろできたとは。
