(no subject)

[beldmit]

Последними дискуссиями у Витуса навеяло.

Я очень хорошо помню этот момент. Год был 1992-й, я только поступил в институт. Мы с Лешей Студеновым собирались писать на Pascal-е (C я тогда не знал) некую экономическую игру. Договорились вечером, разошлись по домам, и я задумался.

Игра начиналась с раздачи карт. Карты естественным образом ложились в двумерный массив, а раздавать надо было датчиком случайных чисел. И тут я задумался - а что, если одна и та же карта выпадет в раздаче дважды? Немного подумав, я понял, что просто повторять раздачу этой карты бесполезно - то же число может выпасть и третий раз. Мне стало очень грустно. И тут меня осенило - есть же цикл while! Он решит все проблемы!

Второго такого озарения с тех пор в моем програмистском опыте не было. Но ощущения я запомнил навсегда.

Comments

[raydac.livejournal.com]

что то маловато, когда одно, надо над собой работать

[beldmit.livejournal.com]

Нет, масса других было. Просто остальные не щелкали настолько оглушительно.

Вообще мое любимое занятие как программиста (после пристройки плюс-минус нового куска, если это не требует нудного кодирования базового фреймворка) - выжимать максимум из имеющейся архитектуры. Расшивая узкие места по необходимости, но все равно расширяя имеющееся.

[maksa.livejournal.com]

У меня такая задача возникла ещё в школе. Поскольку в школе я знал только бейсик (и немного фортрана, который тоже бейсик), то выход в виде i = i + 1 внутри цикла явился сам собой.

[slobin.livejournal.com]

Невероятное по силе озарение я испытал вот прямо сейчас, одновременно с чтением твоей записи. Я наконец-то догадался, как читать с моего мобильника текстовые файлы. Правильный ответ: он их просто читает сам, из коробки. Я почему-то думал, что это должно быть трудно, а тупо взять и попробовать тормозил.

P.S. Причём автоопределяет cp1251 и utf-8. Сейчас с интересом читаю мой любимый текст "весь юникод по алфавиту", смотрю, какие буквы в нём есть. Уже нашлись: латиница разная, греческий, кириллица, иврит, арабский, тайский и деванагари. Дальше крутить лень.

P.P.S. Но вот нормальной навигации по большому тексту встроенной всё-таки, похоже, нет.

... В Греции всё есть, даже проблемы с кодировками ...

[vitus_wagner]

Есть другой способ - при выдаче каждой следующей карты генерировать случайное число на единицу меньше.
Правда, тогда цикл понадобится для того чтобы найти карту номер N, не считая уже выданых. Но зато время завершения детерминировано.
Этот способ более точно имитирует раздачу карт из колоды. Хотя еще более точной имитацией было бы сгенерировать случайную перестановку массива, а потом просто отсчитать N первых.

[slobin.livejournal.com]

less /usr/lib/python2.5/random.py
/def sample

Узнаешь много нового и интересного (например, она пользуется двумя разными алгоритмами в зависимости от соотношения размеров колоды и выборки).

... За каникулами, книгами и кеннингами канувших князей ...

[beldmit.livejournal.com]

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

[city-rat.livejournal.com]

Эмммм... Вот так и погибает программирование, как искусство, превращаясь из математической игры в подбор подходящей языковой конструкции... Вместо учебников - доки и спеки.

Вообще-то можно просто закодить формулу, который по заданному [псевд]случайному семечку возвращает псевдослучайную последовательность заведомо неповторяющихся чисел, причем в нужном диапазоне. У Кнута, скажем, спереть - у него целый том этому посвящен, помнится.

Кинуть кубик еще раз, кстати, плохой метод, порождает уязвимости.

[beldmit.livejournal.com]

Оно не может оставаться искусством при таком количестве практикующих.

Фамилию Кнута я тогда не слышал еще.

[city-rat.livejournal.com]

О, нашел. Тридцатисекундный поиск по "последовательность неповторяющихся псевдослучайных чисел кнут"

Вопрос: хочу получить последовательность чисел от 0 до N-1, в случайном порядке, причём они не должны повторяться.

