Простий алгоритм випадкової вибірки з урахуванням ваги, dotzero

Іноді вам може знадобитися вибрати випадковий елемент зі списку з урахуванням того, що деякі елементи мають більший шанс вибору, ніж інші (мають більший «вагу»). Наприклад, ви можете взяти список програм і кількість завантажень, і випадковим чином вибрати «Популярне додаток» в залежності від кількості завантажень.

У цій замітці я покажу вам два підходи до «зваженого» випадковому вибору - один підходить для невеликих списків, а інший оптимізований для більшого числа елементів.

Простий алгоритм випадкової вибірки з урахуванням ваги

У загальному вигляді цей алгоритм можна описати так:

  1. Вибрати випадкове число між одиницею і сумою «ваг» всіх елементів
  2. Спускатися по списку елементів додаючи до лічильника вага поточного елемента
  3. Перевірити, якщо лічильник (крок №2) більше або дорівнює випадковому числу (крок №1), то закінчити цикл і повернути поточний елемент. В іншому випадку перейдіть до кроку №2.

Цей алгоритм простий в реалізації і досить швидкий, коли число елементів не велике, або коли вам потрібно зробити вибір один раз. Нижче наводиться функція, яка приймає масив елементів для вибору, а також масив відповідних їм ваг, і повертає випадково вибраний пункт першого масиву. Ви можете використовувати будь-яке ціле позитивне число, як вага.

Ось приклад скрипта який виведе або A, B, C або з ймовірністю 15%, 35% і 50% відповідно:

Алгоритм випадкової вибірки з тисяч елементів

Описаний вище алгоритм може працювати дуже повільно, коли список елементів великий, і вам необхідно зробити кілька вибірок. Це тому, що він повинен пройтися по всьому масиву кожен раз при зверненні до функції.

Однак, алгоритм може бути розширений, щоб зробити його значно швидше. Замість обчислення загальної ваги (крок №1) і лічильника (крок №2) кожен раз, можна зробити це один раз і зберегти значення лічильників в масиві. Тоді ми зможемо використовувати бінарний пошук, щоб швидко вибрати правильний елемент. Нижче наведено модифікований варіант функції:

Описаний вище скрипт також містить дві нові функції - calc_lookups яка обчислює масив для використання в бінарному пошуку, і безпосередньо функція binary_search яка здійснює бінарний пошук. Приклад використання скрипта:

На закінчення

Щоб дати вам уявлення про те, яка швидкість цих алгоритмів: Для кожного з них я використовував масив включає 10 000 елементів, 10 000 разів підряд. Перший алгоритм відпрацював за 13 секунд, а другий всього 0,09 секунд.