Мы провели небольшую раздачу для запуска Toolz, и я сделал розыгрыш ленивым способом: вклеил список участников в электронную таблицу, добавил столбец =RAND(), и отсортировано по нему. это сработало, но друг, который зарабатывает на жизнь статистикой, оглянулся через мое плечо и сказал: " вы знаете, что на самом деле это не однородно, верно?" Он был прав, и кроличья нора, в которую я попал в тот вечер, - это большая часть того, почему у Toolz теперь есть надлежащее рандомизатор списков так перетасовывается правильно Это руководство - то, что я узнал, написанное для всех, кому нужно вытащить имена из шляпы и хочется, чтобы шляпа была честной.
TL;DR: Рандомизатор списков либо переупорядочивает целый список случайным образом (перетасовка), либо вытягивает из него случайную выборку (выбор).Хорошие используют перетасовку Фишера-Йейтса и криптографический случайный источник, поэтому каждый порядок одинаково вероятен. Используйте перетасовку для порядка хода и рассадки, а также выбирайте подарки и образцы. Этот инструмент запускает клиентскую сторону, по умолчанию вытягивает без замены, поэтому победители уникальны и отказываются рисовать больше уникальных элементов, чем держит список.
Я создаю продукты SaaS на Laravel и React, поэтому меня здесь волнуют две вещи: правильно посчитать и сделать интерфейс достаточно очевидным, чтобы вы никогда не задавались вопросом, был ли розыгрыш честным. Оба оказываются более важными, чем звучат.
Что такое рандомизатор списков?
Рандомизатор списков берет список элементов, по одному на строку, и переставляет или выборочно его. Изрядная перетасовка - это решенная проблема с неправильным ответом, который выглядит правильным: сортировка по случайному ключу смещена, а перетасовка Фишера-Йейтса - нет, и браузер обеспечивает несмещенные биты crypto.getRandomValues(). Вставляйте имена, призы, задачи, команды или идеи, и он либо возвращает весь список в перетасованном порядке, либо выбирает количество победителей, о которых вы просили. Это программная версия рисования сложенных промахов из чаши, с тем преимуществом, что она устраняет тихую предвзятость, которую люди вносят, когда пытаются выбрать "randomly" вручную.
На самом деле есть только две операции, и зная, какая из вас хочет, это весь навык. Shuffle возвращает каждый предмет, который вы ему дали, просто в новом случайном порядке, поэтому ничего не добавляется или теряется. Pick возвращает подмножество, вытягивая определенное количество предметов из бассейна. розыгрыш - это выбор.Решение того, кто первым представит в стойке, - это перетасовка. Большинство людей хотя бы раз тянутся не к той, обычно пытаясь "перетасовать и взять тройку и квоту; когда Pick со счетом три делает то же самое за один шаг.
Как на самом деле работает честная перетасовка?
Вот часть, которую мой друг-статистик получил в. Трюк с электронной таблицей, назначая случайное число каждой строке и сортируя, кажется случайным, но не однородным. алгоритмы сортировки делают сравнения, и когда два случайных ключа случается быть близкими, крошечные предубеждения в том, как связи и сравнения разрешают утечку в результат. В маленьких списках перекос мал, но он реален, и для всего, где справедливость является точкой, "close достаточно & quot; не является отличным ответом.
Правильный метод - это тасование Фишера-Йейтса, иногда называемое тасованием Кнута после того, как Дональд Кнут популяризировал версию in-place.Оно было описано Рональдом Фишером и Фрэнком Йейтсом в 1938 году и учитывая его современную компьютерную форму Ричардом Дерстенфельдом в 1964 г. Идея проста. Перейдите по списку от последнего пункта ко второму. В каждой позиции выберите случайный индекс от начала списка до текущей позиции включительно, затем поменяйте местами два пункта. Потому что каждый своп вытягивается из сокращающегося, четко определенного диапазона, каждый из возможных порядков выходит с точно равной вероятностью. Он выполняется за линейное время, касаясь каждого элемента один раз, и ему не требуется никакой дополнительной памяти за пределами самого списка.
выше рандомизатор списков использует этот алгоритм напрямую. когда вы выбираете без замены, это та же самая перетасовка, остановленная заранее: перетасуйте список, затем возьмите первые N пунктов. Это гарантирует, что победители различны и что каждая возможная группа победителей одинаково вероятна.
Откуда берется случайность?
Алгоритм справедлив лишь так же, как и случайные числа, питающие его. если источник случайности предсказуем или предвзят, то идеальная перетасовка все равно дает искаженный результат. именно здесь браузер зарабатывает себе на жизнь.
Современные браузеры разоблачают crypto.getRandomValues, часть W3C Web Cryptography API, которая заполняет массив криптографически сильными случайными значениями, взятыми из пула энтропии операционной системы. это гораздо более сильный источник, чем Math.random, который быстрый псевдослучайный генератор никогда не предназначался для чего-либо, где предсказуемость имеет значение Рандомизатор предпочитает crypto.getRandomValues и только возвращается к Math.random когда криптоисточник действительно недоступен, чего в текущем браузере почти никогда не бывает.
Есть еще одна тонкость, которую я должен был получить правильно, Чтобы превратить случайное 32-битное число в несмещенный индекс от 0 до N минус 1, вы не можете просто взять остаток после деления на N, потому что, если N не делится равномерно в диапазон, низкие индексы появляются немного чаще. исправление - это выборка отказа: вычислить наибольшее кратное N, которое подходит в диапазон, и если жеребьевка приземляется выше этого порогового значения, выбросить его и снова рисовать. Это стоит незначительное количество дополнительных розыгрышей и полностью удаляет смещение. Инструмент делает это на каждом выбранном индексе, и это такая деталь, которую никто не замечает, пока она не пропадет.
Как мне использовать рандомизатор?
В интерфейсе есть одна кнопка и пара вариантов. Вот как я его запускаю.
Вставьте свой список в поле ввода, по одному элементу в строке. Если вы скопировали ячейку, разделенную запятыми, из электронной таблицы, переключите разделитель ввода на запятую, и вместо этого он разделится на запятые. Поведение обрезки и выпадения включено по умолчанию, поэтому пустые пустые строки и случайные ведущие пробелы не становятся фантомными записями.
Выберите свой режим. перетасовка переупорядочивает все.Выберите розыгрыши победителей. если вы выберете "Выбрать", появится небольшая панель, на которой вы установите, сколько рисовать и разрешены ли повторы. оставьте повторы для розыгрыша, чтобы каждый победитель был разным человеком. включайте повторы только тогда, когда вы действительно хотите семплировать с заменой, например, когда вы имитируете розыгрыши, похожие на кости, и одно и то же значение может законно повториться.
Нажмите Рандомизировать. вы получаете свежий, независимый результат каждый раз, поэтому, если вы хотите перерисовать вы просто нажмите еще раз. скопируйте вывод одним щелчком мыши, чтобы вставить его в свое объявление, ваш билет или где результат должен жить. Если вы просите более уникальных победителей, чем может предоставить список, инструмент говорит вам вместо того, чтобы тихо возвращать короткий или повторяющийся список, что является ошибкой, которую я видел другие инструменты.
На практике списки, которые я вставляю, повсюду на карте. В некоторые дни это столбец писем клиентов для розыгрыша призов, в другие дни это имена в моей команде для тех, кто рассматривает следующий запрос на извлечение, и как только это был каждый ресторан в шаговой доступности, потому что никто не мог решить на обед. Инструмент не заботится о том, что это за предметы, только то, что они разделены чисто. Вот почему параметры ввода заслуживают второго внимания: если ваш источник - ячейка электронной таблицы, разделитель запятых спасает вас от ручного редактирования, и если это беспорядочная копипаста с пустыми рядами, раскрывающаяся папка по умолчанию незаметно очищает его перед розыгрышем. Минута, потраченная на форматирование ввода, - это минута, которую вы не тратите на споры о том, считается ли случайная пустая строка запись запись записью.
Когда мне следует перетасовать и когда мне следует выбирать?
Эти два режима охватывают разные работы, а в таблице ниже представлена шпаргалка, которую мне хотелось бы иметь, когда я начинал.
| ты хочешь... | обычай | Повторяет | почему |
|---|---|---|---|
| Решите говорить или порядок поворота | Перетасовывать | н/д | Все остаются в порядке, порядок справедлив |
| Ничья один победитель розыгрыша | Выбирайте, считайте 1 | Выключить | Единый уникальный результат |
| Нарисуйте несколько лауреатов призов | Пик, граф Н | Выключить | Отличные победители, без двойного погружения |
| Назначьте людей в две команды | Перетасовать, потом расколоть | н/д | Разделить перетасованный список пополам |
| Образец с заменой на сим | Пик, граф Н | На | Тот же предмет может повторяться по замыслу |
| Рандомизировать список воспроизведения или список чтения | Перетасовывать | н/д | Закажите, ничего не отказывая |
Эмпирическое правило: если количество предметов должно оставаться прежним, перетасуйте Если вы хотите, чтобы предметов было меньше, чем вы вставили, выберите. Командное назначение - это то, о чем люди слишком много думают. Перетасуйте полный список, затем возьмите первый тайм за команду А, а остальные за команду Б, и обе команды случайны и сбалансированы по размеру.
Достаточно ли справедливо проводить публичную раздачу?
Да, и причина стоит прямо заявить, потому что & quot;fair& quot; это вся ценность инструмента. сочетание перетасовки Фишера-Йейтса, криптографического случайного источника и выборки отказа означает, что каждый участник имеет одинаковый шанс, и каждый возможный набор победителей одинаково вероятен. Это более сильная гарантия, чем физическая вытяжка, когда размер скольжения, складывание и то, насколько хорошо перемешана чаша, все это приводит к предвзятости.
Поскольку розыгрыш полностью выполняется в вашем браузере, вы можете сделать это в прямом эфире на экране во время потока или встречи, что является прозрачностью, которую люди хотят от публичного розыгрыша. Ничего не отправляется на сервер, поэтому нет скрытого шага, с помощью которого результат можно было бы подделать между вашим щелчком мыши и объявлением. Если вам нужен контрольный журнал, запишите на экране розыгрыш: список участников виден, щелчок виден, и победители появляются немедленно.
Мой список частный?
Это имеет большее значение, чем кажется на первый взгляд, потому что списки, которые люди рандомизируют, часто не являются общедоступными. Короткие списки кандидатов, внутренние имена команд, записи клиентов и списки адресов электронной почты - все это конфиденциально. Рандомизатор обрабатывает все локально с помощью простого JavaScript. Ваш список никогда не загружается, не регистрируется и не сохраняется, и вы можете подтвердить это на вкладке сети браузера, где нажатие "Рандомизация" вообще не вызывает запросов. Он также продолжает работать в автономном режиме после загрузки страницы.
Это преднамеренная позиция в Toolz, и я написал об обосновании в примечании Конфиденциальность данных в онлайн-инстру. Рандомизатор - хороший пример того, почему он имеет значение: входные данные часто представляют собой список реальных людей, а список реальных людей - это именно то, чего вы не хотите, сидя в журнале запросов на каком-то сервере, который вы никогда не проверяли.
Несколько привычек, которые делают рисунки чище
Очистите список перед тем, как нарисовать Включите удалить дубликаты, если один человек может появиться дважды, поэтому двойная запись не удваивает тайно их шансы.Опускание пустых линий включено по умолчанию, но стоит взглянуть, чтобы убедиться, что конечная пустая линия не была засчитана.
Сопоставьте счет с призами В режиме Pick установите счет точно на нужное вам количество победителей и оставьте повторы выключены Если у вас есть три приза, вытяните три сразу, а не щелкайте один тираж три раза, что позволяет избежать неловкого случая с одним и тем же именем, возникающего дважды в отдельные щелчки.
Перерисовывать открыто, а не тайно Если победитель не имеет права участвовать, удалите их и перерисуйте перед тем, кто смотрит. Справедливость исходит из того, что процесс виден, а не из того, что результат является окончательным при первом щелчке.
Храните его в браузере. как и в случае с каждым инструментом, который я отправляю, локальная обработка является стандартом, потому что она быстрее и приватна. если вы собираете персональный комплект небольших утилит, генератор случайных чисел естественным образом сочетается с рандомизатором для числовых розыгрышей и шире Инструменты повышения производительности разработчик roundup объясняет, почему стоит создать набор инструментов, ориентированный на браузер.
Сопутствующие инструменты, на которые стоит обратить внимание
Если случайный выбор является постоянной потребностью, рядом с ним сидят несколько соседей. The генератор случайных чисел рисует числа в диапазоне с той же случайностью крипто-класса, что и нужно, когда вещь, которую вы выбираете, является значением, а не элементом из списка.The Генератор UUID производит уникальные идентификаторы для записей и тестовых данных.The генератор паролей применяет тот же сильный случайный источник для производства безопасных паролей. все три работают в браузере без регистрации, точно так же, как рандомизатор, и я покрываю сторону идентификатора этого семейства в руководство генератора паролей, йо-
Часто задаваемые вопросы
Как работает рандомизатор списка?
Инструмент считывает ваш список по одному пункту в строке, затем либо переупорядочивает каждый пункт, либо вытягивает запрошенных вами победителей. Перетасовка использует алгоритм Фишера-Йейтса, который прогуливается по списку один раз и меняет каждый элемент на случайно выбранную более раннюю позицию, создавая равномерно случайный порядок. Случайные позиции поступают от криптографического генератора браузера, поэтому результат действительно непредвзят.
Действительно ли рандомизация справедлива?
Да. он черпает из crypto.getRandomValues, криптографического случайного источника, встроенного в современные браузеры, и использует выборку отбраковки, поэтому ни один индекс не является даже немного более вероятным, чем другой. в сочетании с перетасовкой Фишера-Йейтса каждый возможный порядок вашего списка имеет равные шансы, что справедливее, чем ручная перетасовка или сортировка электронных таблиц случайным ключом.
Как выбрать случайного победителя из списка имен?
Вставьте свои имена по одной строке, переключитесь в режим выбора, установите счетчик 1 и нажмите «Рандизаруй». Инструмент возвращает одно случайное имя. Чтобы привлечь сразу нескольких победителей, установите более высокий счет и оставьте повторы отключенными, чтобы каждый победитель был уникальным.
В чем разница между перетасовкой и выбором?
Shuffle возвращает весь ваш список в новом случайном порядке, поэтому ничего не добавляется или удаляется, только переставлено. Pick возвращает подмножество, выведя количество победителей, указанных в списке. Используйте перемешивание для заказа или рассадки, а также выберите для подарков, образцов или выбор нескольких человек из большей группы.
Можно ли выбрать один и тот же предмет более одного раза?
Только если вы включите повторы По умолчанию режим Pick рисует без замены, поэтому каждый победитель является другим элементом, что и нужно для розыгрыша или розыгрыша Включение повторов позволяет осуществлять выборку с заменой, где тот же элемент может появиться снова, что полезно для моделирования.
Почему он не может выбрать больше уникальных предметов, чем в моем списке?
Без повторов каждый победитель должен быть отдельным предметом, поэтому вы не можете набрать десять уникальных победителей из списка из восьми. Когда это произойдет, инструмент сообщает вам вместо того, чтобы возвращать неверный результат. Либо понизьте счетчик, чтобы он соответствовал размеру списка, либо включите повторы, чтобы элементы можно было использовать повторно.
Мой список загружен на сервер?
Нет. все анализы и рандомизация выполняются локально в вашем браузере с простым JavaScript, и ничего не передается, не регистрируется и не сохраняется. Вы можете подтвердить это на вкладке сети вашего браузера, где при нажатии "Рандомизировать" не делается никаких запросов. Он также работает в автономном режиме после загрузки страницы.
Могу ли я использовать его для розыгрыша или розыгрыша?
да. Вставьте своих участников по одной строке, используйте режим выбора с отключенными повторами и установите количество призов. Каждый клик рисует свежий, независимый набор уникальных победителей. Поскольку розыгрыш является непредвзятым и происходит на стороне клиента, вы можете запускать его в прямом эфире для прозрачности.
