読者です 読者をやめる 読者になる 読者になる

studies

いろいろ勉強用備忘録的な感じ

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ではさらっと書かれているが、そういう工夫がされていることには、注意を払うべきポイントだと思う。

京都に行ってきた【東寺・来迎院・宝泉院】

仕事が閑散期なため、ふと思いついて京都に行ってきた。
そうだ、京都行こう。

東寺教王護国寺ともいう。
真言宗のお寺。五重塔の初層が公開されていた。
f:id:developingskills1110:20170114231604j:plain:w300

ところ変わって大原来迎院。
大原エリアではここだけまだ来たことがなかった。
ここは天台宗のお寺。静かで良い。
f:id:developingskills1110:20170114231740j:plain:h300

こちらは宝泉院。ここは3回目かな。
f:id:developingskills1110:20170114231953j:plain:h300

宝泉院は一名を額縁の庭園といい、京都でも屈指の美意識を感じさせる。
今日は額縁の向こうは吹雪いていた。
f:id:developingskills1110:20170114232317j:plain:h300

鎌倉に行ってきた【銭洗弁財天~大仏ハイキングコース~高徳院】

鎌倉に行ってきた。

銭洗弁財天。トライフォース
f:id:developingskills1110:20170109222615j:plain:w300

銭を洗うと金運が上がるらしい。
f:id:developingskills1110:20170109222629j:plain:h300

大仏までのハイキングコースから鎌倉を望む。
f:id:developingskills1110:20170109222635j:plain:h300

大仏。
f:id:developingskills1110:20170109222639j:plain:w300

勉強用サーバ兼ファイルサーバの構築(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がもっさりしててイライラする。

解決策

勉強って言っても基本コマンドラインしか使わないし、大きなPCをサーバにして、小さな方からsshでログインすればOK。
ついでにファイルも共有できる感じにすれば楽しそう。

Ubuntu16.04をインストール(サーバ側)

DVDに焼いて、普通にインストールするだけと思いきや。
デフォルトで「Windows Boot Managerとは別にインストール」という選択肢があり、これでデュアルブートになるらしい。
あまり前の環境に未練はないけど、せっかくなのでデュアルブートにしてみた。

TeraTermssh接続(クライアント側)

サーバ側のIPアドレスを入力して、ユーザ名・パスワードを入力して接続する。
難なく接続できた。素晴らしい。

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だと見られるだけだね(書き込めない)。

vimを閉じたら、sambaを再起動。

sudo systemctl restart smbd nmbd

クライアント側からディレクトリを見る。

エクスプローラでネットワークを見ると、サーバのPC名が表示されているので、ダブルクリックしてログインする。
あるいは、\\[IPアドレス]と直打ちしてログインしてもOK。

ついでにiPhoneからも…

もちろんiPhoneからも見れるはずなので試してみた。
「File Explorer」というアプリをインストールして、ログインすると中身が見える。

感想

あまりに簡単だったので拍子抜けした。
クライアントサーバシステムとか名前からして凄そうだし、敬遠していた。
まだ分からないけど、捗りそう。
活用していこう。

2017年の目論見

あけましておめでとう。

年は明けて2017年。
今年もよろしくお願いします。

年頭よろしく、今後の目論見なんかを作ってみる。

ブログの更新頻度向上

アウトプットの場としてのブログの利用価値を見直す。

応用情報技術者

4月の試験はこれ。

ネットワークスペシャリスト

10月の試験はこれかな。
正直ネットワークにはあまり興味がないのが辛いところ。
でもネットワーク知らないと、環境構築とかできないし。
マスタリングTCP/IP 入門編 第5版

アルゴリズム

どうも基本的なアルゴリズムを知らないような気がしている。
アルゴリズムクイックリファレンス 第2版

機械学習

最近はやり。
やっぱりちょっと興味持っちゃうよね。
ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装

Python

はやりのスクリプト言語
機械学習の本なんかはこれで書かれていることが多いし、必要になるかなと。
入門 Python 3

Haskell

純粋関数型言語
需要は少ないだろうけど、理論的な側面に惹かれている。
すごいHaskellたのしく学ぼう!

C++

結局かじっただけになっているオブジェクト指向言語
たぶん今後も仕事で付き合うことになる。
プログラミング言語C++第4版 Effective C++ 第3版 (ADDISON-WESLEY PROFESSIONAL COMPUTI) Effective Modern C++ ―C++11/14プログラムを進化させる42項目

コンピュータアーキテクチャ

基本だけど、表面的にしか理解していないことが多い分野という感じ。
今年の終わりには「実感」を持てるようになりたい。
コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方 コンピュータの構成と設計 第5版 上 コンピュータの構成と設計 第5版 下

Linux

Linuxは今後も仕事で使うことになる。
今のところは「操作」がそれなりにできる段階。
カーネルに足を突っ込む。


盛沢山すぎる気もするけど、知らないことが多すぎるから、これくらいがちょうどよいという気もする。
がんばるぞー。

perlで順序を保つグルーピング ~優先度からの解放~

excelでちょっと複雑なソート - studies
perlでちょっと複雑なソート - studies
perlでちょっと複雑なソート2 - studies
perlでちょっと複雑なソート3 - studies
ワンライナーでちょっと複雑なソート - studies

今までタイトルに「ソート」と付けていたように、この問題を「ソート」の問題として解いてきた。
今回は別の視点でこの問題を解いてみよう。

「別の視点で」と書いたが、実は最初からこの問題は必ずしもソートの問題として定義されていたわけではない。
私の書いた問題文はこうだった。

これを、次の条件でソートするのが本日の課題であった。

 1.基本的な順番は変えない。

 2.同じ都道府県どうしをまとめる。

たとえば、上の例のデータでいえば、次のようにソートすることになる。

 1.第4行まではすべて異なる都道府県なので、とりあえずここまでは何もしない。

 2.第1行で京都府京都市がでてきたあと、第5行で京都府宮津市が出てくる。同じ都道府県同士をまとめるので、第1行と第2行との間に、この第5行目のデータを挿入する。

 3.そのあとさらに下を見ていくと、長野県諏訪市が出てくる。このデータを長野県松本市のすぐ下に移動する。

重要なのは2の「同じ都道府県同士をまとめる」というところだ。
つまり、この問題はソートの問題ではなくグルーピングの問題であると考えてもよい。
(正確に言えば、グルーピング+ソートの問題なのだが、どちらに重点を置くか、ということで少し解き方が変わってくるように思う)。

この問題は、グルーピングした結果を表示するときに、元の順序をできるだけ保つようにする、というだけなのだ。
ここでいう「順序を保つ」というのは、最初に出てきたグループを優先し、次にグループ内では最初に出てきたメンバを優先する、ということだ。

これまで、条件1の「基本的な順番は変えない」という点に注目していたが、今回は条件2に着目してみよう。
アルゴリズム的には「たとえば」以下で書かれた方法をほぼそのまま採用する。
このアルゴリズムは優先度を全く使っていないのが特徴だ。
優先度を設定して、その優先度順にソートするというのは、おそらくプログラム的には早いのだが、必ずしも人間にわかりやすいものとは言えない。
今回は、優先度を設定せずに書いたので、直観的なコードになったと思う。

次のようになる。

#! /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);
}

ワンライナーでちょっと複雑なソート

早く目が覚めてしまった。
これは午後眠くなるぞー。

さて、excelperlでいろいろやってきたこの問題。

studies.hatenablog.com

最後の仕上げ?として、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コマンドでもこんなにいろいろできたとは。