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]

少しマシになった。

いい感じに遅延してくれないからなぁ。