screencast2
http://www.screencast-o-matic.com/watch/ciXO1dsc
odzさんとこのQuicksortを高速化する過程を配信しようと思ったんだけど、途中でFirefox固まったりPython固まったりでちゃんと撮れているのかよくわからない。
http://d.hatena.ne.jp/odz/20071125
コアが1つしかないノートパソコンではやっぱりしんどいな、という結論になった。
>>> from timeit import Timer >>> t = Timer(setup=""" from itertools import islice def tail(xs): return islice(xs, 1, len(xs)) def quicksort(xs): if len(xs) == 0: return [] x = xs[0] return quicksort([y for y in tail(xs) if y < x]) \ + [x] \ + quicksort([y for y in tail(xs) if y >= x]) from random import random data = [random() for i in range(4096)]""", stmt="quicksort(data)") >>> t.repeat(3, 10) [1.3894659796146698, 1.3651681987516895, 1.4261438255421126] >>> t = Timer(setup=""" from itertools import tee, chain from random import random def quicksort(xs): if isinstance(xs, list): xs = (x for x in xs) try: x = xs.next() except StopIteration: return (x for x in []) def yield_x(): yield x xs1, xs2 = tee(xs) return chain( quicksort(y for y in xs1 if y < x), yield_x(), quicksort(y for y in xs2 if y >= x)) data = [random() for x in range(4096)] """, stmt=""" list(quicksort(data)) """) >>> t.repeat(3, 10) [2.9476609457346967, 3.0186817039598282, 3.3074144898305349]
まぁ、こんな感じでリスト内包をジェネレータ内包に書き換えてやると帰って遅くなってしまった。
これ前座のつもりでここから「新しいインスタンスを作らないでリストを破壊的に書き換えるクイックソート」に走ろうとしたんだけどなー。気が向いたら明日撮影する。
>>> t = Timer(setup=""" from itertools import tee from random import random def quicksort(xs): if isinstance(xs, list): xs = (x for x in xs) x = xs.next() xs1, xs2 = tee(xs) for y in quicksort(y for y in xs1 if y < x): yield y yield x for y in quicksort(y for y in xs2 if y >= x): yield y data = [random() for x in range(4096)] """, stmt=""" list(quicksort(data)) """) >>> t.repeat(3, 10) [2.5895629193095715, 2.8631820524675788, 2.9743467395995822]
少しマシになった。
いい感じに遅延してくれないからなぁ。