Распределение вероятностей в Python

Вот лучший ответ для специального распределения вероятностей, одно , ответ Rex Logan , кажется, приспособлен в. Распределение похоже на это: каждый объект имеет целочисленный вес между 0 и 100, и его вероятность находится в пропорции к его весу. Так как это - в настоящее время принимаемый ответ, я предполагаю, что об этом стоит думать.

Так сохраняют массив 101 мусорного ведра. Каждое мусорное ведро содержит список всех объектов с его конкретным весом. Каждое мусорное ведро также знает общее количество вес всех его объектов.

Для выборки: выберите мусорное ведро наугад в пропорции к его общему весу. (Используйте один из стандартных рецептов для этого - линейный или двоичный поиск.) Тогда выбирают объект от мусорного ведра однородно наугад.

Для передачи объекта: удалите его из его мусорного ведра, поместите его в его мусорное ведро в цели и обновите веса обоих мусорных ведер. (При использовании двоичного поиска выборки необходимо также обновить рабочие суммы, который использует. Это все еще довольно быстро, так как нет многих мусорных ведер.)

Вот классический способ сделать это в псевдокоде, где random.random () дает Вам случайное плавание от 0 до 1.

let z = sum of all the convictions
let choice = random.random() * z 
iterate through your objects:
    choice = choice - the current object's conviction
    if choice <= 0, return this object
return the last object

Для примера: предположите, что у Вас есть два объекта, один с весом 2, другой с весом 4. Вы генерируете число от 0 до 6. Если choice будет между 0 и 2, который произойдет с 2/6 = 1/3 вероятность, то это будет вычтено 2, и первый объект выбран. Если выбор будет между 2 и 6, который произойдет с 4/6 = 2/3 вероятность, то первое вычитание будет все еще иметь выбор быть> 0, и второе вычитание заставит 2-й объект выбираться.

Я использовал бы этот рецепт . Необходимо будет добавить вес к объектам, но это - просто простое отношение и поместило их в список кортежей (объект, убеждение / (сумма убеждений)). Это должно быть легко сделать использование понимания списка.

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

Вы могли, вероятно, использовать хеш/словарь, чтобы сделать это.

то, Что Вы захотите сделать, должно иметь случайное число, x , умноженный и суммированный по всему набору вещей, которые Вы хотите выбранный и делите тот результат по количеству объектов в Вашем наборе.

Псевдокод:

objectSet = [(object1, weight1), ..., (objectN, weightN)]
sum = 0
rand = random()
for obj, weight in objectSet
    sum = sum+weight*rand
choice = objectSet[floor(sum/objectSet.size())]

РЕДАКТИРОВАНИЕ : Я просто думал, насколько медленный мой код будет с очень большими наборами (это - O (n)). Следующий псевдокод является O (журнал (n)) и в основном использует двоичный поиск.

objectSet = [(object1, weight1), ..., (objectN, weightN)]
sort objectSet from less to greater according to weights
choice = random() * N # where N is the number of objects in objectSet
do a binary search until you have just one answer

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

Самая простая вещь сделать состоит в том, чтобы использовать random.choice (который использует равномерное распределение), и варьируйтесь частота возникновения на объекте в исходном наборе.

>>> random.choice([1, 2, 3, 4])
4

... по сравнению с:

>>> random.choice([1, 1, 1, 1, 2, 2, 2, 3, 3, 4])
2

, Таким образом, Ваши объекты могли иметь основной уровень возникновения (n) и между 1, и объекты n добавляются к исходному набору как функция уровня убеждения. Этот метод действительно прост; однако, это может иметь значительные издержки, если количество отдельных объектов является большим, или уровень убеждения должен быть очень мелкомодульным.

, С другой стороны, если Вы генерируете больше, что одно случайное число с помощью равномерного распределения и суммирует их, числа, происходящие около среднего, более вероятны, что те, которые происходят около экстремальных значений (думают о прокрутке двух игр в кости и вероятности получения 7 по сравнению с 12 или 2). Можно затем заказать объекты уровнем убеждения и генерировать число с помощью нескольких бросков кости, которые Вы используете, чтобы вычислить и индексировать в объекты. Используйте числа около среднего для индексации низких объектов убеждения и чисел около экстремальных значений для индексации высоких объектов убеждения. Можно варьироваться точная вероятность, что данный объект будет выбран путем изменения "количества сторон" и количества "игры в кости" (может быть более просто поместить объекты в блоки и игру в кости использования с небольшим количеством сторон вместо того, чтобы пытаться связать каждый объект с определенным результатом):

