Lines и теория вероятностей

[bigfatbrowncat]

Но мы ведь знаем, что все эти теории — ерунда, и рано или поздно, а скорее всего циклов через 80, шарик обязательно попадёт в эту единственную клетку.

Вот вы пошутили, а кто-нибудь возьмет да поверит…

[sim-dev]

Мой сын (школьник, перешел в 10-й класс) учился на курсах «программистов» и в качестве выпускного экзамена их группа делала «сетевой морской бой». Так вот, сын мой решил сделать вариант игры с компьютером (инициативно) и как раз по процитированному алгоритму. В результате когда на игровом поле остается буквально пара свободных клеток (остальные или простреляны, или заняты, или недопустимы по правилам) компьютер тратит иногда до пары минут на «случайный» выбор клетки, куда надо стрелять.
Так что теория теорией, а практика показывает, что «рано или поздно» на самом деле может быть «очень поздно».
Чтобы было понятнее: писал он на C#, между ходами компьютера делал задержки по 500 мс (иначе при удачных ходах играть было неинтересно — за доли секунды убивалось по 2-3 корабля). Вот эти самые 0,5 секунды и давали большую задержку при выборе одной из двух пустых клеток…

[frol]

Хмм, из вашего последнего предложения следует, что пауза была поставлена сразу после получения случайного числа, что достаточно наивно. Если бы пауза была поставлена уже после проверки на «нестреляность», то не должно было быть всё так печально. Пара минут — 120 секунд с задержками по 0.5 секунды — это всего лишь 240 «холостых выстрелов».

[khim]

Именно. А 240 пустых выстрелов у нас случаются с вероятностью 8%, что не так и мало. Вот, скажем, 10'000 выстрелов уже могут потребоваться в одном случае из 10⁴³. Конечно при абсолютно случайном ГСЧ, но в любом случае: если бы задержка была вставлена после проверки допустимости, то никто и никогда бы этих задержек не заметил. Даже если бы Lines запускали на старом, древнем, IBM PC с процессором на 4.77MHz.

[sim-dev]

Наивно? Ну а что вы хотите от первой попытки сделать свою программу? Конечно наивно.

[SVlad]

То есть, задержка не после завершения выстрела, а после попытки выстрелить, но до проверок?
Тогда 2 минуты — 240 попыток для угадывания 1 из 100.

[grechnik]

Ага, есть такой эффект.
geektimes.ru/post/243195

[Plone]

Бинго! Помнил, но найти быстро не смог. Сначала думал, что просто dup.
Как говорится, читайте доки. Или предыдущие посты.

[ID_Daemon]

Я искал на хабре. Поэтому и не нашел.

[boeing777]

Помню, еще в школе столкнулся с подобной проблемой, когда пытался написать карточного «Дурака»: ломал голову, как же получить случайную карту именно из оставшейся колоды, а не из всей. Правда, уже тогда решение в лоб, то есть пинать рандом до тех пор, пока не выпадет неиспользованная карта, я считал неприемлемым. В итоге было решено использовать множество (писал на дельфи): после использования карта удалялась из множества, а аргумент функции random был равен числу элементов множества. Если бы писал на Си, использовал бы std::vector. Таким образом, мы получаем равновероятный исход (насколько это позволяет random) всего за один вызов, но приходится тратить время на reallocate массива. Думаю, что разработчики Lines нашли компромисс между ресурсами и случайностью, и не было цели сделать подлянку.
На счет последней ячейки небольшая поправка: Вы указали, что шарик попадет туда, только если все ячейки левее будут заняты. Точнее так: если random вернет число 79 (т.е. предпоследняя ячейка), и она окажется занятой, то как раз будет рассмотрена последняя. В принципе это может произойти хоть в начале партии.

[ID_Daemon]

Да, я не очень точно выразился. Имелось в виду, что если все клетки от случайно выбранного места до правого нижнего угла будут заняты.

[gaelpa]

Странно, я бы скопировал реальный мир и перетасовал бы множество «колоды» в начале игры.

[boeing777]

Вы будете смеяться, но у меня была паранойя: я не хотел, чтобы кто-то мог прочитать содержимое массива с помощью средств типа artmoney. Но Ваше предложение, безусловно, оптимальнее по скорости.

[bigfatbrowncat]

… а если вместо std::vector задействовать std::list, то реаллоцировать массив и не придется…

[boeing777]

С одной стороны, да. Но в алгоритме необходим доступ к элементу по номеру (оператор []), что является нетипичной операцией для std::list.

[bigfatbrowncat]

Поиск элемента по номеру (вернее, пролистывание k элементов по цепочке) — операция несопоставимо более быстрая, нежели
1. Выделить память под n+1
2. Скопировать k-1 и еще n-k элементов
Учитывая, что удалять элемент придется при каждом доступе, этот вариант наверняка быстрее

[khim]