Ответ:
x(n+1) = (a * x(n) + c) % N, x(0) = rand(),

где a взаимно просто с N;
a - 1 кратно p для всех простых p — делителей m;
a - 1 кратно 4, если m кратно 4.

Выдаёт числа от 0 до N-1 в псевдослучайном порядке.

Это называется линейным конгруэнтным генератором (linear congruential generator, LCG). Существует множество других генераторов. Подробности во втором томе Кнута.

[vitus_wagner]

Аплодисменты!

[beldmit.livejournal.com]

Браво!

[arilou]

Или я не понял, или у тебя опечатка? где в формуле 'm' и есть ли какие-либо условия на 'c'?

[city-rat.livejournal.com]

Я скат-н-пейстил не вчитываясь, просто для примера. Первоисточник там указан, если кому надо - найдет.

[gegmopo4.livejournal.com]

Проще занести все карты в колоду (массив), а при выборе менять случайную карту местами с верхней и снимать с верха колоды.

[slobin.livejournal.com]

А вообще этот стиль обращения со случайными числами (если совпало с предыдущим или, скажем, попало на границу -- просто перегенерить) меня почему-то раздражает неимоверно. С полгода назад был случай -- ловлю баг в ньюлиспе, вроде бы в функции randomize. Автор вообще-то человек вменяемый, за что и люблю, но в этот раз он захотел воспроизводимого багрепорта. Воспроизводимого. В randomize. А он у меня выпадает один раз из сорока. Пришлось лезть в исходник самому -- указал ему конкретное место ошибки, а заодно ещё одной, которая была рядом по тексту. Автор поблагодарил и исправил. Я на всякий случай лезу смотрю исправления, и вижу вот ровно это: "а если выпало значение вне диапазона -- просто кинь кубик ещё раз". Причём я не могу не признать, что это на самом деле работает. Но меня почему-то раздражает.

... Ледяные ласки огненных лисиц ...

[beldmit.livejournal.com]

Ну так на то они и случайные...

Кто-то тут недавно рассказывал про GPF, вызванный ошибкой в самописном рандоме - возвращал число не от 0 до n-1, а до n - а результат использовался как индекс в массиве.

[slobin.livejournal.com]

Вот у него ровно это и было! Но он подробно тестирует свой продукт в системах с RAND_MAX = 2**31-1, а в системах с RAND_MAX = 2**15-1 так, лишь бы было. Хотя пользователей у него в этих системах дохрена. А randomize (перемешать массив) вызывает rand по числу элементов массива -- у меня около 750-и. Вот один раз из сорока оно и падало. Ну и другая аналогичная ошибка у него была в том же коде, я просто стал просматривать окрестности и заметил.

ПыСы: генератор совершенно не обязан быть самописным. Просто сишники с молоком матери впитали, что верхняя граница диапазона всегда исключительная (i=0;i<n;i++), а rand определена в stdlib как возвращающая величины от 0 до RAND_MAX включительно. Плакать после слова "грабли".

... Зачем ты выключил свопинг? ...

[beldmit.livejournal.com]

Маны надо читать. Внимательно.

[slobin.livejournal.com]

Само собой. Но согласись, что, когда весь язык пропитан духом "верхняя граница -- это следующий после", то в одном месте в стандартной библиотеке сделать её включительной -- изящный ход. Причём мне в каком-то смысле повезло, что в mingw такой куцый интервал -- у меня ошибка стала довольно быстро вылезать в реальном коде (тот самый один из сорока).

... Вы сбиваете с толку весь Париж! ...

[beldmit.livejournal.com]

Ты знаешь, я как правило не помню порядок аргументов и тому подобные вещи.

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

Из ISO 9899:1999 (E)

[yurikhan]

7.20.2.1/2: The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX.

[…]

7.20.2.2/5: Example: The following functions define a portable implementation of rand and srand.

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next / 65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

То есть да, формулировка недостаточно точная, но пример всё проясняет.

[gegmopo4.livejournal.com]

А это на самом деле единственный правильный способ генерировать целые из произвольного диапазона.