Ура! Спасибо! :) Так действительно не нужно делать массовых сдвигов и не нужно обрабатывать коллизии за счёт того, что выбранные элементы отправляются в конец массива, это корректный алгоритм!
Но требуется знать размер заранее и требуется изменять входные данные — т.е. для потоковой обработки всё-таки не подходит.
Если единичек больше, чем ноликов — будем чаще проваливаться в одну ветку алгоритма; если наоборот — в другую. Заранее не знаешь, какой вариант выгоднее.
Мне нравится вариант с обновлением в ветке про единичку, потому что в таком случае не возникает корнер-кейса с обработкой последнего элемента.
Давай ты напишешь код, который имеешь в виду? И его предметно обсудим. А то так обсуждение довольно непонятное. Код из статьи гарантированно работает за линию, проходит по данным один раз и использует O(K) дополнительной памяти, это всё, что нужно.
1 — Пусть мы знаем N и алгоритм таков: выбрать случайный номер от 1 до N, взять элемент с этой позиции, повторить K раз. Но тут нужно реализовать выбор без повторений: если я выбрал элемент с первой позиции, я не могу выбрать его ещё раз. Так что при повторе выбранной случайно позиции (коллизии) мне надо будет либо выбирать случайное число ещё раз, либо программировать собственно выбор без повторений: при выборе числа k пройтись по массиву и взять k-е ещё не выбранное число. Оба способа работают за в среднем линейное время, так что по итогу алгоритм окажется квадратичным.
2 — Можно иметь оценку до выбора, но тогда никак не обойтись без нескольких проходов.
3 — Это в любом случае на разных этапах происходит. Как правило, платят за клики, а не за показы.
Это тоже вариант, но есть несколько подвохов.
1. Если K сравнимо по величине с длиной массива, придётся часто сталкиваться с коллизиями: будем выбирать тот номер, что уже был выбран и перебрасывать кубик. В среднем там квадратичный алгоритм получается.
2. Нужно знать N заранее. Тогда надо либо все данные читать два раза (а это может быть дорого — вдруг их терабайт?), либо ограничивать работоспособность алгоритма только данными, которые влезают в память. Если работаешь на MapReduce — у тебя как правило нет ни одной, ни второй возможности. Нужно реализовать за один проход и при этом не знать полную длину входных данных.
Они не связаны, более того — они by design являются результатами независиммых измерений. Скажем, для кросс-валидации — результатами независимо проведённых кросс-валидаций с разным seed'ом разбиения. Мне кажется, что такой график хорошо показывает и среднее, и дисперсию.
Это графики вариационных рядов. Берём все полученные значения (например: прогнали CV 100 раз, получили 100 значений), сортируем их в порядке неубывания, выводим на график. Т.е. по оси X — порядковый номер величины в вариационном ряду.
Задача второго игрока — минимизировать собственный проигрыш, который в точности равен выигрышу первого игрока. (Ap, q) — это как раз и есть выигрыш первого игрока! Поэтом замена равновесной стратегии второго игрока будет эту величину увеличивать.
У меня на курсе нет лабораторок в виде очных занятий. По большей части мы используем задачки с leetcode.com и подобных ресурсов, на которых можно проверять решения автоматически. Решения потом студенты коммитят в GitHub, и мы их автоматом же анализируем на списывание и прочее. Так работает уже много лет, и дистанционность обучения совсем не играет никакой роли.
Ещё раньше я заводил задачки в некоторый аналог Яндекс.Контеста, но потом оказалось, что использовать открытые платформы существенно легче.
Да, такая функция будет расти, конечно, быстрее :)
Вообще, действительно, придумать быстрорастущую функцию — не rocket science. Тут вся суть утверждения в том, что ПРФы в принципе не способны расти сколь угодно быстро.
Ну а ещё для нас важно, что функция Аккермана растёт быстро, потому что это значит, что обратная к ней функция растёт медленно. И этим обосновывается «почти константная» асимптотика методов DSU.
Когда человек ввёл слово, он хочет автоматический пробел. Не увидев его, он начнёт вводить пробел самостоятельно, а это лишнее действие и затраты времени. Неудобно.
Подсказки тоже нужно показывать для запроса с пробелом, иначе там будет много нерелевантного.
Это вопрос архитектуры. Мобильные приложения тяжело обновлять, часть из них всегда будет старых версий и так далее, поэтому на сервер хочется перенести настолько много логики, насколько это возможно. В частности, мы можем однажды начать ранжировать на общих основаниях сразу несколько подсказок, часть из которых с пробелом, а часть без, и в текущей архитектуре это легко внедрить на серверной стороне. Если же реализовать какую-то логику работы с пробелами на клиенте, нам будет очень сложно что-то изменить.
Но требуется знать размер заранее и требуется изменять входные данные — т.е. для потоковой обработки всё-таки не подходит.
Мне нравится вариант с обновлением в ветке про единичку, потому что в таком случае не возникает корнер-кейса с обработкой последнего элемента.
2 — Можно иметь оценку до выбора, но тогда никак не обойтись без нескольких проходов.
3 — Это в любом случае на разных этапах происходит. Как правило, платят за клики, а не за показы.
1. Если K сравнимо по величине с длиной массива, придётся часто сталкиваться с коллизиями: будем выбирать тот номер, что уже был выбран и перебрасывать кубик. В среднем там квадратичный алгоритм получается.
2. Нужно знать N заранее. Тогда надо либо все данные читать два раза (а это может быть дорого — вдруг их терабайт?), либо ограничивать работоспособность алгоритма только данными, которые влезают в память. Если работаешь на MapReduce — у тебя как правило нет ни одной, ни второй возможности. Нужно реализовать за один проход и при этом не знать полную длину входных данных.
Ещё раньше я заводил задачки в некоторый аналог Яндекс.Контеста, но потом оказалось, что использовать открытые платформы существенно легче.
Вообще, действительно, придумать быстрорастущую функцию — не rocket science. Тут вся суть утверждения в том, что ПРФы в принципе не способны расти сколь угодно быстро.
Ну а ещё для нас важно, что функция Аккермана растёт быстро, потому что это значит, что обратная к ней функция растёт медленно. И этим обосновывается «почти константная» асимптотика методов DSU.
Ура! Рад, что понравилось :)
Подсказки тоже нужно показывать для запроса с пробелом, иначе там будет много нерелевантного.