analizer
12.12.2011 15:13 mcabber
алсо, у бывшего коллеги в вконтактике откопал красивую задачку для собеседований: «Напишите функцию выбора случайного элемента из списка неизвестной длины за один проход». Желающие позанудничать и попетросянить могут сразу в приват скинуть заявку на добавление в BL
65 comments
recommend
bookmark
subscribe
Бросать монетку каждый раз, если 1, то выбрать текущий элемент, если 0, то перейти на следующий (или в начало списка, если ВНЕЗАПНО конец).
Для любого элемента есть ненулевая вероятность его выбора, а про равномерное распределение никто и не говорил :3
Считаем длину и возвращаем элемент, ну.
за один проход
Так один проход же.
ПОЧЕМУ ТЫ МЕНЯ ИГНОРИРУЕШЬ (((((
«список» подразумевает отсутствие random-access по номеру элемента
А, ок. Тогда вариант дедфуда.
а с равномерным распределением слабо?
>>> x = range(100)
>>> import random
>>> g = lambda xx: random.choice(xx)
>>> g(x)
93
>>> g(x)
75
>>>
вообще-то там выбор случайных N элементов, но это так. я знаю два решения, одно которое якобы умное, а второе сам придумал, и сложность у него хуже, но при маленьком N и большом кол-ве элементов гораздо лучше получится.
линейная сложность и достаточно простое решение
питонисты, они все такие, да
Первым проходом собрать в массив с доступом по индексу, а затем вернуть рандомный элемент:-)
/12
что?
ну в том-то и дело, что идеальный ответ описал дедфуд (для N то же самое, только вероятность выбора менять). а вот в реальной жизни у тебя млн. объявлений рекламы, из них надо выбрать на показ 3 штуки. потому глупость это решение :)
не ко всему в этом мире можно применить random-access
хотя может эта моя задачка это про список известной длинны.
а каковы стат.свойства случайной величины? распределение должно быть равномерное? список двухсвязный/односвязный? не понятны условия
список односвязный, распределение требуется равномерное
ах да, еще существует "улучшение" этой задачи тем, что требуется решение, пригодное для Map/Reduce (до конца я тут не вдумывался, потому также предлагаю сначала дофантазировать, что имел в виду автор требования)
кажется придумал как это делать. тред не читал, только домой пришел, пора есть и спать.
Хм, для каждого элемента при проходе брать от 0 до RAND_MAX, запоминать максимум. В конце максимум будет сгенеренным числом.
Элемент, стоящий на максимуме, obv.
Такие они, питонщики :3
ну и если теперь вероятность смены элемента каждый ход уменьшать, то получится равномерное распределение.
как-то так.
вопрос в том как её уменьшать
экспоненциально, каждый раз пополам видимо.
тогда в списке о трёх элементах вероятность выбора третьего элемента — ¼, а должна быть ⅓
обратно пропорционально ? :)
вероятность выбора первого элемента зависит от длины списка, а етот элемент мы наблюдаем первым и единственный раз => полный пиздец
тут надо хитрую математику использовать.
на втором элементе отбрасываем первый и второй с вероятностью 1/2, на третьем с вероятностью 2/3-1/2, на на четвертом с вероятностью 3/4-(2/3-1/2). аналогично для остальных. надо додумать вот в эту степь.
1/2 — вероятность не отбросить первый и второй. И ? У тебя опять не выйдет равномерности.
еще раз. на втором шаге ты оба отбросишь с вероятностью 1/2 (ну, надо додумать чтоб не отбрасывались все и чтоб не невыбрасывались тоже, но тут можно просто в одну из сторон правило определить), если на третьем ты первый и второй отбросишь с вероятностью 2/3-1/2, то в сумме ты их отбросишь с вероятностью 2/3, а третий надо отбрасывать с вероятностью 2/3. когда добавляется 4й элемент тебе надо отбрасывать так, чтоб каждый был выброшен с вероятностью 3/4 и т.п. Ты на каждом шаге делаешь так, что каждый элемент выброшен с вероятностью N-1/N. понимаешь? короче я в эту степь подумаю еще.
Опять же, вероятность выбора 1-го получается 1/2, разве нет ? Если определять правило в одну сторону, то тебе нужна память :)
ну, когда их двое — да, его выбор 1/2. когда трое — 1/3. типа того.
то есть отбросить мы могли кого-то и с меньшей вероятностью, чем он заслуживает. но выберем не с большей, чем надо. хотя может я и в бреду.
Если ты не отбрасываешь элемент, то куда ты его деваешь ? Выдаешь в результат, ведь так ? Если ты выбрал для первого элемента шанс отбросить в 1/2, то равновероятным становится событие его не отбросить, т.е. отдать в результат! Что происходит с вероятностью 1/2. Это уже неравномерность.
ответ есть?
чорт, он же очевиден.
и?
смысл в том, чтоб не отдавать результат пока не дойдём до конца. то есть пока элементов два — да, вероятность того, что он выпадет равна 1/2. но если мы его не отбрасываем на шаге 2, то при шаге 3 вероятность уменьшаем до 1/3. памяти нам потребуется в худшем случае столько, чтоб держать все элементы, но по теории вероятности в среднем должен храниться один элемент :)
то есть основная идея в том, что если всего элементов N (хотя мы этого не знаем), то в конечном счете мы каждый элемент отбросим с вероятностью (N-1)/N либо же меньше. но если мы какой-то элемент отбросим с меньшей вероятностью (скажем, 1/2), нас это тоже устроит, потому как можно сказать, что вероятность отбрасывания на (N-1)/N равна вероятности "1/2 OR ((N-1)/N — 1/2)"
вероятность выбора i-ого элемента равна 1/i
тогда ты всегда будешь выбирать 1й элемент. класс!
правильно, первый элемент всегда выбираем. и идём дальше, до конца.
лол, да :)
и что в конце? какой выбираем?
запоминаешь последний выбранный)
какой последний выбрали тот и возращаем.
да всё очевидно же, чото вчера сразу не допёр.
ну вот всего их три. третий не выбрал, а выбрал второй. получается ты его с вероятностью 1/2 выбрал, да?
точнее 2/3 — 1/2 вероятность того, что второй выберешь
всего их три! у тебя было 3 шанса выбрать 1.
понял
он был ещё до поста.
по теории вероятности рано или поздно случится худший случай
по теории вероятности рано или поздно вероятность худшего случая будет нулём.
не занудничай. не надо ничего хранить. расход памяти у решения — константный, сложность — линейная
да уже rtsome всё решил же )
ну да, именно так. можно даже строгое доказательство в лучших традициях ТерВера сделать
Закон больших чисел и я не согласны с тобой.
и я, а это двое пстачевцев — это куда хуже чем какой-то там математический закон
Сколько нужно пстачевцев, чтобы закидать угнича говном ?
ни одного, настоящий пстачевец отрицает существование угнича
отрицает закон угнича