Поиск элемента по номеру (вернее, пролистывание k элементов по цепочке) — операция несопоставимо более быстрая

Это с какого-такого перепугу?

Вспоминаем числа, которые должен знать каждый и замечаем, что чтение из памяти занимает 100 ns (грубо), а чтение мегабайта — 250,000 ns (тоже грубо), то есть фактически вам всё равно — читать из памяти один байт или байт 300-400. Сколько там у нас данных хранится для одной карты? Один байт? Да пусть даже и десять, всё равно std::list проиграет.

1. Выделить память под n+1
2. Скопировать k-1 и еще n-k элементов

Это зачем такой ужас-то? erase в std::list память не реаллоцирует и копирует только «хвостовые элементы». В среднем — тоже половину, только для реализации на базе std::listа «плохие» варианты — когда карта ближе к концу, а для для реализации на базе std::vectorа — когда ближе к началу.

Учитывая, что удалять элемент придется при каждом доступе, этот вариант наверняка быстрее.

s/быстрее/медленнее/

При удалении карты из массива память не высвобождается, нужно всего-навсего сдвинуть данные о не более, чем о 51й карте. По сравнению с этим высвобождение памяти, которое неизбежно последует за удалением элемента из std::listа — это просто «умри всё живое»: там с неизбежностью придётся оперировать гигантскими структурами, что будет весьма медленно. Если же у нас странная колода с миллионом карт, то там, конечно, время аллокации/деаллокации станет незаметным, но проблемы со скоростью доступа к памяти никуда не денутся.

Вообще есть хорошее правило: видишь в коде std::list — требуй бенчмарков. В 90% случаев это обозначает, что человек не понимает что делает и на самом деле тут нужен либо std::vector, либо std::unordered_set, либо, редко, std::set. Задачи, для которых std::list оптимален встречаются примерно также часто как солнечные затмения. Они легко придумываются, но редко встречаются на практике.

[bigfatbrowncat]

чтение из памяти занимает 100 ns (грубо), а чтение мегабайта — 250,000 ns (тоже грубо), то есть фактически вам всё равно — читать из памяти один байт или байт 300-400

Раз уж вы начинаете разговор про оптимизацию, то учтите, пожалуйста, что так как изначальный список будет выделяться, скорее всего, за один прием, а размер кеша процессора намного длиннее, то скорее всего весь список целиком провалится в кеш. Хотя я, конечно, в этом не силен.

Это зачем такой ужас-то? erase в std::list

Не в list, а в vector, который предлагал предыдущий оратор. Я как раз и утверждаю, что удалить элемент из середины вектора много дольше, чем искать по листу.

При удалении карты из массива память не высвобождается, нужно всего-навсего сдвинуть данные о не более, чем о 51й карте. По сравнению с этим высвобождение памяти, которое неизбежно последует за удалением элемента из std::listа — это просто «умри всё живое»

Тут, пожалуй, соглашусь… хотя подзреваю, что освобождение 20 байтов из страницы, принадлежащей приложению, — это операция чуть более сложная, чем nop. Скорее всего она сведется к выкидыванию указателя из таблицы аллокации — и всё. Хотя опять же, утверждать ничего не буду — в подобных случаях предпочитаю обычно не теоретизировать, а измерять. А в конкретном случае вообще спорить не о чем — потери в любом случае ерундовые. Зря я вообще эту дискуссию начал…

[khim]

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

Только в том случае если ваша программа ничем, кроме тасования карт не занимается. Да и в этом случае вариант с вектором будет быстрее, просто выигрыш будет не ~10-15 раз, а где-то 1.5-2 раза. Не любят современные системы рандомного доступа от слова «совсем». Только кеш первого уровня их нормально обслуживает, но там мизер — от 16KiB до 64KiB даже на самых новейших процессорах. Оттуда и код и данные «вылетают» очень быстро.

Не в list, а в vector, который предлагал предыдущий оратор. Я как раз и утверждаю, что удалить элемент из середины вектора много дольше, чем искать по листу.

Это я опечатался. Конечно речь идёт о erase в std::vectorе. Это он аллокациями не занимается и перемещает только «хвост» массива, как я описал. erase в std::listе ничего никуда не двигает, понятно, но платит за это слишком большую цену.

Тут, пожалуй, соглашусь… хотя подзреваю, что освобождение 20 байтов из страницы, принадлежащей приложению, — это операция чуть более сложная, чем nop.

И да и нет. Вам в любом случае нужно простись где-то по 3-5 указателям в среднем (иногда больше в зависимости от того как аллокатор сделан), что, понятно, копейки, но обращение к массиву объёмом в ~50 байт — всё равно стоит много дешевле.

