Эффективно выбрать подмножество, где каждый элемент имеет вероятность быть выбранным - PullRequest
Новая
       3

Эффективно выбрать подмножество, где каждый элемент имеет вероятность быть выбранным

0 голосов
/ 03 ноября 2019

Вызов здесь)

ИСТОРИЯ

У меня есть большая последовательность объектов: 

OBJS = [o_1, o_2, ..., o_n]

Каждый объект может быть пересчитан (чтоэто дорого). Во время пересчета он может добавлять и удалять элементы из последовательности: 

class Obj:
    def recalculate(self):
        # some expensive calcs here
        ...

        # may add objects
        if create_new_obj:
            OBJS.append(Obj())

        # may remove objects
        if delete_obj:
            del OBJS[idx]

И у меня есть цикл пересчета их, который я хочу перебрать как можно быстрее: 

while True:
    for obj in OBJS:
        obj.recalculate()

Что яможет сделать, это пересчитать не все из них каждую итерацию. Я могу добавить атрибут probability в класс Obj или добавить вероятности в последовательность, подобную этой: 

OBJS = [
    [o_1, 0.0001],  # recalculate once per 10 000 iterations in average
    [o_2, 1.0],  # recalculate each iteration
    ...,
    [o_n, 0.5]  # recalculate once per 2 iterations in average
]

Создать генератор, который возвращает подмножество объектов, которые будут пересчитаны на этой итерации: 

def pick_subset_of_randoms(sequence):
    for obj, probability in sequence:
        if random.random() <= probability:
            yield obj

И обновите цикл следующим образом: 

while True:
    for obj in pick_subset_of_randoms(OBJS):
        obj.recalculate()

ПРОБЛЕМА

Есть ли шанс оптимизировать генератор pick_subset_of_randoms?

Идеальный вариант - избегать повторения цикла for по всей последовательности. Поскольку длина подмножества может быть в десятки или сотни тысяч раз меньше длины последовательности.

Допускаются сторонние пакеты (скажем, numpy). Любые предложения приветствуются!

...