>>> die = lambda sides : random.randint(1, sides)
>>> die(6)
3
>>> die(6) + die(6) + die(6)
10

Я предлагаю Вас порт эта реализация PHP взвешенных, случайных к Python. В частности, основанный на двоичном поиске второй алгоритм помогает обратиться к Вашим проблемам скорости.

В комментариях к исходному сообщению Nicholas Leonard предлагает, чтобы и обмен и выборка были быстры. Вот идея для того случая; я не попробовал его.

, только выбирая должно было быть быстрым, мы могли использовать массив значений вместе с рабочей суммой их вероятностей и сделать двоичный поиск на рабочей сумме (при этом ключ был универсальным случайным числом) - O (журнал (n)) операция. Но обмен потребовал бы обновления всех значений рабочей суммы, появляющихся после того, как записи обменивались - O (n) операция. (Вы могли принять решение обмениваться только объектами около конца их списков? Я приму нет.)

Так позволяют нам стремиться к O (журнал (n)) в обеих операциях. Вместо массива сохраните двоичное дерево для каждого набора к образцу от. Лист содержит демонстрационное значение и его (ненормализованную) вероятность. Узел ответвления содержит общую вероятность своих детей.

Для выборки генерируйте универсальное случайное число x между 0 и общая вероятность корня и убывание дерево. При каждом ответвлении выберите покинутого ребенка, если у покинутого ребенка есть общая вероятность <= x. Еще вычтите вероятность покинутого ребенка от x и пойдите право. Возвратите листовое значение, которого Вы достигаете.

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

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

Обновление: По запросу, вот базовое внедрение. Не настроили его вообще. Использование:

>>> t1 = build_tree([('one', 20), ('two', 2), ('three', 50)])
>>> t1
Branch(Leaf(20, 'one'), Branch(Leaf(2, 'two'), Leaf(50, 'three')))
>>> t1.sample()
Leaf(50, 'three')
>>> t1.sample()
Leaf(20, 'one')
>>> t2 = build_tree([('four', 10), ('five', 30)])
>>> t1a, t2a = transfer(t1, t2)
>>> t1a
Branch(Leaf(20, 'one'), Leaf(2, 'two'))
>>> t2a
Branch(Leaf(10, 'four'), Branch(Leaf(30, 'five'), Leaf(50, 'three')))

Код:

import random

def build_tree(pairs):
    tree = Empty()
    for value, weight in pairs:
        tree = tree.add(Leaf(weight, value))
    return tree

def transfer(from_tree, to_tree):
    """Given a nonempty tree and a target, move a leaf from the former to
    the latter. Return the two updated trees."""
    leaf, from_tree1 = from_tree.extract()
    return from_tree1, to_tree.add(leaf)

class Tree:
    def add(self, leaf):
        "Return a new tree holding my leaves plus the given leaf."
        abstract
    def sample(self):
        "Pick one of my leaves at random in proportion to its weight."
        return self.sampling(random.uniform(0, self.weight))
    def extract(self):
        """Pick one of my leaves and return it along with a new tree
        holding my leaves minus that one leaf."""
        return self.extracting(random.uniform(0, self.weight))        

class Empty(Tree):
    weight = 0
    def __repr__(self):
        return 'Empty()'
    def add(self, leaf):
        return leaf
    def sampling(self, weight):
        raise Exception("You can't sample an empty tree")
    def extracting(self, weight):
        raise Exception("You can't extract from an empty tree")

class Leaf(Tree):
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
    def __repr__(self):
        return 'Leaf(%r, %r)' % (self.weight, self.value)
    def add(self, leaf):
        return Branch(self, leaf)
    def sampling(self, weight):
        return self
    def extracting(self, weight):
        return self, Empty()

def combine(left, right):
    if isinstance(left, Empty): return right
    if isinstance(right, Empty): return left
    return Branch(left, right)

