Создание дистрибутива на основе списка [duplicate]

Третье решение, о котором я почти никогда не упоминал, имеет специфику MySQL и выглядит так:

SELECT id, MAX(rev) AS rev
 , 0+SUBSTRING_INDEX(GROUP_CONCAT(numeric_content ORDER BY rev DESC), ',', 1) AS numeric_content
FROM t1
GROUP BY id

Да, это выглядит ужасно (преобразование в строку и обратно и т. д.), но по моему опыту это обычно быстрее, чем другие решения. Возможно, это только для моих случаев использования, но я использовал его на таблицах с миллионами записей и множеством уникальных идентификаторов. Возможно, это связано с тем, что MySQL очень плохо оптимизирует другие решения (по крайней мере, в 5,0 дней, когда я придумал это решение).

Важно то, что GROUP_CONCAT имеет максимальную длину для строки, которую она может построить. Вероятно, вы захотите поднять этот предел, установив переменную group_concat_max_len. И имейте в виду, что это будет предел для масштабирования, если у вас есть большое количество строк.

В любом случае вышеупомянутое не работает напрямую, если ваше поле содержимого уже является текстом. В этом случае вы, вероятно, захотите использовать другой разделитель, например, \ 0. Вы также быстрее столкнетесь с пределом group_concat_max_len.

76
задан pafcu 24 November 2010 в 11:56
поделиться

12 ответов

scipy.stats.rv_discrete может быть тем, что вы хотите. Вы можете предоставить свои вероятности с помощью параметра values. Затем вы можете использовать метод rvs() объекта распределения для генерации случайных чисел.

Как отмечено в комментариях Юджином Пахомовым, вы также можете передать параметр ключевого слова p в numpy.random.choice() , например

numpy.random.choice(numpy.arange(1, 7), p=[0.1, 0.05, 0.05, 0.2, 0.4, 0.2])

Если вы используете Python 3.6 или выше, вы можете использовать random.choices() из стандартной библиотеки - см. ответ Mark Dickinson ].

72
ответ дан Mark Ransom 27 August 2018 в 01:03
поделиться

Создайте список элементов на основе их weights:

items = [1, 2, 3, 4, 5, 6]
probabilities= [0.1, 0.05, 0.05, 0.2, 0.4, 0.2]
# if the list of probs is normalized (sum(probs) == 1), omit this part
prob = sum(probabilities) # find sum of probs, to normalize them
c = (1.0)/prob # a multiplier to make a list of normalized probs
probabilities = map(lambda x: c*x, probabilities)
print probabilities

ml = max(probabilities, key=lambda x: len(str(x)) - str(x).find('.'))
ml = len(str(ml)) - str(ml).find('.') -1
amounts = [ int(x*(10**ml)) for x in probabilities]
itemsList = list()
for i in range(0, len(items)): # iterate through original items
  itemsList += items[i:i+1]*amounts[i]

# choose from itemsList randomly
print itemsList

Оптимизация может состоять в нормализации сумм с помощью наибольшего общего делителя, чтобы сделать список целей меньшим.

Кроме того, это может быть интересным.

1
ответ дан Community 27 August 2018 в 01:03
поделиться

Ни один из этих ответов не является особенно ясным или простым.

Вот простой и понятный метод, который гарантированно работает.

accumulate_normalize_probabilities принимает словарь p, который отображает символы к вероятностям ИЛИ частот. Он выводит полезный список кортежей, из которых можно сделать выбор.

def accumulate_normalize_values(p):
        pi = p.items() if isinstance(p,dict) else p
        accum_pi = []
        accum = 0
        for i in pi:
                accum_pi.append((i[0],i[1]+accum))
                accum += i[1]
        if accum == 0:
                raise Exception( "You are about to explode the universe. Continue ? Y/N " )
        normed_a = []
        for a in accum_pi:
                normed_a.append((a[0],a[1]*1.0/accum))
        return normed_a

Выход:

>>> accumulate_normalize_values( { 'a': 100, 'b' : 300, 'c' : 400, 'd' : 200  } )
[('a', 0.1), ('c', 0.5), ('b', 0.8), ('d', 1.0)]

Почему он работает

Шаг накопления поворачивает каждый символ в промежуток между собой и предыдущими символами вероятность или частота (или 0 в случае первого символа). Эти интервалы могут использоваться для выбора из (и, следовательно, выборки предоставленного распределения) простым переходом по списку до тех пор, пока случайное число в интервале 0,0 -> 1,0 (подготовленное ранее) не будет меньше или равно конечной точке интервала текущего символа.

