import random

def w_choice(lst):
	n = random.uniform(0, 1)
	for item, weight in lst:
		if n < weight:
			break
		n = n - weight
	return item

import random

def w_choice(ls):
    m, n = 0, random.uniform(0, sum(x[1] for x in ls))
    for item, weight in ls:
        if n > m and n <= m+weight:
            return item
        m += weight

import random

ITEM_INDEX, WEIGHT_INDEX = 0, 1

def w_choice(lst):
    n = random.uniform(0, 1)
    test_list = [a for a in lst if a[WEIGHT_INDEX] > n]
    if test_list:
        return random.choice(test_list)[ITEM_INDEX]

import random

def choose_one(lst):
    new_list = list(lst)
    # Немного побалуемся с весом элементов.
    for i in range(1, len(lst)):
        new_list[i] = (0, new_list[i][1]+new_list[i-1][1])
    n = random.uniform(0, new_list[-1][1])
    for i, item in enumerate(new_list):
        if n > item[1]: continue
        return lst[i]

def choose_one(lst):
    new_list = list(lst)
    n = random.uniform(0, 1)
    return [x for x in lst if x[1] >= n]

def build_cdf(distrib):
    cdf = []
    val = 0
    for key, freq in distrib.items():
        val += freq
        cdf.append((val, key))
    return (val, cdf)

import random
def sample_from_cdf(val_and_cdf):
    (val, cdf) = val_and_cdf;
    rand = random.uniform(0, val)
    # use bisect.bisect_left to reduce search time from O(n) to O(log n).
    return [key for index, key in cdf if index > rand][0]

x = build_cdf({"a":0.2, "b":0.3, "c":0.5});
y = [sample_from_cdf(x) for i in range(0,100000)];
print (len([t for t in y if t == "a"]))   # 19864
print (len([t for t in y if t == "b"]))   # 29760
print (len([t for t in y if t == "c"]))   # 50376

from random import choice
d ={"key1":2,"key2":1}
c=[]
for k,v in d.items():
   c+=[k]*v

choice(c)
'key1'

>>> sum(1 for x in range(100) if choice(c)=="key1")
63
>>> sum(1 for x in range(100) if choice(c)=="key2")
36