Просто этот пример очень близок оказался к оптимизации, которую мы в нашем JIT'е недавно делали. Там тоже шла обработка списков инструкций и изначально использовался std::list со всеми его накладными расходами. Потому что иногда инструкции нужно вставлять в середину списка и удалять оттуда. Но оказалось, что std::vector потому что просто меньше памяти расходует, а то, что вставление/удаление элементов стоит «дорого» оказалось неважно. И это — типичный случай. Проблема в том, что в случае, когда работа устроена как «пройтись по std::listы, подёргать пару элементов», то std::vector, как правило, выигрывает: пройтись по нему быстрее, а что «подёргать пару элеменов» — это уже не так важно! Выигрыш std::list даёт тогда, когда вы имеете огромный список с которым работаете локально — то есть не просматриваете весь список (или его существенную часть), а обрабатываете как-нибудь хитро близко расположенные элементы. Это, вообще говоря, редко случается.

Причём это одно из вещей, про которые у людей неправильное представление. Совсем неправильное. Дело в том, что «когда компьютеры были большими» обращение в память было не таким дорогим. И списки действительно имели смысл. Они и сейчас имеют смысл где-нибудь в микроконтроллерах, где память встроена в CPU. А вот на PC «disk is the new tape, and RAM is the new disk», так что многие вещи оказываются устроены совсем по другому… Но учат-то в ВУЗах студентов люди, которые хорошо помнять «старые времена» и плохо знают современную архитектуру! Приходится переучивать…

[khim]

Вот только не надо нам std::listа. Не то, что он никогда не может быть нужен, но в 9 случаях из 10 его использование — ошибка проектирования системы.

[Jeditobe]

Запуск игры на NTVDM.

[michael_v89]

Ведь если останется всего одна последняя клетка, кто знает, сколько раз придётся повторяться? Сколько времени понадобится 16-битному процессору, чтобы выполнить столько циклов?

Не совсем по теме статьи, но реально встречался с подобной ошибкой в продакшене. В системе использовалась довольно старая и сильно допиленная версия osTicket. Там есть возможность генерировать дополнительный случайный номер для заявки.
Выглядит это так (class.ticket.php):

function genExtRandID() {
	global $cfg;

	// We can allow collissions...extId and email must be unique ...so same id with diff emails is ok..
	// But for clarity...we are going to make sure it is unique.
	$id=Misc::randNumber(EXT_TICKET_ID_LEN);
	if(db_num_rows(db_query('SELECT ticket_id FROM '.TICKET_TABLE.' WHERE ticketID='.db_input($id))))
		return Ticket::genExtRandID();

	return $id;
}

EXT_TICKET_ID_LEN по умолчанию равно 6.

В итоге, когда количество заявок превысило примерно полмиллиона, система начала случайным образом падать при создании заявки. Потому что предел рекурсии 100 вызовов. Долго не могли понять, в чем дело, ошибка-то не воспроизводится.

[f0rk]

Много раз подобный код видел, и не могу понять, что мешает людям auto increment поле использовать в качестве extId? Даже если поле сильно секретное, то добавлять к нему случайную строку фиксированного размера, и никаких странных проверок делать не надо. Этот пример еще ничего, иногда бывает такое месиво из каких-то случайных чисел от которых вычисляется md5 что-то добавляется а потом все равно ищется в базе… В основном в php коде, кстати.

[SKolotienko]

Хороший пример плохого применения рекурсии вместо циклов.

[khim]

У кого? У разработчиков PHP? Даже приличные компиляторы C тут хвостовую рекурсию сотворят, а во многих языках — это основной способ реализации циклов.

[rednaxi]

Предел рекурсии 100 вызовов это не ограничение пхп, это расширение suhosin добавляет. Отключается в настройках и спокойно живете дальше.

[michael_v89]

Да, перепутал немного, 100 вызовов это было на моей машине, это ограничение XDebug. А на сервере падала по превышению лимита памяти либо по таймауту выполнения.

[dtestyk]

Когда решал подобную задачу просто последовательно проходил по всем элементам, пересчитывая вероятность для каждого: первый элемент выбираем с вероятностью m/n, второй — (m-1)/(n-1), если выбрали и m/(n-1), если нет. То есть для получения вероятности выбора текущего элемента делим число оставшихся для выбора элементов на число оставшихся.

m — число элементов, которые нужно выбрать
n — общее число элементов

[dlinyj]

Спасибо, смахнул ностальгическую слезу…

[vlivyur]

Я б генерил случайное число до 81. А потом циклически проходил бы столько пустых клеток.

[grechnik]

Если так, то первая пустая клетка будет выпадать всегда более вероятно, чем последняя. Например, при постановке второго шарика числа 0 и 80 приведут к первой пустой клетке, что сделает её в два раза более вероятной, чем любую другую (к которой приведёт только одно число).

[vlivyur]

Кажется да, чем ближе к началу, тем более вероятно. Тогда продолжаем от последнего шарика, а не с начала.

[SKolotienko]

Корректнее — генерить случаное число до <количество пустых клеток> и потом проходить столько пустых клеток.