Выберите k случайные элементы из списка, элементы которого имеют веса

Принимая ваш другой вопрос в качестве предполагаемой модификации на этом, вы можете создать что-то вроде оператора switch/case

select :: Monad m => [(m Bool, m a)] -> m a -> m a
select fallback [] = fallback
select fallback ((check, action) : others) = do
    ok <- check
    if ok then action else select fallback others

newfile :: FilePath -> IO Bool
newfile x = select
    (return True)
    [ (return $ length x <= 0, return False)
    , (doesFileExist x,        return False) ]

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

newFile [] = return False
newFile fn = fmap not $ doesFileExist fn

Есть ли способ упаковать данные раньше времени - скажем, во время разработки? И когда вы толкаете приложение в магазин, часть данных уже есть?

Если данные чувствительны к времени или не готовы, или по какой-либо причине вы не можете это сделать, можете ли вы сжать данные с помощью сжатия zlib, прежде чем отправить их по сети?

Или проблема в том, что телефон умирает, делая 5K + вставляет?

Я использовал ассоциативную карту (вес, объект). Например,

{
(10,"low"),
(100,"mid"),
(10000,"large")
}

total=10110

просматривает случайное число между 0 и «total» и выполняет итерацию над ключами, пока это число не умещается в заданном диапазоне.

В вопросе, с которым вы связались, решение Кайла будет работать с тривиальным обобщением. Просканируйте список и просуммируйте общие веса. Затем вероятность выбора элемента должна быть:

1 - (1 - (#weed/(вес влево)))/(вес в n). После посещения узла вычитаем его вес из суммы. Также, если вам нужно n и у вас осталось n, вы должны явно остановиться.

Вы можете проверить, что если все имеет вес 1, то это упрощает решение киля.

Редактировано: (пришлось переосмыслить, что в два раза вероятнее)

Если выборка с заменой, используйте выбор колеса (часто используется в генетических алгоритмах):

1. Сортировка весов
2. Вычислить совокупный Вес
3. Выберите случайное число в [0,1] * Общая весов
4. Найти интервал, в котором этот номер попадает в
5. , выберите элементы с соответствующим интервалом
6. k Times

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

Если выборка с заменой, вы можете использовать этот алгоритм (реализованный здесь на Python):

import random

items = [(10, "low"),
         (100, "mid"),
         (890, "large")]

def weighted_sample(items, n):
    total = float(sum(w for w, v in items))
    i = 0
    w, v = items[0]
    while n:
        x = total * (1 - random.random() ** (1.0 / n))
        total -= x
        while x > w:
            x -= w
            i += 1
            w, v = items[i]
        w -= x
        yield v
        n -= 1

Это O ( n + m ) где м - количество элементов.

Почему это работает? Она основана на следующем алгоритме:

def n_random_numbers_decreasing(v, n):
    """Like reversed(sorted(v * random() for i in range(n))),
    but faster because we avoid sorting."""
    while n:
        v *= random.random() ** (1.0 / n)
        yield v
        n -= 1

Функция weighted_sample - это просто алгоритм, объединенный с обходом списка элементов для выберите предметы, выбранные этими случайными числами.

Это, в свою очередь, работает, потому что вероятность того, что n случайных чисел 0 .. v окажутся меньше, чем z , равна P = ( z / v ) ⁿ . Решите относительно z , и вы получите z = vP ^{1 / n} . Подстановка случайного числа на P выбирает наибольшее число с правильным распределением; и мы можем просто повторить процесс, чтобы выбрать все остальные числа.

Если выборка без замены, вы можете поместить все элементы в двоичную кучу, где каждый узел кэширует сумму весов всех элементов в этой подкуче. Высота отвала составляет O ( м ). Выбор случайного элемента из кучи с учетом веса составляет O (log m ). Удаление этого элемента и обновление кэшированных итогов также составляет O (log m ). Таким образом, вы можете выбрать n элементов за O ( m + n log m ) времени.

(Примечание: «вес» здесь означает, что каждый раз, когда элемент выбирается, оставшиеся возможности выбираются с вероятностью, пропорциональной их весам. Это не означает, что элементы появляются в выходных данных с вероятностью, пропорциональной их весам.)

Вот реализация этого с множеством комментариев:

import random

class Node:
    # Each node in the heap has a weight, value, and total weight.
    # The total weight, self.tw, is self.w plus the weight of any children.
    __slots__ = ['w', 'v', 'tw']
    def __init__(self, w, v, tw):
        self.w, self.v, self.tw = w, v, tw

def rws_heap(items):
    # h is the heap. It's like a binary tree that lives in an array.
    # It has a Node for each pair in `items`. h[1] is the root. Each
    # other Node h[i] has a parent at h[i>>1]. Each node has up to 2
    # children, h[i<<1] and h[(i<<1)+1].  To get this nice simple
    # arithmetic, we have to leave h[0] vacant.
    h = [None]                          # leave h[0] vacant
    for w, v in items:
        h.append(Node(w, v, w))
    for i in range(len(h) - 1, 1, -1):  # total up the tws
        h[i>>1].tw += h[i].tw           # add h[i]'s total to its parent
    return h

def rws_heap_pop(h):
    gas = h[1].tw * random.random()     # start with a random amount of gas

    i = 1                     # start driving at the root
    while gas >= h[i].w:      # while we have enough gas to get past node i:
        gas -= h[i].w         #   drive past node i
        i <<= 1               #   move to first child
        if gas >= h[i].tw:    #   if we have enough gas:
            gas -= h[i].tw    #     drive past first child and descendants
            i += 1            #     move to second child
    w = h[i].w                # out of gas! h[i] is the selected node.
    v = h[i].v

    h[i].w = 0                # make sure this node isn't chosen again
    while i:                  # fix up total weights
        h[i].tw -= w
        i >>= 1
    return v

def random_weighted_sample_no_replacement(items, n):
    heap = rws_heap(items)              # just make a heap...
    for i in range(n):
        yield rws_heap_pop(heap)        # and pop n items off it.