Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 23
Иногда требуется детерминированное поведение, например, в тестах. По идее можно предусмотреть в RandomProvider'е возможность выдавать заранее инициализированный ГПСЧ и использовать этот вариант в тестах. При этом должна быть возможность его сбрасывать в исходное состояние, чтобы результат не зависел от порядка выполнения тестов.
Абсолютно согласен.
Кстати, Джим Митчелл реализовал Random-like оболочку вокруг RNGCryptoServiceProvider: Cryptographically Secure Random Numbers. И хотя она, возможно, не столь идеальна, как того хотелось бы Джону Скиту, ею вполне возможно пользоваться. Не хотел это вставлять в статью ради чистоты перевода, так сказать.
Кстати, Джим Митчелл реализовал Random-like оболочку вокруг RNGCryptoServiceProvider: Cryptographically Secure Random Numbers. И хотя она, возможно, не столь идеальна, как того хотелось бы Джону Скиту, ею вполне возможно пользоваться. Не хотел это вставлять в статью ради чистоты перевода, так сказать.
Казалось бы, времена ассемблера давно прошли… Ан нет, все ещё приходится писать страницы кода чтобы получить простой тривиальный результат, вроде вычисления случайного числа. Платформы наращивают номера с все убыстряющимся темпом, а программисту почему-то не сильно легчает от этого. Может не в том направлении шагаем?
А почему Вы решили, что я имел в виду алгоритмическую сложность?
r = rand(1);
одна строчка, одно действие — в переменную r попадает (псевдо)случайное значение в диапазоне [0..1). Если нет никаких подводных камней вроде проблем с инициализацией и тредовой безопасностью, можно спокойно программировать дальше то что задумал, и не отвлекаться на низкоуровневые вещи. Я ж сравнение с ассемблером не зря упомянул.
r = rand(1);
одна строчка, одно действие — в переменную r попадает (псевдо)случайное значение в диапазоне [0..1). Если нет никаких подводных камней вроде проблем с инициализацией и тредовой безопасностью, можно спокойно программировать дальше то что задумал, и не отвлекаться на низкоуровневые вещи. Я ж сравнение с ассемблером не зря упомянул.
Практика показывает, что если Вы пишете что-то сложнее курсовой младших курсов института, то подводные камни — есть.
Просто Вы о них(пока еще) не знаете. Но в продакшне вылезет.
То же rand() без srand() — а, от запуска к запуску будет выдавать одно и то же. Ну то есть игра, например, в нарды будет вызывать чувство дежа вю. А если с srand()-ом с сидом с таймера — то как воспроизвести в тестах? Да и вообще — воспроизвести.
Просто Вы о них(пока еще) не знаете. Но в продакшне вылезет.
То же rand() без srand() — а, от запуска к запуску будет выдавать одно и то же. Ну то есть игра, например, в нарды будет вызывать чувство дежа вю. А если с srand()-ом с сидом с таймера — то как воспроизвести в тестах? Да и вообще — воспроизвести.
А не кажется ли Вам, что в rand() можно встроить проверку был ли инициализирован srand()? И ещё сделать его сразу threadsafe? Т.е. избавить сотни тысяч! программистов от необходимости тратить миллионы человеко-часов на всю эту рутину и избавить их от необходимости выискивать неочевидные ошибки? А для тех, кому действительно надо, — оставить возможность при необходимости покопаться под капотом, как-то выставить начальное состояние принудительно или ещё что-то, для тех же тестов.
> А не кажется ли Вам, что в rand() можно встроить проверку был ли инициализирован srand()?
Он всегда инициализирован. По умолчанию единицей. Что дает полностью предсказуемый результат. Для тех, кого не устраивает, как раз и сделали функцию srand(). Просто про нее надо знать.
> И ещё сделать его сразу threadsafe?
Да запросто. С бесплатным бонусом в виде возросшего на порядок времени исполнения и малопредсказуемыми дедлоками.
> и избавить их от необходимости выискивать неочевидные ошибки?
Вы хотите сказать — добавить им необходимости выискивать неочевидные ошибки?
Собственно, rand() так и сделан — предельно просто и очевидно. И потому для реальных целей малоприменим. Все равно придется писать объекты-обертки, если не вообще менять алгоритм генерации, т.к. дефолтная реализация, скажем прямо, не жжет.
Языки программирования, они как правило делаются не для студентов все же, а для коммерческого ПО. Где подразумевается, что пишущие имеют представление о том, как оно должно работать. Поэтому C#-овский рандом сделан именно так — минимализм и расширяемость в ущерб удобству использования «из коробки». Зато максимально прозрачно.
Он всегда инициализирован. По умолчанию единицей. Что дает полностью предсказуемый результат. Для тех, кого не устраивает, как раз и сделали функцию srand(). Просто про нее надо знать.
> И ещё сделать его сразу threadsafe?
Да запросто. С бесплатным бонусом в виде возросшего на порядок времени исполнения и малопредсказуемыми дедлоками.
> и избавить их от необходимости выискивать неочевидные ошибки?
Вы хотите сказать — добавить им необходимости выискивать неочевидные ошибки?
Собственно, rand() так и сделан — предельно просто и очевидно. И потому для реальных целей малоприменим. Все равно придется писать объекты-обертки, если не вообще менять алгоритм генерации, т.к. дефолтная реализация, скажем прямо, не жжет.
Языки программирования, они как правило делаются не для студентов все же, а для коммерческого ПО. Где подразумевается, что пишущие имеют представление о том, как оно должно работать. Поэтому C#-овский рандом сделан именно так — минимализм и расширяемость в ущерб удобству использования «из коробки». Зато максимально прозрачно.
Зачем придираться к словам? Разумеется у генератора будет стартовое состояние после создания, но я ведь имел ввиду «инициализацию» как подготовку к выдаче различающихся псевдослучайных чисел, а не одного и того же потока для каждого запуска программы. Ведь в 99.(9)% случаев программисту надо именно просто какое-то похожее на случайное число, и крайне желательно чтобы оно было НЕ предсказуемым. А srand() то как раз сделали для того чтобы получать ПРЕДСКАЗУЕМЫЙ поток, а вовсе не для тех, кого он не устраивает )
Да прямо уж на порядок. )) Звучит страшно, а давайте аккуратно проанализируем? Для одного потока блокиратор только один, а значит конкуренции за мютекс ему ждать неоткуда — так что тут оверхед микродоли процента. Для нескольких потоков — необходимо лочить сид чтобы им не воспользовался паралельный поток для получения такого же числа. Можно лочить втупую, до тех пор пока не посчитаем новое значение, а можно в умную, проинкрементив сид и отпустив лок (чтобы паралельный поток получил отличающееся число без ожидания мютекса), и потом проапдейтить сид, когда новое значение будет высчитано (тут и лок без необходимости). Опять оверхед очень и очень далек от «возросшего на порядок времени»…
>Вы хотите сказать — добавить им необходимости выискивать неочевидные ошибки?
Вы, очевидно, не пытаетесь понять мою мысль. Если программисту нужно случайное непредсказуемое число, то в чем вообще может произойти ошибка, если он его получит легко и без напряга?
>И потому для реальных целей малоприменим.
Вдумайтесь в свои слова ) Если реализовано малоприменимое решение, вместо применимого, то налицо архитектурный дефект.
Да прямо уж на порядок. )) Звучит страшно, а давайте аккуратно проанализируем? Для одного потока блокиратор только один, а значит конкуренции за мютекс ему ждать неоткуда — так что тут оверхед микродоли процента. Для нескольких потоков — необходимо лочить сид чтобы им не воспользовался паралельный поток для получения такого же числа. Можно лочить втупую, до тех пор пока не посчитаем новое значение, а можно в умную, проинкрементив сид и отпустив лок (чтобы паралельный поток получил отличающееся число без ожидания мютекса), и потом проапдейтить сид, когда новое значение будет высчитано (тут и лок без необходимости). Опять оверхед очень и очень далек от «возросшего на порядок времени»…
>Вы хотите сказать — добавить им необходимости выискивать неочевидные ошибки?
Вы, очевидно, не пытаетесь понять мою мысль. Если программисту нужно случайное непредсказуемое число, то в чем вообще может произойти ошибка, если он его получит легко и без напряга?
>И потому для реальных целей малоприменим.
Вдумайтесь в свои слова ) Если реализовано малоприменимое решение, вместо применимого, то налицо архитектурный дефект.
Про синхронизацию — бред.
Время выполнения Monitor.Enter/Monitor.Exit раза в 3-4 больше чем у Random.GetDouble.
Микродоли процента — это в ваших тёплых снах. А в hi-performance computing локи — это не такая радуждая вещь. Почитайте на досуге о lock free synchronizations. Например у Альбахари.
Время выполнения Monitor.Enter/Monitor.Exit раза в 3-4 больше чем у Random.GetDouble.
Микродоли процента — это в ваших тёплых снах. А в hi-performance computing локи — это не такая радуждая вещь. Почитайте на досуге о lock free synchronizations. Например у Альбахари.
Слово spinlock вам ничего не говорит? Мьютексы, они, знаете ли, очень разные бывают ) Правда, не знаю особенности реализации блокировок в .NET, поэтому не стану утверждать, что на этой платформе thread-safety реализуется без больших накладных расходов.
1. Мьютексы при невозможности взять лок (когда он занят уже) на .NET под виндой уходят в код ядра. Это дико медленно на фоне генерации ПСЧ. Подозреваю что раз в 50 больше времени занимает.
2. Spinlock вам ничем не поможет. Его взятие будет ещё дороже чем Monitor.Enter/Exit. Да, он эффективнее для случаев когда очень большая concurrency, но опять же, потерять 90% перфоманса это слишком.
Thread-safety реализуется на любой платформе с огромными накладными расходами на фоне расходов на генерацию ПСЧ.
2. Spinlock вам ничем не поможет. Его взятие будет ещё дороже чем Monitor.Enter/Exit. Да, он эффективнее для случаев когда очень большая concurrency, но опять же, потерять 90% перфоманса это слишком.
Thread-safety реализуется на любой платформе с огромными накладными расходами на фоне расходов на генерацию ПСЧ.
1. Это везде так, ведь надо шедулеру управление передать и усыпить тред. Но это самый тяжелый случай, когда лок занят надолго, на блокирующейся операции например, или долгих вычислениях…
2. Гм, у Вас неверное представление о spinlock-ах — это самые дешевые (в плане взятия) и быстрые (в плане времени на взятие/освобождение) локи, но они создают большую дополнительную нагрузку на cpu в тех тредах, которые пытаются захватить заблокированный ресурс, поэтому должны использоваться недолго. Например, при обновлении переменной.
3. Thread-safety сегодня — насущная необходимость, и уже много ресурсов было брошено на оптимизацию этого вопроса, так что не все так страшно, как было 10 лет назад.
2. Гм, у Вас неверное представление о spinlock-ах — это самые дешевые (в плане взятия) и быстрые (в плане времени на взятие/освобождение) локи, но они создают большую дополнительную нагрузку на cpu в тех тредах, которые пытаются захватить заблокированный ресурс, поэтому должны использоваться недолго. Например, при обновлении переменной.
3. Thread-safety сегодня — насущная необходимость, и уже много ресурсов было брошено на оптимизацию этого вопроса, так что не все так страшно, как было 10 лет назад.
Последний раз. Потокобезопасный генератор псевдослучайных чисел (разумеется если брать непотокобезопасный алгоритм) будет в разы медленнее его непотокобезопасного аналога при применении в однопоточном контексте (это наиболее используемый сценарий).
Медленнее он будет потому что любая синхронизация на практике окажется дороже генерации ПСЧ (несомненно есть тяжёлые алгоритмы генерации ПСЧ, но я говорю о простейших).
То же самое проецируется на коллекции.
Вы можете свои теоретические познания продолжить изливать в тред, но к сожалению практика иная. И я перед тем как писать всё же создал проект и прогнал там тесты на время. Давайте вы почитаете Albahari и этим закончим. Вот вам cсылочка.
www.albahari.com/threading/
Медленнее он будет потому что любая синхронизация на практике окажется дороже генерации ПСЧ (несомненно есть тяжёлые алгоритмы генерации ПСЧ, но я говорю о простейших).
То же самое проецируется на коллекции.
Вы можете свои теоретические познания продолжить изливать в тред, но к сожалению практика иная. И я перед тем как писать всё же создал проект и прогнал там тесты на время. Давайте вы почитаете Albahari и этим закончим. Вот вам cсылочка.
www.albahari.com/threading/
За ссылку спасибо. Хоть я и не под виндой программирую, но немного интересно, что и как на другой стороне происходит.
Согласен, что дискуссию можно завершать, ведь генерация ПСЧ действительно происходит быстро и не должна включать в себя переключение контекста, да и изначально мой месседж состоял в том что инструментарий для программисто надо готовить тщательно, а не так чтобы его потом ещё напильником надо было дорабатывать.
Тем не менее, есть один момент касательно
Смотрим http://www.albahari.com/threading/part5.aspx#_SpinLock_and_SpinWait:
Я уже упоминал постом выше про свойства спинлока — это самый оптимизированный способ залочить очень короткую операцию, по сравнению с которой любые другие способы блокировки приведут к оверхеду, часто на порядки большему, чем собственно операция. Высокой конкуренции он как раз очень-очень не любит — с ним надо обращаться весьма аккуратно, в частности, лочить очень короткие операции.
В частности, если лочить весь процесс генерации ПСЧ, от взятия текущего сида до его обновления, то это ограничит производительность rand() максимум одним ядром минус оверхед (ок, пусть даже десятки процентов). Но я не представляю себе ситуации, где может потребоваться большая производительность для rand(), так что сделать его thread-safe все-таки стоило бы из коробки )
Согласен, что дискуссию можно завершать, ведь генерация ПСЧ действительно происходит быстро и не должна включать в себя переключение контекста, да и изначально мой месседж состоял в том что инструментарий для программисто надо готовить тщательно, а не так чтобы его потом ещё напильником надо было дорабатывать.
Тем не менее, есть один момент касательно
Spinlock вам ничем не поможет. Его взятие будет ещё дороже чем Monitor.Enter/Exit
Смотрим http://www.albahari.com/threading/part5.aspx#_SpinLock_and_SpinWait:
SpinLock and SpinWait are structs and not classes! This design decision was an extreme optimization technique to avoid the cost of indirection and garbage collection.
The SpinLock struct lets you lock without incurring the cost of a context switch, at the expense of keeping a thread spinning (uselessly busy).
Я уже упоминал постом выше про свойства спинлока — это самый оптимизированный способ залочить очень короткую операцию, по сравнению с которой любые другие способы блокировки приведут к оверхеду, часто на порядки большему, чем собственно операция. Высокой конкуренции он как раз очень-очень не любит — с ним надо обращаться весьма аккуратно, в частности, лочить очень короткие операции.
В частности, если лочить весь процесс генерации ПСЧ, от взятия текущего сида до его обновления, то это ограничит производительность rand() максимум одним ядром минус оверхед (ок, пусть даже десятки процентов). Но я не представляю себе ситуации, где может потребоваться большая производительность для rand(), так что сделать его thread-safe все-таки стоило бы из коробки )
Вот правильная удобная реализация: random.seed([x])
Вот эта программа будет всегда генерировать случайное число на основании таймера при запуске:
интепретатор в первой команде (импорт модуля) сам сделал srand, выполнив его обёртку random.seed() c аргументом «текущее время» или даже /dev/random в Linux и CryptGenRandom в Windows, т.е. реально настоящее случайное.
А вот эта программа будет выдавать одно и то же значение:
интепретатор сделал srand, но мы потом сделали ещё один, уже сознательно, зная, что хотим повторения последовательности.
Подход .Net в данном случае — плохой, он заставляет изобретать велосипед каждого, кто захочет генерировать случайные числа. Не факт, что программист на C# с ходу напишет такую же продвинутую логику, какую сделали разработчики Python в библиотеке random — скорее наоборот, он пока дойдёт до такой логики перелопатит кучу документации и всё равно где-нибудь допустит оплошность. Подход Python позволяет гораздо быстрее и дешевле получить как минимум тот же, а в большинстве случаев более качественный результат.
Initialize the basic random number generator. Optional argument x can be any hashable object. If x is omitted or None, current system time is used; current system time is also used to initialize the generator when the module is first imported. If randomness sources are provided by the operating system, they are used instead of the system time (see the os.urandom() function for details on availability).
Вот эта программа будет всегда генерировать случайное число на основании таймера при запуске:
import random
print(random.random())
интепретатор в первой команде (импорт модуля) сам сделал srand, выполнив его обёртку random.seed() c аргументом «текущее время» или даже /dev/random в Linux и CryptGenRandom в Windows, т.е. реально настоящее случайное.
А вот эта программа будет выдавать одно и то же значение:
import random
random.seed(1)
print(random.random())
интепретатор сделал srand, но мы потом сделали ещё один, уже сознательно, зная, что хотим повторения последовательности.
Подход .Net в данном случае — плохой, он заставляет изобретать велосипед каждого, кто захочет генерировать случайные числа. Не факт, что программист на C# с ходу напишет такую же продвинутую логику, какую сделали разработчики Python в библиотеке random — скорее наоборот, он пока дойдёт до такой логики перелопатит кучу документации и всё равно где-нибудь допустит оплошность. Подход Python позволяет гораздо быстрее и дешевле получить как минимум тот же, а в большинстве случаев более качественный результат.
Насколько я помню из школьного курса информатики — есть ровно два способа получить не псевдослучайное число. Один из них связан с радиоактивным распадом, а второй — с кипением какого-то масла в большом-большом чане. Во втором случае якобы измеряют координаты пузырей растворённого газа и их объём. Хоть я иногда и думаю, что с чаном информатик над нами пошутил.
Если мы говорим о *действительно* случайных числах — то только квантовые аппаратные генераторы, там жестко подперто, что за рандомность отвечает вселенная в лице квантовой механики.
На практике такая пунктуальность не особенно важна, поэтому используются разнообразные шумы из драйверов, типа младшего бита на линейном входе аудиокарточки.
На практике такая пунктуальность не особенно важна, поэтому используются разнообразные шумы из драйверов, типа младшего бита на линейном входе аудиокарточки.
Есть такая штука — Гиперион, спутник планеты Сатурн. Его центр масс движется вокруг Сатурна по нормальной эллиптической орбите с предсказуемыми возмущениями от других небесных тел, но вот сам спутник при этом хаотически кувыркается. Его положение в пространстве невозможно предсказать на сколь-нибудь длинный (по астрономическим меркам) промежуток времени, в отличие от положения собственно на орбите, которое предсказывается очень точно надолго. Это такой, знаете ли, совершенно неквантовый генератор случайных чисел.
На Земле таких же примеров полно. Например, можно подобрать такой поток воды, капающей из крана, чтобы попасть в режим динамического хаоса — интервалы между каплями будут совершенно случайными. То же самое, никаким способом вы не предскажете, каким будет следующий интервал.
А ещё турбулентность, кипение жидкостей и тому подобное.
На Земле таких же примеров полно. Например, можно подобрать такой поток воды, капающей из крана, чтобы попасть в режим динамического хаоса — интервалы между каплями будут совершенно случайными. То же самое, никаким способом вы не предскажете, каким будет следующий интервал.
А ещё турбулентность, кипение жидкостей и тому подобное.
Вы не очень удачный пример подобрали, хотя и интересный.
Любая неквантовая система эволюционирует по собственному закону, которое можно выразить некоторым дифф. уравнением. На малых временных масштабах дифф. уравнение решается точно, если дано точное исходное состояние. Стало быть всё, всякий ГСЧ на таких системах будет опирать только на то, что исходное состояние нам не известно. Для хаотических систем это работает, хотя опять же на малых масштабах по времени будет наблюдаться детерменизм.
Вы правильно сказали: «Его положение в пространстве невозможно предсказать на сколь-нибудь длинный (по астрономическим меркам) промежуток времени».
Однако даже системное время в мс (или даже просто в секундах) можно использовать для генерации СЧ в небольшом диапазоне, если это требуется, скажем, раз в сутки/неделю/месяц. Опять же, это вопрос о масштабах, в нашем мире нет ни одной полностью детерминированной системы.
Автор статьи же ставит вопрос о том, что делать, если генерировать нужно много и сразу. Можно ли использовать предложенные Вами методы для генерации 100500+ СЧ в ед. времени? Не получится.
Квантовые генераторы — это другой уровень. При измерении физ. величины состояние коллапсирует в собственное состояние физ. величины вероятностно, притом эти вероятности определяются квадратом модуля коэффициентов разложения состояния по базису из собственных состояний физ. величины.
Случайность является истинной, неподдельной, поэтому всё как бы хорошо. Но там могут возникнуть проблемы, связанные с эволюцией состояния во времени: нестационарное состояние будет меняться во времени детерминированным образом вплоть до следующего измерения, однако может понадобиться некоторое время для того, чтоб отойти от собственного состояний физ.величины, которое было получено при предыдущем измерении.
Но эти порядки совершенно другие, нам столько информации сразу не нужно.
Любая неквантовая система эволюционирует по собственному закону, которое можно выразить некоторым дифф. уравнением. На малых временных масштабах дифф. уравнение решается точно, если дано точное исходное состояние. Стало быть всё, всякий ГСЧ на таких системах будет опирать только на то, что исходное состояние нам не известно. Для хаотических систем это работает, хотя опять же на малых масштабах по времени будет наблюдаться детерменизм.
Вы правильно сказали: «Его положение в пространстве невозможно предсказать на сколь-нибудь длинный (по астрономическим меркам) промежуток времени».
Однако даже системное время в мс (или даже просто в секундах) можно использовать для генерации СЧ в небольшом диапазоне, если это требуется, скажем, раз в сутки/неделю/месяц. Опять же, это вопрос о масштабах, в нашем мире нет ни одной полностью детерминированной системы.
Автор статьи же ставит вопрос о том, что делать, если генерировать нужно много и сразу. Можно ли использовать предложенные Вами методы для генерации 100500+ СЧ в ед. времени? Не получится.
Квантовые генераторы — это другой уровень. При измерении физ. величины состояние коллапсирует в собственное состояние физ. величины вероятностно, притом эти вероятности определяются квадратом модуля коэффициентов разложения состояния по базису из собственных состояний физ. величины.
Случайность является истинной, неподдельной, поэтому всё как бы хорошо. Но там могут возникнуть проблемы, связанные с эволюцией состояния во времени: нестационарное состояние будет меняться во времени детерминированным образом вплоть до следующего измерения, однако может понадобиться некоторое время для того, чтоб отойти от собственного состояний физ.величины, которое было получено при предыдущем измерении.
Но эти порядки совершенно другие, нам столько информации сразу не нужно.
Как дополнение к вышесказанному, использование Mersenne Twister во многих случаях дает более адекватный результат чем стандартный Random.
Большое спасибо!
Я, честно сказать, даже и не думал о том, что класс Random потоконебезопасен. Всегда хранил его в статическом поле. Теперь, видимо, не буду =)
Кстати, буквально сегодня столкнулся с вариантом получения случайных чисел, в котором использовался Random, а seed для него вычислялся не из времени, а через RNGCryptoServiceProvider.
Я, честно сказать, даже и не думал о том, что класс Random потоконебезопасен. Всегда хранил его в статическом поле. Теперь, видимо, не буду =)
Кстати, буквально сегодня столкнулся с вариантом получения случайных чисел, в котором использовался Random, а seed для него вычислялся не из времени, а через RNGCryptoServiceProvider.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Генерация случайных чисел в .NET