Нормализация освобождает нас от необходимости убедиться, что все суммируется до некоторой величины. После нормализации «вектор» вероятностей суммируется до 1,0.

Остаток кода для кода для выбора и создания произвольно длинной выборки из распределения ниже:

def select(symbol_intervals,random):
        print symbol_intervals,random
        i = 0
        while random > symbol_intervals[i][1]:
                i += 1
                if i >= len(symbol_intervals):
                        raise Exception( "What did you DO to that poor list?" )
        return symbol_intervals[i][0]


def gen_random(alphabet,length,probabilities=None):
        from random import random
        from itertools import repeat
        if probabilities is None:
                probabilities = dict(zip(alphabet,repeat(1.0)))
        elif len(probabilities) > 0 and isinstance(probabilities[0],(int,long,float)):
                probabilities = dict(zip(alphabet,probabilities)) #ordered
        usable_probabilities = accumulate_normalize_values(probabilities)
        gen = []
        while len(gen) < length:
                gen.append(select(usable_probabilities,random()))
        return gen

Использование:

>>> gen_random (['a','b','c','d'],10,[100,300,400,200])
['d', 'b', 'b', 'a', 'c', 'c', 'b', 'c', 'c', 'c']   #<--- some of the time
0
ответ дан Cris Stringfellow 27 August 2018 в 01:03
поделиться

Возможно, это немного поздно. Но вы можете использовать numpy.random.choice() , передавая параметр p:

val = numpy.random.choice(numpy.arange(1, 7), p=[0.1, 0.05, 0.05, 0.2, 0.4, 0.2])
13
ответ дан Engineero 27 August 2018 в 01:03
поделиться

Другой ответ, возможно, быстрее:)

distribution = [(1, 0.2), (2, 0.3), (3, 0.5)]  
# init distribution  
dlist = []  
sumchance = 0  
for value, chance in distribution:  
    sumchance += chance  
    dlist.append((value, sumchance))  
assert sumchance == 1.0 # not good assert because of float equality  

# get random value  
r = random.random()  
# for small distributions use lineair search  
if len(distribution) < 64: # don't know exact speed limit  
    for value, sumchance in dlist:  
        if r < sumchance:  
            return value  
else:  
    # else (not implemented) binary search algorithm  
1
ответ дан Lucas Moeskops 27 August 2018 в 01:03
поделиться

, вы можете захотеть взглянуть на NumPy Случайные выборки распределения

1
ответ дан Manuel Salvadores 27 August 2018 в 01:03
поделиться

(Хорошо, я знаю, что вы просите термоусадочную пленку, но, возможно, эти домашние решения просто не были достаточно краткими для вашей симпатии.: -)

pdf = [(1, 0.1), (2, 0.05), (3, 0.05), (4, 0.2), (5, 0.4), (6, 0.2)]
cdf = [(i, sum(p for j,p in pdf if j < i)) for i,_ in pdf]
R = max(i for r in [random.random()] for i,c in cdf if c <= r)

Я псевдоподтвержден что это работает, наблюдая вывод этого выражения:

sorted(max(i for r in [random.random()] for i,c in cdf if c <= r)
       for _ in range(1000))
11
ответ дан Marcelo Cantos 27 August 2018 в 01:03
поделиться

Начиная с Python 3.6, в стандартной библиотеке Python есть решение random.choices .

Пример использования: давайте настроим популяцию и весы, соответствующие тем, которые находятся в Вопрос OP:

>>> from random import choices
>>> population = [1, 2, 3, 4, 5, 6]
>>> weights = [0.1, 0.05, 0.05, 0.2, 0.4, 0.2]

Теперь choices(population, weights) генерирует один образец:

>>> choices(population, weights)
4

Необязательный аргумент ключевого слова k позволяет запрашивать более одного образца в один раз. Это ценно, потому что есть некоторая подготовительная работа, которую random.choices должен делать каждый раз, когда она вызывается, до создания каких-либо образцов; создавая сразу несколько образцов, нам нужно только сделать эту подготовительную работу один раз. Здесь мы создаем миллион выборок и используем collections.Counter, чтобы проверить, что распределение, которое мы получаем, грубо совпадает с весами, которые мы дали.

