重みをつけてランダムに選択する方法

d = {0: 48, 1: 13, 2: 6, 3: 61, 4: 14, 5: 8, 6: 4, 7: 41, 8: 84, 9: 50}
というようなdictオブジェクトから、d[k] の大きさに応じてランダムに選択する処理を考えていました。

たとえば
d[0] = 48
d[5] = 8
なので、"0" は "5" の6倍(= 48/8 )の確率で選択されるようにしたいです。

普通、真っ先に思いつくのは、こんな処理でしょう。

def choice(d):
    s = 0
    for k, v in d.items():
        s += v
    rnd = random.randrange(s)
    for k, v in d.items():
        s += v
        if rand < s:
            return k

dを一旦全部読み込んで d[k] の和をとってから、乱数を発生させて
また d を最初から読んでいって、丁度いいところでリターンする。
でも、d を二回読み込むのは効率が悪い気がします。

どうにかならないかなと思って、こういう処理を思いつきました。

def choice(d):
    s = 0
    for k, v in d.items():
        s += v
        if random.randrange(s) < v:
            n = k
    return n

これなら一周でOKです。
これで、ちゃんと望んだ処理になっているは、確認が必要です。
最後の要素が選択される確率は、d[n] / (d[0] + d[1] + ... + d[n]) なので最後の要素に関してはOK。
最後から二番目が選択される確率は、(d[n-1] / (d[0] + d[1] + ... + d[n-1]) ) * (1 - d[n]/ (d[0] + ... + d[n])) = d[n-1] / (d[0] + d[1] + ... + d[n])
以下同様に、後ろから計算していけば全部望んだ確率で選択されることがわかります。