google web font

четверг, 19 мая 2011 г.

random debugging

Пример дедуктивного способа дебажить логику. На прошлой неделе гугл настоятельно подсовывал мне новости про отмену результатов розыгрыша грин-карт (например). Отменили, потому что, судя по результатам, логика выбора победителей была какой-то сомнительной, а рандом был не очень рандомным. Странным в результатах было то, что 90% выигравших заявок были поданы в первые два дня.

Правильного "компьютерщика" одним из первых должен заинтересовать вопрос "как такое возможно вообще?" Начать можно с того, что теории вероятности этот результат не противоречит, несмотря на то, что он такой подозрительный. То есть, теоретически, есть вероятность получить такой результат и при правильных алгоритмах. Однако совершенно очевидно, что это не оправдание.


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

Способ посерьёзнее состоит в предварительном отборе какой-то части (например, четверти) заявок по методу, аналогичному предыдущему, а потом выбору победителя среди них. Этот способ похож на выборы с двумя турами голосования. Более серьёзным этот метод делает двухэтапность.

Кстати, про выборы. Правильный алгоритм можно сделать ещё и так: берём каждую заявку и для неё генерируем случайное число от одного до десяти. Потом собираем заявки, получившие самое большое количество очков и повторяем процедуру, пока не определится победитель.

Представить себе, что среди победителей при использовании описанных подходов окажется 90% заявок, поданных в первые день регистрации достаточно сложно — только если 90% всех заявок реально были поданы в первые два дня регистрации.

А как же сделать так, что бы ошибка, которая привела к отмене результатов, стала реальностью? Во-первых, как я уже отметил, теория вероятности не запрещает появления такой ситуации. То есть, самый первый метод — это быть счастливчиком. Но это не ошибка :-)

Второй способ тоже прост, его нам подсказывает простая арифметика: для того, чтобы 90% выигравших заявок оказались оформленными в первые два дня, достаточно, чтобы 90% всех заявок были реально зарегистрированы в первые два дня. Этот вариант интересен тем, что ошибка находится вне алгоритма выбора счастливчика — и именно по этой причине я не буду тут рассматривать способы устроить такой вариант: я хочу придумать именно бажный алгоритм. Однако в реальности, вероятнее всего, ошибка была именно в этом месте.

А вот по поводу неправильного рандома — есть у меня на примете один "метод". Кто хоть раз видел циклы, тот поймёт, что тут происходит, пример на перле:
foreach $req (@requests) {
    if ( int(rand(2)) ) {
        print "winner is $req\n";
        last;
    }
}
Для непрограммистов поясню: здесь берётся по очереди каждая заявка и для неё бросается монетка: орёл — выиграла, решка — нет выиграла. Какая заявка первой получит орла — та и победила. Как несложно догадаться, уже десятая заявка выиграет чуть меньше, чем в одном случае из тысячи, в половине случаев выиграет первая. Считайте этот способ сортировки методом "Единой России", а метод — запатентованным: "Единая Россия" в половине бюллетеней попадает на первое место.

Есть ещё не такой смешной вариант: надо разделить все заявки на десять групп, выбрать произвольную группу и набрать оттуда победителей. Издевательство над теорией вероятности и здравым смыслом в этом варианте, в отличие от предыдущего, нельзя объяснить ни ошибкой, ни неграмотностью, ни хотя бы злым умыслом, поэтому считаем его нереальным.

Других способов получить такую ошибку с помощью неправильного алгоритма выбора победителя я придумать не смог. Помогайте. 

Комментариев нет:

Отправить комментарий