第12回アルゴリズム勉強会に行ってきました

人生初勉強会。
やったのは counting sort と radix sort。
この二つは書いたことがなかったので、Python で超手抜きに書いてみた。

https://gist.github.com/1395308

base = 10

def radix_sort(x, max):
    radix = 1
    while radix < max:
        x = counting_sort(x, radix)
        radix *= base
    return x

def counting_sort(a, radix):
    c = [0] * base
    for k in a:
        r = (k / radix) % base
        c[r] += 1

    for i in range(1, base):
        c[i] += c[i - 1]

    b = [0] * len(a)
    for k in reversed(a):
        r = (k / radix) % base
        b[c[r] - 1] = k
        c[r] -= 1

    return b

print radix_sort([925, 663, 212, 58, 775, 802], 1000)

（この counting_sort は radix_sort から呼ぶためのもので汎用的ではない）

C++ のちゃんとしたものは http://d.hatena.ne.jp/nokuno/20111126/1322297750で id:nokuno さんが書かれている。

ここから下は個人的なこと。

元々、自分に勉強会は合わないと思っていた。

大人数のコミュニケーションは苦手で、これまで実りがあった勉強会は 1人勉強会と 2人勉強会だけだったから。

それで今は毎週、大学院のころの友達と二人勉強会をしているのだが、今週はもう一人が用事があって暇になった。

そこでこの勉強会のことを思い出し、参加してみる気になった。そういえば大学院のころ、アルゴリズムの授業＆輪講だけは面白かったなぁと思い出したので。

参加してみて。

経験としては面白かった。でも、自分にとって、同じテーマで集中できるのはせめて 1時間半。4時間はちょっと長かった。しかし、仮に 1時間半であったとすると、そのために会場まで行って帰るのはきついだろうな。また、既婚者ということもあり懇親会に参加できなかったのも残念だった。

大学院時代の面白かった輪講について書いてみる。

岩間・伊藤研 の「計算量理論」というタイトルの輪講。自分が参加したのは 2009年度の。材料は Erik Demaine 先生の Advanced Data Structures。

この輪講は、準備がかなりしんどかったけど、それに見合った充実度はあったと思う。自分は第三回（Tango tree、あまり実用には使われない）を担当した。あの輪講に最後まで出た人は、みんな良かったと思っているんじゃないかな。

（内容も面白かったけど、何といっても岩間先生のキャラが強烈だったw）