#!/usr/bin/env python
# -*- coding: utf-8 -*-
import Image, urllib2
from cStringIO import StringIO
url = 'http://www.google.co.jp/intl/ja_jp/images/logo.gif'
buffer = urllib2.urlopen(url).read()
img = Image.open(StringIO(buffer))
fp = open(url.split('/')[-1], 'w')
if img.info.has_key('transparency'):
img.save(fp, transparency=img.info['transparency'])
else:
img.save(fp)
fp.close()
メモ
- ・Image.open()にはバッファで投げる。
- ・そのままだと透過色が保存できない。img.infoから引っ張る。
プレゼンで自社商品の画像が使いたかったので、BeutifulSoupと組み合わせてサイト上の商品画像を全部落っことすスクリプト書いた。
Pythonで多次元リストを作るときに、どうすれば見栄えがよいか、ということを小一時間考えていました。
一次元の簡単なリストであれば、
>>> map(lambda x: 0, range(5)) [0, 0, 0, 0, 0] >>> [0]*5 [0, 0, 0, 0, 0]
[0]*5は非常に簡単でいいのですが、参照「先」に対する操作を行うときには少し気を付ける必要があります。この方法で生成されたリストの要素は、すべて同じインスタンスを指しているからです。
>>> a = [[]]*5 >>> a [[], [], [], [], []] >>> a[1].append(1) >>> a [[1], [1], [1], [1], [1]]
したがって、この記法で多次元リストを作ることはできません。多次元リストのようなものはできますが、多次元リストとして使うことはできません。すべての行が、ただ一つの実体を参照しているからです。
>>> a = [[0]*3]*2 >>> a [[0, 0, 0], [0, 0, 0]] >>> a[1][1] = 3 >>> a [[0, 3, 0], [0, 3, 0]]
こんなときは、おそらくリスト内包表記を使うのが一番簡単だと思います。ただ、これは次元が増えると大変です。入れ子となった内包表記を全て一行におさめる必要があるからです。
>>> a = [ [ [] for j in range(0,3) ] for i in range(0,2) ] >>> a [[[], [], []], [[], [], []]] >>> a[1][1] = 3 >>> a [[[], [], []], [[], 3, []]]
結局、考えていたことというのは、次元が増えたときにはdeepcopy()を使うしかないのか?ということです。何か代替があってもよさそうな気がするんですが。
import copy
def hyperlist(dimension=(), baselist=[]):
if dimension:
return hyperlist(dimension[1:], [ copy.deepcopy(baselist) for i in range(0, dimension[0]) ])
else:
return baselist
# dimension : dimensions (x, y, z, ...)
# beselist : Initial Entity (You can use it individually)
>>> a = hyperlist((4,3,2)) >>> a [[[[], [], [], []], [[], [], [], []], [[], [], [], []]], [[[], [], [], []], [[], [], [], []], [[], [], [], []]]] >>> a[1][1][1].append(3) >>> a [[[[], [], [], []], [[], [], [], []], [[], [], [], []]], [[[], [], [], []], [[], [3], [], []], [[], [], [], []]]] >>> a[1][2][2] = 4 >>> a [[[[], [], [], []], [[], [], [], []], [[], [], [], []]], [[[], [], [], []], [[], [3], [], []], [[], [], 4, []]]] >>> a[0][0][0].append([1,2]) >>> a [[[[[1, 2]], [], [], []], [[], [], [], []], [[], [], [], []]], [[[], [], [], []], [[], [3], [], []], [[], [], 4, []]]]
PIL(Python Imaging Library) は、Pythonインタープリタ用の画像処理ライブラリ群。これを使うとPythonで多くの形式のファイルを読み取って相互に変換できたり、非常に便利。
例えば、RGB画像を開いてその画素値を配列で取得するには、
import Image filename = "xxx.xxx" im = Image.open(filename) print list(im.getdata())
輝度表現に変換。
im = im.convert("L")
print list(im.getdata())
輪郭検出フィルタを適用して保存。
import ImageFilter im_contour = im.filter(ImageFilter.CONTOUR) savefilename = "yyy.yyy" im_contour.save(savefilename)
フィルタを自分で定義することもできます。ImageFilter.CONTOURは8方向ラプラシアンフィルタ(画素値の変化分の変化分を検出)ですが、4方向のものが使いたいときには、
from ImageFilter import BuiltinFilter
class LAP4CONTOUR(BuiltinFilter):
name = "Lap4Contour"
filterargs = (3, 3),1, 255, (
0, -1, 0,
-1, 4, -1,
0, -1, 0
)
im_l4contour = im.filter(LAP4CONTOUR)
im_l4contour.save(savefilename)
また、簡単なフィルタはクラスにしなくても作れます。下は4方向ラプラシアンを用いた鮮鋭化フィルタ。
from ImageFilter import Kernel f = Kernel((3,3), (0, -1, 0, -1, 5, -1, 0, -1, 0), 1, 0) im_l4edge = im.filter(f) im_l4edge.save(savefilename)
それぞれの値の意味は、
class SomeFilter(BuiltinFilter):
name = "SomeFilter"
filterargs = matrixsize, scale, offset, matrix
f = Kernel(matrixsize, matrix, scale, offset)
# matrixsize フィルタ行列の大きさをあらわすタプル (3,3) または (5,5)
# matrix : フィルタ行列
# scale : フィルタ後の画素値はscaleで除算される 省略された場合はフィルタ行列の和
# offset : scaleで除算した後、この値を足す 下地の画素値
ちょっとHTMLをパースする必要があったので、BeautifulSoupを使ってみました。参考にさせていただいたサイトはこちら。
あかさかランチにっき: BeautifulSoupによるスクレイピングの練習
あかさかランチにっき: 続・BeautifulSoupのスクレイピングの練習
Perl使いのPythonちゃん: BeautifulSoupでHTML解析
Perl使いのPythonちゃん: PythonでGoogleの表示順位を取得
特定タグの抽出
>>> from BeautifulSoup import BeautifulSoup
>>> import urllib2
>>> url = 'http://www.crummy.com/software/BeautifulSoup/documentation.html'
>>> html = urllib2.urlopen(url).read()
>>> soup = BeautifulSoup(html)
>>> soup('h1')
[<h1>Beautiful Soup Documentation</h1>]
特定のタグを抽出したいときには、上のリンク先の例にあるようにfindAll()を使うこともできる。抽出した結果には抽出タグ自身も含まれている。これを取り除くにはrenderContents()を使う。
>>> for s in soup('h1'):
... s.renderContents()
...
'Beautiful Soup Documentation'
特定タグについてさらに絞りこんで抽出
それぞれのタグについて、条件をつけてさらに絞りこみたいときにはディクショナリが使える。アンカータグでクラスが "l" のものを絞りこみ、リンク先URLとアンカーテキストからなるタプルのリストを返すには次のように書く。 (Googleの検索結果表示画面で、外部リンク先へのアンカータグのクラスは "l"。したがって、Googleの検索結果をsoupに入れておけば、URLとタイトルの組からなるリストができる）
[(_a.get('href'), _a.renderContents()) for _a in soup('a', {'class' : 'l'})]
HTMLの本文のみを抽出
renderContents()は、子要素のタグも含めて文字列にする。アンカータグ内で b タグなんかが使われていると、「***<b>***</b>」のような文字列が返ってきてしまう。
BeautifulSoupによってHTMLが木構造に分解されたとき、それぞれの要素は自分の子要素（タグで囲まれた部分）をcontentsというリストとして持っているようだ。
>>> ex = BeautifulSoup('<a>This is <b>Example.</b></a>')
>>> for e in ex('a'):
... print e.contents
...
[u'This is ', <b>Example.</b>]
ここで、contentsの長さが1のとき、つまりタグが入れ子を含まないとき、タグが囲む文字列を"string"という識別子で取得できる。タグが複数の子要素を持つとき、stringはNoneとなっている。
>>> ex = BeautifulSoup('<a>This is <b>Example.</b></a><a>text</a>')
>>> for e in ex('a'):
... print e.string
...
None
text
これを使って、HTMLのタグを取り除く関数が書ける。
import re, urllib2
from BeautifulSoup import BeautifulSoup
def getPlainText(soup):
text = ''.join([ s.string if s.string else getPlainText(s) for s in soup ])
ctug = re.compile('<!--.*?-->',re.DOTALL)
text = ctug.sub('', x)
return text
url = 'http://www.crummy.com/software/BeautifulSoup/documentation.html'
html = urllib2.urlopen(url).read()
soup = BeautifulSoup(html)
print getPlainText(soup)
改行のみの行を取り除きたいときは、joinの前でfilter()を使うと簡単。ctugは「<!-- -->」のようなコメントを取り除くためのもの。re.DOTALLは正規表現の「. (ドット)」で改行も含めてマッチさせるのに必要。しかし、これだとscriptタグで囲まれた部分(javascriptとか)は取り除かれずに返ってきてしまう。document.write()をどう扱うべきか、、、。
''.join(filter(lambda(x): x != '\n' ,[ s.string if s.string else getPlainText(s) for s in soup ]))
複数リストのループ
昔のソースを見ていたら、こんなのがでてきた。どうやら一つのループで複数のリストを処理したかったようだ。
>>> lst = ['a', 'b', 'c', 'd'] >>> for t in zip(range(len(lst)), lst): ... print t[0], t[1] ... 0 a 1 b 2 c 3 d
複数戻り値を受けるときと同じように、これでよい。
>>> for i, l in zip(range(len(lst)), lst): ... print i, l ... 0 a 1 b 2 c 3 d
番号をつけるだけならenumerate()が便利。
>>> for i, l in enumerate(lst): ... print i, l ... 0 a 1 b 2 c 3 d
リストと三項演算
ふたつのリスト、aとbを組み合わせて、cみたいなリストを作りたいことがよくある。え、あんまりないですか?
>>> a = [1, 2, 3] >>> b = ['a', 'b', 'c', 'd', 'e'] >>> c = [1, 2, 3, "d", "e"]
どちらが長いかわからないとき、forループで回すとちょっと面倒なので、
>>> a + b[len(a):] if len(a) < len(b) else b + a[len(b):] [1, 2, 3, 'd', 'e'] >>> a,b = b,a >>> a + b[len(a):] if len(a) < len(b) else b + a[len(b):] [1, 2, 3, 'd', 'e']
要素を埋めて適当な長さのリストを作りたいときは内包表記が便利。
>>> a = [1, 2, 3] >>> num = 5 >>> [a[i] if len(a) > i else '' for i in range(num)] [1, 2, 3, '', '']
>>> a = [1,2] >>> b = [1] >>> b += [2] >>> a [1, 2] >>> b [1, 2] >>> a == b True >>> a is b False
==演算子は中身を、is演算子は参照を比べています。Javaだと==で参照の同一性、equalsで同値性だったはずなんで逆ですね。
>>> c = [1] >>> d = c >>> c is d True >>> c = c + [2] >>> c [1, 2] >>> d [1]
c = c + [2]とした場合、新しいオブジェクトが作られ、それにcが結合されます。cがもともと結合されていたオブジェクトは書き換えられません。
>>> e = [1] >>> f = e >>> e is f True >>> e += [2] >>> e [1, 2] >>> e [1, 2]
拡張代入の場合、cが結合されているオブジェクト自体が書き換えられます。
>>> for i in xrange(10000000): ... e += [i] ... >>> e is f True
Pythonのgenerator(2) グラフ探索(1)のつづき。
こんな感じでノードクラスというものを作ってみます。フィールドは自分のノード名と隣接するノードインスタンスのリストとしました。
class Node:
def __init__(self, name):
self.name = name
self.nodelist = []
def add(self, list):
self.nodelist += list
このクラスを使って先日のものと同じグラフを作ると
n1 = Node("a")
n2 = Node("b")
n3 = Node("c")
n4 = Node("d")
n5 = Node("e")
n6 = Node("f")
n1.add([n2, n6])
n2.add([n1, n3, n5])
n3.add([n2, n4, n5, n6])
n4.add([n3])
n5.add([n2, n3, n6])
n6.add([n1, n3, n5])
これに対する探索用ジェネレータはこんな感じ。再帰はなくしました。深さ優先はスタックを、幅優先はキューを使うと簡単。深さ優先のほうで隣接するノードのリストをひっくり返しているのは先日と同じ出力を得るためです。
def graph_depth2(node):
route = []
stack = []
stack.append(node)
while stack:
n = stack.pop()
if n not in route:
for l in n.nodelist[::-1]:
if l not in route:
stack.append(l)
yield n.name
route.append(n)
def graph_breadth2(node):
route = []
queue = []
queue.append(node)
while queue:
n = queue.pop(0)
for l in n.nodelist:
if l not in route and l not in queue:
queue.append(l)
yield n.name
route.append(n)
実際に探索させてみると
>>> for t in graph_depth2(n1):
print t,
a b c d e f
>>> for t in graph_depth2(n3):
print t,
c b a f e d
>>> for t in graph_breadth2(n1):
print t,
a b f c e d
>>> for t in graph_breadth2(n3):
print t,
c b d e f a
先日と同じ結果に。
もう一個のほうでも
n1 = Node(1) n2 = Node(2) n3 = Node(3) n4 = Node(4) n5 = Node(5) n6 = Node(6) n7 = Node(7) n8 = Node(8) n9 = Node(9) n10 = Node(10) n11 = Node(11) n1.add([n2, n5]) n2.add([n1, n3, n5]) n3.add([n2, n4, n9]) n4.add([n3, n5]) n5.add([n1, n2, n4, n6, n7]) n6.add([n5, n9]) n7.add([n5, n8]) n8.add([n7]) n9.add([n3, n6, n10]) n10.add([n9, n11]) n11.add([n10])
>>> for t in graph_depth2(n1):
print t,
1 2 3 4 5 6 9 10 11 7 8
>>> for t in graph_depth2(n9):
print t,
9 3 2 1 5 4 6 7 8 10 11
>>> for t in graph_breadth2(n1):
print t,
1 2 5 3 4 6 7 9 8 10 11
>>> for t in graph_breadth2(n9):
print t,
9 3 6 10 2 4 5 11 1 7 8
当然同じ結果に。
先日は距離を導入してダイクストラでもやってみようと思ったんですが、ほとんど変わらなそうなので止めました。リストに追加する際に始点からの距離を計算して、ポップする時に一番始点から近いノードを拾って来ればいいだけですし。
ジェネレータのメリットというのは簡潔さとメモリ使用量の削減にあるので、再帰を使ったり、複雑な制御構造を持たせたりするのは避けた方がよいんでしょうね。
をちょっと考えてみます。まずいかにもアルゴリズムの教科書に載ってそうなグラフから。グラフの表現はとりあえずディクショナリを使って、
graph = {"a":["b","f"],"b":["a","c","e"],"c":["b","d","e","f"],
"d":["c"],"e":["b","c","f"],"f":["a","c","e"]}
こんな感じで。ノードとそれに接続するノードのリストが要素。リストの左側のものが優先的に探索されます。ディクショナリまるごと渡したらジェネレータの利点がなくなるんじゃ、って感はありますが。
import copy
def graph_depth(node, graph):
g = copy.deepcopy(graph)
def graph_depth_inner(node):
if node in g:
yield node
nodes = g.pop(node)
for n in nodes:
if n in g:
for i in graph_depth_inner(n):
yield i
for n in graph_depth_inner(node):
yield n
def graph_breadth(node, graph):
g = copy.deepcopy(graph)
def graph_breadth_inner(queue):
q = []
for n in queue:
if n in g:
yield n
q += g.pop(n)
if q:
for n in graph_breadth_inner(q):
yield n
for n in graph_breadth_inner([node]):
yield n
graph_depthが深さ優先、graph_breadthが幅優先。木を探索する場合にはノード、左部分木、右部分木とはっきり分割できるのでジェネレータを再帰的に呼び出すだけでいいのですが、グラフの場合はどこを探索したのかを覚えておく必要があります。ディクショナリをコピーしてそれを破壊しながら探索するのが楽。探索済みのノードはディクショナリから削除することで判定するようにします。それぞれの関数の内部で定義された**_innerが実際の探索を行います。
ノードaから深さ優先探索する場合、aを出力、graph-{"a"}をノードbから深さ優先探索、bを出力、graph-{"a","b"}をノードcから深さ優先探索...と再帰的にジェネレータを適用できます(graph-{"a"}はgraphからノードaを取り除いたグラフとします)。
>>> for t in graph_depth("a",graph):
print t,
a b c d e f
>>> for t in graph_depth("c",graph):
print t,
c b a f e d
幅優先の場合、探索を開始したノードから等しい高さ(辺数)にあるノードをひとまとめにして再帰。もっとスマートにできそうですが。
>>> for t in graph_breadth("a",graph):
print t,
a b f c e d
>>> for t in graph_breadth("c",graph):
print t,
c b d e f a
もう少し大きいグラフを
graph2 = {1:[2,5],2:[1,3,5],3:[2,4,9],4:[3,5],
5:[1,2,4,6,7],6:[5,9],7:[5,8],8:[7],
9:[3,6,10],10:[9,11],11:[10]}
深さ優先
>>> for t in graph_depth(1,graph2):
print t,
1 2 3 4 5 6 9 10 11 7 8
>>> for t in graph_depth(9,graph2):
print t,
9 3 2 1 5 4 6 7 8 10 11
幅優先
>>> for t in graph_breadth(1,graph2):
print t,
1 2 5 3 4 6 7 9 8 10 11
>>> for t in graph_breadth(9,graph2):
print t,
9 3 6 10 2 4 5 11 1 7 8
少しだけいじると
def graph_depth(node, graph):
g = copy.deepcopy(graph)
def graph_depth_inner(node):
if node in g:
yield node
nodes = g.pop(node)
for n in nodes:
if n in g:
for i in graph_depth_inner(n):
yield i
yield node
for n in graph_depth_inner(node):
yield n
深さ優先で行って帰ってきたり、
>>> for t in graph_depth(1,graph2):
print t,
1 2 3 4 5 6 9 10 11 10 9 6 5 7 8 7 5 4 3 2 1
>>> for t in graph_depth(9,graph2):
print t,
9 3 2 1 5 4 5 6 5 7 8 7 5 1 2 3 9 10 11 10 9
def graph_breadth(node, graph):
g = copy.deepcopy(graph)
def graph_breadth_inner(queue):
q = []
for n in queue:
if n in g:
yield n
q += g.pop(n)
if q:
yield "|"
for n in graph_breadth_inner(q):
yield n
for n in graph_breadth_inner([node]):
yield n
幅優先で同じ高さ(辺数)にあるノードを区切ったりできます。
>>> for t in graph_breadth(1,graph2):
print t,
1 | 2 5 | 3 4 6 7 | 9 8 | 10 | 11 |
>>> for t in graph_breadth(9,graph2):
print t,
9 | 3 6 10 | 2 4 5 11 | 1 7 | 8 |
次はグラフの各ノードをクラスとして、ノード間の距離も考えてみます。あんまり変わらなそうですが。
ジェネレータというものを試してみようと思った。
通常の関数の場合、
def hello():
return 'hello,world!'
>>> hn = hello()
>>> hn
'hello,world!'
実行すると文字列が返ってきます。その結果、hnは文字列を指すことになります。
ジェネレータだと、
def hellogen():
yield 'h'
yield 'e'
yield 'l'
yield 'l'
yield 'o'
yield ','
yield 'w'
yield 'o'
yield 'r'
yield 'l'
yield 'd'
yield '!'
>>> hg = hellogen()
>>> hg
<generator object at 0x00D2CB20>
なんかオブジェクトが作られたようです。関数定義内にyieldが含まれる場合、それはジェネレータとして扱われます。ジェネレータは実行されるとgenerator objectを生成し、それがhgの参照となっているようです。このgenerator objectに対して、
>>> hg.next() 'h'
とnextメソッドを実行するとhが返ってきます。これは一行目のyieldの引数ですね。
>>> hg.next() 'e' >>> hg.next() 'l' >>> hg.next() 'l' >>> hg.next() 'o'
next()を続けると、そのたびに一文字ずつ、別の文字が返ってきます。これらはhellogen()の中でyieldの引数として与えたものです。generator objectは、next()が実行されるたびにyieldの引数をひとつずつ順番に返します。generrator objectは「次によばれたとき、どこから開始すればよいか」を記憶しているようです。
>>> hg1 = hellogen() >>> hg2 = hellogen() >>> hg1.next() 'h' >>> hg1.next() 'e' >>> hg2.next() 'h' >>> hg1.next() 'l'
hellogen()によってふたつのgenerator objectを作ってみます。それぞれの「次の開始位置」は別々に記憶されているのがわかります。hg1とhg2は別のインスタンスだということです。
>>> hg1 is hg2 False
上のhellogen()によって作られたgenerator objectは、「12個の文字を順番に返すという約束」を持っています。12個を超えて文字を取り出そうとするとエラーになります。
...
>>> hg.next()
'!'
>>> hg.next()
Traceback (most recent call last):
File "<pyshell#40>", line 1, in <module>
hg.next()
StopIteration
ジェネレータはfor文で回してやることができます。
>>> for t in hellogen(): print t, h e l l o , w o r l d !
これは、
>>> for t in hello(): print t, h e l l o , w o r l d !
と同じように見えます。つーか結果としては同じで、文字が用意されるタイミングが違います。hello()のほうは、forループに入った瞬間に'hello,world!'の文字列全体が用意され、そこから一文字ずつ取り出してprintしています。hellogen()のほうは、まずhellogen()によって'h'一文字だけが用意され、それを取り出して表示、また次の文字が用意され、それを取り出して表示、と一文字ずつ取得と表示を行っています。
極端な例だと
def gentest(n):
i = 0
while i < n:
yield i ** 2
i += 1
def test1():
for t in [x ** 2 for x in range(1000000)]:
if (t % 10000000000 == 0):
print t
return
def test2():
for t in gentest(1000000):
if (t % 10000000000 == 0):
print t
return
こんな感じで大量に調べなければならない値があってかつ候補のほとんどがフィルタされて消えるときには、range()で候補のリストをまとめて用意するのはメモリの無駄ってことでジェネレータが有効ですね。
上のgentest(n)の引数をとっぱらうと
def gentest():
i = 0
while 1:
yield i ** 2
i += 1
0, 1, 4, 9, 16, ...と無限に要素を返し続けるジェネレータが作れます。
定番のFibonacci級数
def fibs():
a = 0
b = 1
while 1:
yield a
a, b = b, a+b
>>> for t in xrange(15):
print f.next(),
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
Schemeでいうstreamのようなものなので、SICPを真似てちょっと不思議なこともできる。
def fibs2():
yield 0
yield 1
f = fibs2()
g = fibs2()
g.next()
while 1:
yield f.next()+g.next()
>>> f2 = fibs2()
>>> for t in xrange(15):
print f2.next(),
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
グラフ探索とかもできそう。
一昨日のエントリはひどいものだった。僕はこれをPythonでやりたかったんだ。
foldl(op, v, [a, b, c, d]) = (((v op a) op b) op c) op d
foldr(op, v, [a, b, c, d]) = a op (b op (c op (d op v)))
そしてこう書いた。
def foldl(proc, elem, lis):
lis.insert(0, elem)
return reduce(proc, lis)
def foldr(proc, elem, lis):
lis.append(elem)
lis.reverse()
return reduce(lambda x, y : apply(proc, [y, x]), lis)
fl = foldl(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])
fr = foldr(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])
>>> fl
0.03125
>>> fr
0.5
こんなアホみたいなことをする必要なんて全くなかったんだ……。もう少し考えるべきだった、Pythonがこんな不便なはずはないって。
import operator
def foldl(proc, elem, l):
lis = l[:]
lis.insert(0, elem)
return reduce(proc, lis)
def foldr(proc, elem, l):
lis = l[::-1]
lis.insert(0, elem)
return reduce(lambda x, y : proc(y, x), lis)
fl = foldl(operator.truediv, 2, [1, 2, 4, 8])
fr = foldr(operator.truediv, 2, [1, 2, 4, 8])
>>> fl
0.03125
>>> fr
0.5
これでよかったんじゃないか……。そして忘れていた、普通の言語にはループってものがあるってことを。
def foldl_loop(proc, elem, l):
lis = l[:]
for x in lis:
elem = proc(elem, x)
return elem
def foldr_loop1(proc, elem, l):
lis = l[::-1]
for x in lis:
elem = proc(x, elem)
return elem
def foldr_loop2(proc, elem, l):
lis = l[:]
while lis:
elem = proc(lis.pop(),elem)
return elem
時間を計ってみよう。largelist = range(10000000)として、リストの整数を全て足しあわせてみる。
foldl(operator.add, 0, largelist) 3.36605238934 foldl_loop(operator.add, 0, largelist) 5.12172161546 foldr(operator.add, 0, largelist) 7.88937811929 foldr_loop1(operator.add, 0, largelist) 5.67820882263 foldr_loop2(operator.add, 0, largelist) 8.93474310282
reduceはえー。そして気づいた、こんなことしたってHaskellの勉強にはならないって。
foldl,foldr
Hugs.Base> foldl (/) 2 [1, 2, 4, 8] 0.03125 Hugs.Base> foldr (/) 2 [1, 2, 4, 8] 0.5
foldl (/) 2 [1, 2, 4, 8] は、(((2 / 1) / 2) / 4) / 8
foldr (/) 2 [1, 2, 4, 8] は、1 / (2 / (4 / (8 / 2)))ということですね。
Hugs.Base> foldl (/) 3 [1, 3, 5, 7, 2, 1] 0.0142857142857143 Hugs.Base> foldr (/) 3 [1, 3, 5, 7, 2, 1] 1.42857142857143
Schemeで書いてみる。Schemeのライブラリ、SRFIのfoldは
> (fold / 2 '(1 2 4 8)) 8
これは8 / (4 / (2 / (1 / 2)))になってしまう。自分で書くしかない。
(define (foldl proc elem list)
(define (foldl-iter list ans)
(cond ((null? list) ans)
(#t (foldl-iter (cdr list) (proc ans (car list))))))
(foldl-iter list elem))
(define (foldr proc elem list)
(define (foldr-rec list)
(cond ((null? list) elem)
(#t (proc (car list) (foldr-rec (cdr list))))))
(foldr-rec list))
> (foldl / 2.0 '(1 2 4 8))
0.03125
> (foldr / 2.0 '(1 2 4 8))
0.5
> (foldl / 3.0 '(1 3 5 7 2 1 ))
0.014285714285714287
> (foldr / 3.0 '(1 3 5 7 2 1 ))
1.4285714285714284
いい感じに頭がこんがらがってきました。
次は Pythonで。
def foldl(proc, elem, lis):
lis.insert(0, elem)
return reduce(proc, lis)
def foldr(proc, elem, lis):
lis.append(elem)
lis.reverse()
return reduce(lambda x, y : apply(proc, [y, x]), lis)
fl = foldl(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])
fr = foldr(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])
>>> fl
0.03125
>>> fr
0.5
>>> print foldl(lambda x, y : x / y, 3.0, [1.0, 3.0, 5.0, 7.0, 2.0, 1.0])
0.0142857142857
>>> print foldr(lambda x, y : x / y, 3.0, [1.0, 3.0, 5.0, 7.0, 2.0, 1.0])
1.42857142857
Pythonて絶対こんな書き方をする言語ではないと思った。
文字列のスライシングについて、ちょっと考えて納得した。
s = ' 0123456789 'とすると、こんなデータ構造が作られる。データ構造の上下に振られた添え字はそれぞれスライシングの開始地点、終端地点である。
s[ 0 : 0 ]のとき、開始地点 = 終端地点であるので、スライシングは行われない。
s[ 0 : 3 ]のとき、上の添え字 0 から右下に矢印を伸ばし、データ『 0 』をとってくる。
一番目の添え字に 1 を足し、s[ 1 : 3 ]とする。
上の添え字 1 から右下に矢印を伸ばし、データ『 1 』をとってくる。
一番目の添え字に 1 を足し、s[ 2 : 3 ]とする。
上の添え字 0 から右下に矢印を伸ばし、データ『 2 』をとってくる。
一番目の添え字に 1 を足し、s[ 3 : 3 ]とする。
s[ 3 : 3 ]のとき、開始地点 = 終端地点であるので、スライシングは行われない。
s[ 4 : 7 : 2 ]のとき、上の添え字 4 から右下に矢印を伸ばし、データ『 4 』をとってくる。
一番目の添え字に 2 を足し、s[ 6 : 7 : 2 ]とする。
上の添え字 6 から右下に矢印を伸ばし、データ『 6 』をとってくる。
一番目の添え字に 2 を足し、s[ 8 : 7 : 2 ]とする。
s[ 8 : 7 : 2 ]のとき、開始地点 > 終端地点であるので、スライシングは行われない。
s[ 0 : 10 : 3 ] も同じように考えられる。
三つ目のインデックスが負のときは終了判定が逆になる。
s[ 1 : 0 : -1 ]のとき、上の添え字 1 から右下に矢印を伸ばし、データ『 1 』をとってくる。
一番目の添え字に -1 を足し、s[ 0 : 0 : -1 ]とする。
s[ 0 : 0 : -1 ]のとき、開始地点 = 終端地点であるので、スライシングは行われない。
s[ 9 : 3 : -2 ]のとき、上の添え字 9 から右下に矢印を伸ばし、データ『 9 』をとってくる。
一番目の添え字に -2 を足し、s[ 7 : 3 : -2 ]とする。
上の添え字 7 から右下に矢印を伸ばし、データ『 7 』をとってくる。
一番目の添え字に -2 を足し、s[ 5 : 3 : -2 ]とする。
上の添え字 5 から右下に矢印を伸ばし、データ『 5 』をとってくる。
一番目の添え字に -2 を足し、s[ 3 : 3 : -2 ]とする。
s[ 3 : 3 : -2 ]のとき、開始地点 = 終端地点であるので、スライシングは行われない。
つまり s[ a : b : c ] を求めるアルゴリズムとしては、
1. A = ' ' とする。
2. 配列の添え字 a , b が有効な範囲にあるか確かめ、範囲を超えていれば境界をその値として振りなおす。
3. c が正のとき、a <= b なら終了、c が負のとき、a => b ならば終了。A を出力する。
4. A += s[ a ]。
5. a += c として、A = A + s[ a : b : c ] を求める。
>>> s = "0123456789" >>> s[ : ] '0123456789' >>> s[ 0 : 0 ] '' >>> s[ 0 : 1 ] '0' >>> s[ -10 : -9 ] '0' >>> s[ -10 : 1 ] '0' >>> s[ -10 : 2 ] '01' >>> s[ 0 : len(s) ] '0123456789' >>> s[ 0 : len(s) - 1 ] '012345678' >>> s[ -len(s) : len(s) ] '0123456789' >>> s[ -len(s) : len(s) - 1 ] '012345678' >>> s[ len(s) : 0 : -1 ] '987654321' >>> s[ : : -1 ] '9876543210' >>> s[ len(s) - 1 : len(s) - 2 : -1 ] '9' >>> s[ len(s) - 1 : 0 : -1 ] '987654321'
三つ目のインデックスを負にしたときの挙動がよくわからない。『最初からn文字を逆順で取り出す』といった操作を行うには、『n文字取り出す→逆順にする』とスライシングが二回必要なんだろうか。
>>> s[ 3 : : -1 ] '3210'
これでいけた。逆順の時はインデックスがひとつずれるのかな。
>>> s[ 0 : : -1 ] '0'
モジュールとオブジェクト指向について。
後でまた読もう。
・ステートメントを式に書き直す
>>> (((True and [0]) or (True and [1])) or [2]) [0] 0 >>> (((False and [0]) or (True and [1])) or [2]) [0] 1 >>> (((False and [0]) or (False and [1])) or [2]) [0] 2
つまりこんな書き方もできると。
def teststate(x,y): return ((x and ((y and ['11']) or ['10'])) or ((y and ['01']) or ['00'])) [0]
>>> print teststate(True, True) 11 >>> print teststate(True, False) 10 >>> print teststate(False, True) 01 >>> print teststate(False, False) 00
def exor(x, y): return (((x==y) and [False]) or [True]) [0]
>>> print exor(True, True) False >>> print exor(True, False) True >>> print exor(False, True) True >>> print exor(False, False) False
まあ
def exor(x, y): return x!=y
これでいいんだけどね……。
・ディクショナリの更新
for i in D.keys():
× CD={i : D[i]}
〇 CD[i]=D[i]
ディクショナリに存在しないインデックスを指定すると値が代入される、と。
・リスト内包表記
>>> [x * x for x in range(10)] [0, 1, 4, 9, 25, 36, 49, 64, 81]
defのネストと関数オブジェクトへの代入ってありなんだ。
x = 1 if x == 1: def func(): print 1 else: def func(): print 2 other = func other()
(第二版)を読みながら勉強している。さすがオライリー、という感じで入門書にもかかわらず700Pもある。いまそのうちの200Pちょっとを読んだところで、3部も終わりにさしかかりちょっと楽しくなってきた。冬期休暇中に読み終えられるかな。
今日覚えたこと
>>> range(7) [0, 1, 2, 3, 4, 5, 6] >>> 3 in [2, 3, 4] True >>> zip(range(3),range(7)) [(0, 0), (1, 1), (2, 2)]
