pythonで順序を保つグルーピング
恒例の?問題をpythonでやってみる。
使うアルゴリズムは、perlで最後にやったのと同じ(いちおうバケットソートといえるだろうか?)
studies.hatenablog.com
pythonのcollectionモジュールにあるOrderedDict(順序付き辞書)を使うと楽に書ける。
OrderedDictについての説明は以下にある。
8.3. collections — コンテナデータ型 — Python 3.6.1 ドキュメント
通常の dict メソッドをサポートする、辞書のサブクラスのインスタンスを返します。 OrderedDict は、キーが最初に追加された順序を記憶します。新しい項目が既存の項目を上書きしても、元の挿入位置は変わらないままです。項目を削除して再挿入するとそれが最後に移動します。
さて、書いたコードは以下の通り。
#! /usr/bin/python3 import fileinput from collections import OrderedDict pref_to_cities = OrderedDict() for city in fileinput.input(): pref = city.split()[1] if pref not in pref_to_cities.keys(): pref_to_cities[pref] = list() pref_to_cities[pref].append(city) for cities in pref_to_cities.values(): print(*cities, sep="", end="")
以前perlで書いたコードと比べると、ダイヤモンド演算子や組み込みの変数が少ないのと、インデント強制のため、少し長いコードになっている。
しかし、以前は順序を覚えておくためだけに無駄な配列を作っていたのに比べれば、問題に最適なデータ構造を選択できていて、よい。
pythonとhaskellで素数のリストを作ってみる
今回はメモ程度。
リスト内包表記と、filter, mapを使った書き方。
>>> [n for n in range(2,100) if 0 not in [n%d for d in range(2,n)]] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] >>> list(filter(lambda n: 0 not in map(lambda d: n%d, range(2,n)), range(2,100))) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Prelude> [n | n <- [2..100], not $ 0 `elem` [n `mod` d | d <- [2..n-1]]] [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] Prelude> filter (\n -> not $ 0 `elem` map (n `mod`) [2..n-1]) [2..100] [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
pythonはリスト内包表記のほうがすっきり。
というか、lambdaキーワードが長すぎて…。
haskellはどっちも似たようなものかな~。
pythonにはこんなことできないかな?
Prelude> take 30 $ filter (\n -> not $ 0 `elem` map (n `mod`) [2..n-1]) [2..] [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]
フィボナッチ数をたくさん出力すると放物線が現れる件
前回、pythonを使ってフィボナッチ数の第n項を返す関数をいくつかのバリエーションで実装した。
ところで、pythonではメモリが許す限りいくらでも大きな整数を扱うことができる。
調子に乗って、前回作った関数でフィボナッチ数を(各項の間にスペースを一個入れながら)、大量に出力してみていると、面白いことに気づいた。
放物線が現れるのである。
おお。
なんだこれは。
若干の感動を覚えつつ、少し考えてみると理由が分かった。
おおざっぱに説明してみよう。
フィボナッチ数列をとかく。
フィボナッチ数列の漸化式を解くと、一般項は、
である。ここでは黄金比である。
であり、したがってであるから、
ゆえに、nが十分大きいとき、
と評価される。
つまり、nが十分大きくなると、その挙動は「指数関数的」になる。
いま、各項は10進数でコマンドラインに表示しているので、各項の桁数はである。
先の評価も考慮すれば、第n項の桁数は
で評価されることが分かる。
つまり、フィボナッチ数の各項の桁数はおおよそ「線形」に増えていく。
ところで、上のコマンドラインに放物線が現れたのは、スペースがある適当な間隔で表示されたことが直接の原因である。
ここで、「適当な間隔」というのは、ここまでで議論してきたフィボナッチ数の各項の桁数であり、それはおおむね線形に増加しているのだった。
そこで、長さがの文字列を繰り返し表示すれば(そして、各文字列のあいだに適当な文字を挟めば)、別にフィボナッチ数列でなくても、同じように放物線が現れそうだと予想がつくだろう。
以下のコードで試してみると、確かにそうなっている。
for i in range(200): print(" "*i, end="*")
では、なぜこのような状況で放物線が現れるのか。
次の図で説明する。
コマンドライン下に向かってx軸を、右に向かってy軸をとる。
コマンドラインの左端がで、右端がである。
各*はxが整数である点に現れていると考え、その座標を、とする。
上で定義した状況は、図に示した赤色の線の長さの合計が線形に増加する、という状況だから、次のように言い換えられる。
数列は、等差数列である
これは、Cという定数を抜きにして考えることで、すぐに次のように言い換えられる。
数列の階差数列は、等差数列である
したがって、
が分かり、これにより、放物線が現れることが説明される。
(ほんとうは、離散的な点集合のみで、線は一つも現れてないですけどね)。
あまり、正確には議論していないですが、今日のところはTeXを初めて書いた面倒くささなどもあり、これで
ということで許してください。
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。
感想
あまりに簡単だったので拍子抜けした。
クライアントサーバシステムとか名前からして凄そうだし、敬遠していた。
まだ分からないけど、捗りそう。
活用していこう。