>>> million_samples = choices(population, weights, k=10**6)
>>> from collections import Counter
>>> Counter(million_samples)
Counter({5: 399616, 6: 200387, 4: 200117, 1: 99636, 3: 50219, 2: 50025})
26
ответ дан Mark Dickinson 27 August 2018 в 01:03
поделиться

, основанный на других решениях, вы генерируете накопительное распределение (как целое или плавающее, как вам нравится), тогда вы можете использовать bisect, чтобы сделать его быстрым

, это простой пример (здесь я использовал целые числа)

l=[(20, 'foo'), (60, 'banana'), (10, 'monkey'), (10, 'monkey2')]
def get_cdf(l):
    ret=[]
    c=0
    for i in l: c+=i[0]; ret.append((c, i[1]))
    return ret

def get_random_item(cdf):
    return cdf[bisect.bisect_left(cdf, (random.randint(0, cdf[-1][0]),))][1]

cdf=get_cdf(l)
for i in range(100): print get_random_item(cdf),

функция get_cdf преобразует ее из 20, 60, 10, 10 в 20, 20 + 60, 20 + 60 + 10, 20 + 60 + 10 + 10

теперь мы выбираем случайное число до 20 + 60 + 10 + 10 с использованием random.randint, затем мы используем bisect для быстрого получения фактического значения

1
ответ дан muayyad alsadi 27 August 2018 в 01:03
поделиться
from __future__ import division
import random
from collections import Counter


def num_gen(num_probs):
    # calculate minimum probability to normalize
    min_prob = min(prob for num, prob in num_probs)
    lst = []
    for num, prob in num_probs:
        # keep appending num to lst, proportional to its probability in the distribution
        for _ in range(int(prob/min_prob)):
            lst.append(num)
    # all elems in lst occur proportional to their distribution probablities
    while True:
        # pick a random index from lst
        ind = random.randint(0, len(lst)-1)
        yield lst[ind]

Проверка:

gen = num_gen([(1, 0.1),
               (2, 0.05),
               (3, 0.05),
               (4, 0.2),
               (5, 0.4),
               (6, 0.2)])
lst = []
times = 10000
for _ in range(times):
    lst.append(next(gen))
# Verify the created distribution:
for item, count in Counter(lst).iteritems():
    print '%d has %f probability' % (item, count/times)

1 has 0.099737 probability
2 has 0.050022 probability
3 has 0.049996 probability 
4 has 0.200154 probability
5 has 0.399791 probability
6 has 0.200300 probability
1
ответ дан Saksham Varma 27 August 2018 в 01:03
поделиться

Преимущество создания списка с использованием CDF заключается в том, что вы можете использовать двоичный поиск. Хотя вам нужно O (n) время и пространство для предварительной обработки, вы можете получить k чисел в O (k log n). Поскольку обычные списки Python неэффективны, вы можете использовать модуль array.

Если вы настаиваете на постоянном пространстве, вы можете сделать следующее: O (n), O (1).

def random_distr(l):
    r = random.uniform(0, 1)
    s = 0
    for item, prob in l:
        s += prob
        if s >= r:
            return item
    return item  # Might occur because of floating point inaccuracies
23
ответ дан sdcvvc 27 August 2018 в 01:03
поделиться

Вот более эффективный способ сделать это:

Просто вызовите следующую функцию с массивом 'weightights' (при условии, что индексы соответствуют соответствующим элементам) и no. необходимых образцов. Эта функция может быть легко модифицирована для обработки упорядоченной пары.

Возвращает индексы (или элементы), отобранные / выбранные (с заменой) с использованием их соответствующих вероятностей:

def resample(weights, n):
    beta = 0

    # Caveat: Assign max weight to max*2 for best results
    max_w = max(weights)*2

    # Pick an item uniformly at random, to start with
    current_item = random.randint(0,n-1)
    result = []

    for i in range(n):
        beta += random.uniform(0,max_w)

        while weights[current_item] < beta:
            beta -= weights[current_item]
            current_item = (current_item + 1) % n   # cyclic
        else:
            result.append(current_item)
    return result

Краткая заметка о концепции, используемой в цикле while. Мы уменьшаем вес текущего элемента от кумулятивной бета-версии, которая является совокупным значением, построенным равномерно случайным образом, и увеличиваем текущий индекс, чтобы найти элемент, вес которого соответствует значению бета-версии.

-1
ответ дан Vaibhav 27 August 2018 в 01:03
поделиться
Другие вопросы по тегам:

Похожие вопросы: