valueでsortされたdictが欲しい

という話。

カウントしつつリアルタイムで現在のヒストグラムを確認したいなーと思った。

こういうときは普通パフォーマンスが問題になるから自分でデータ構造を書くんだろうけど。。。
とりあえずbuilt-in、pure pythonで実現するもっともしょぼい方法でやってみた。

class RankDict(object):
    def __init__(self):
        self.__idict  = dict()
        self.__clist = []

    def count(self, s):
        idict, clist = self.__idict, self.__clist
        if s not in idict:
            idict[s] = len(clist)
            clist.append([s, 0])
        ci = idict[s]
        clist[ci][1] += 1
        si = ci
        while si > 0:
            if clist[si - 1][1] < clist[si][1]:
                clist[si - 1], clist[si] = clist[si], clist[si - 1]
                idict[clist[si - 1][0]] = si - 1
                idict[clist[si][0]] = si
                si -= 1
            else:
                break

    def __iter__(self):
        return iter(self.__clist)

結果はこんな感じ。ランダムに一文字アルファベットを割り当てる。

>>> r = RankDict()
>>> for _ in range(100000):
...     r.count(chr(random.randint(97,122)))
... 
>>> for key, count in itertools.islice(r, 10):
...     print '%s : %d' % (key, count)
... 
m : 3997
s : 3936
y : 3888
x : 3882
b : 3880
o : 3870
t : 3868
j : 3865
w : 3864
c : 3864