class Branch(Tree):
    def __init__(self, left, right):
        self.weight = left.weight + right.weight
        self.left = left
        self.right = right
    def __repr__(self):
        return 'Branch(%r, %r)' % (self.left, self.right)
    def add(self, leaf):
        # Adding to a random branch as a clumsy way to keep an
        # approximately balanced tree.
        if random.random() < 0.5:
            return combine(self.left.add(leaf), self.right)
        return combine(self.left, self.right.add(leaf))
    def sampling(self, weight):
        if weight < self.left.weight:
            return self.left.sampling(weight)
        return self.right.sampling(weight - self.left.weight)
    def extracting(self, weight):
        if weight < self.left.weight:
            leaf, left1 = self.left.extracting(weight)
            return leaf, combine(left1, self.right)
        leaf, right1 = self.right.extracting(weight - self.left.weight)
        return leaf, combine(self.left, right1)

Обновление 2: В ответ на другую проблему , Jason Orendorff указывает, что двоичные деревья могут быть сохранены отлично сбалансированными путем представления их в массиве точно так же, как классическая структура "кучи". (Это оставляет свободное место, потраченное на указатели, также.) Видят мои комментарии к тому ответу для того, как адаптировать его код к этой проблеме.

Вы хотите дать каждому объекту вес. Чем больше вес, тем более вероятно это произойдет. Более точно probx =weight/sum_all_weights.

Затем генерируют случайное число в диапазоне 0 к sum_all_weights и отображают его на каждый объект.

Этот код позволяет Вам генерировать случайный индекс, и он отображается, когда объект создается для скорости. Если все Ваши наборы объектов имеют то же распределение затем, можно обойтись только одним объектом RandomIndex.

import random

class RandomIndex:
    def __init__(self, wlist):
        self._wi=[]
        self._rsize=sum(wlist)-1
        self._m={}
        i=0
        s=wlist[i]
        for n in range(self._rsize+1):
            if n == s:
                i+=1
                s+=wlist[i]
            self._m[n]=i    

    def i(self):
        rn=random.randint(0,self._rsize)
        return self._m[rn]


sx=[1,2,3,4]


wx=[1,10,100,1000] #weight list
ri=RandomIndex(wx)

cnt=[0,0,0,0]

for i in range(1000):
    cnt[ri.i()] +=1  #keep track of number of times each index was generated

print(cnt)  

Мне нужны были более быстрые функции, для не очень больших чисел. Итак, вот оно, в Visual C ++:

#undef _DEBUG // disable linking with python25_d.dll
#include <Python.h>
#include <malloc.h>
#include <stdlib.h>

static PyObject* dieroll(PyObject *, PyObject *args)
{
    PyObject *list;
    if (!PyArg_ParseTuple(args, "O:decompress", &list))
        return NULL;

    if (!PyList_Check(list)) 
        return PyErr_Format(PyExc_TypeError, "list of numbers expected ('%s' given)", list->ob_type->tp_name), NULL;

    int size = PyList_Size(list);

    if (size < 1)
        return PyErr_Format(PyExc_TypeError, "got empty list"), NULL;

    long *array = (long*)alloca(size*sizeof(long));

    long sum = 0;
    for (int i = 0; i < size; i++) {
        PyObject *o = PyList_GetItem(list, i);

        if (!PyInt_Check(o))
            return PyErr_Format(PyExc_TypeError, "list of ints expected ('%s' found)", o->ob_type->tp_name), NULL;
        long n = PyInt_AsLong(o);
        if (n == -1 && PyErr_Occurred())
            return NULL;
        if (n < 0)
            return PyErr_Format(PyExc_TypeError, "list of positive ints expected (negative found)"), NULL;

        sum += n; //NOTE: integer overflow
        array[i] = sum;
    }

    if (sum <= 0)
        return PyErr_Format(PyExc_TypeError, "sum of numbers is not positive"), NULL;

    int r = rand() * (sum-1) / RAND_MAX; //NOTE: rand() may be too small (0x7fff).    rand() * sum may result in integer overlow.

    assert(array[size-1] == sum);
    assert(r < sum && r < array[size-1]);
    for (int i = 0; i < size; ++i)
    {
        if (r < array[i])
            return PyInt_FromLong(i);
    }
    return PyErr_Format(PyExc_TypeError, "internal error."), NULL;
}

static PyMethodDef module_methods[] = 
{
    {"dieroll", (PyCFunction)dieroll, METH_VARARGS, "random index, beased on weights" },
    {NULL}  /* Sentinel */
};

PyMODINIT_FUNC initdieroll(void) 
{
    PyObject *module = Py_InitModule3("dieroll", module_methods, "dieroll");
    if (module == NULL)
        return;
}

(год спустя) Метод псевдонимов Уокер для случайных объектов с различными вероятностями очень быстро и очень просто