Комментарии 42
Испокон веков для подсчёта числа пи использовали иголку.
Элегантно и просто. Спасибо.
Единственное что -- вместо
круг с центром в начале координат едичного радиуса
привычнее читать "единичная окружность".
Если мне не изменяет память, этот метод называется "метод Монте-Карло" ?
Так и есть.
Википедия подсказывает, что это действительно так. Выше скидывали инфу как найти число пи с помощью иголки. Этот метод тоже из аналогичной группы численных методов для изучения случайных процессов.
Я удивился, что в статье его не назвали. Это имхо и есть ответ на вопрос из собеседования: "Надо применить метод Монте-Карло", дальше всё довольно очевидно.
Сомневаюсь, что кто-то не зная о нём, сможет прямо на собеседовании его придумать.
Плохо соображаю на ночь глядя, но в целях оптимизации подумалось - если взять вместо круга сферу, то вероятность от трехмерной точки будет Пи/6. И таким образом увеличится вызов генератора случайного числа на одну итерацию до трех. Можно ли пойти в обратном направлении и уменьшить его до одного?
Там надо не количество вызовов рандома оптимизировать, а сходимость у данного метода, которая достаточно паршивая и пропорциональна sqrt(n).
Вот что я нашел:
Пи = 2 * (Arcsin (SQRT (1 - х ^ 2))) + ABS (Arcsin (х))
Где x любое число от -1 до 1. Для задачи можно взять от 0 до 1. Один вызов случайного числа и ни каких итераций!
Хмм... Уровень статей на Хабре непрерывно падает... мы этот метод разбирали в кружке информатики, когда я был в 6 классе. Метод Монте-Карло называется, причём первая же ссылка в поисковике(у меня по крайней мере) — на статю на хабре https://habr.com/ru/post/128454
Ждём статей с программами вида «Звездное небо» и «вычисление факториала» %)))
причём первая же ссылка в поисковике(у меня по крайней мере) — на статю на хабре
которую справедливо заминусовали за бессодержательность и округления)
Да, 11 лет назад Хабр был более требователен к качеству материала.
Да, 11 лет назад Хабр был более требователен к качеству материала.
Такие высказывания встречаются нередко в комментах, типо: "статьи на Хабре раньше были лучше". Не соглашусь. Иногда в поисковике попадаются ссылки на статьи 10-летней давности и качество там "стыд 2010". Пример.
Не соглашусь. Иногда ..
Ключевое слово "иногда"
Да, иногда, но рандомно поманипулировал с url-Хабра рядом с 2010г., получаю низкосортные заметки, а не статьи технического уровня:
https://habr.com/ru/company/asus/blog/109641/
Какие либо торты я не встречал в прошлом.
А вы по какой логике их отбираете? Из 4 статей, только одна с рейтингом больше 20. И то в дисклеймере честно написано, что это комментарий выделенный в статью. Значит на тот момент на это был запрос, т.к. лицензии Creative Commons были не столь известны, как сейчас.
Вы сравнивайте как сообщество реагирует на схожие статьи, а надёргать из поисковика то, что и в ленты то в своё время не попадало, всегда можно.
P.S. А статьи из хабов "Блог компании X" вообще редко отличаются качеством, но они тут в качестве рекламы.
А вы по какой логике их отбираете?
рандомно поманипулировал с url-Хабра рядом с 2010г.
т.е. я даже не пытался выбрать что-то самое level уровня: 10 предложений.
от момент на это был запрос, т.к. лицензии Creative Commons
Там даже не постеснялись метку поставить "tutorial".
"Блог компании X" вообще редко отличаются качеством, но они тут в качестве рекламы.
Не хочу более спорить, но в некоторых корп.блогах пишут технически подкованные авторы, которые умеют и понимают (они также бы могли выдавать контент на высоком уровне и без рекламы, но их нашли и привлекли, контент не пострадал).
А вывод я озвучил в своём первом комментарии в этой ветке. Ищите качественный контент, не стоит ограничиваться Хабром. Браузер с переводчиком, поиск по сайту и Nature; Science или Гугловская Академия. Там не так всё скверно с материалом прошлой эпохи. И пожалуй близкий к Хабру сайт — Slashdot.
А почему бы и нет. Лет 15 назад столкнулся с тем, что отсутствует толковое решение для комбинаторного расчета. Надо было найти число сочетаний из n объектов по k, причем точно. EXEL2003 вообще иногда выдавал дробные числа.
С(7;1913)=18399302838933135756.
У статьи два тэга: Python и Математика. Это прекрасно.
Начнем с питона, перепишем авторское решение, сохранив его идею:
from random import random
def estimate_pi(n):
s = 0.
for _ in range(n):
x, y = random(), random()
if 1. >= x * x + y * y:
s += 4.
return s / nХм, в CPython 3.10 это работает в 3.5 раза быстрее. Как же так, дружище? Как же тэг Python?
Ладно, что там с математикой? Про сходимость тут уже высказались, хорошо бы немного практики, чтобы цифры пощупать. Считаем по-всякому площадь сектора OAC.
Я умею интегрировать трапециями!
from math import sqrt
def trapezoid_pi(n):
s = .5 # значения в крайних точках интервала
# берутся с весом 0.5, а значения эти - 1 и 0
x = step = 1. / n
for _ in range(n - 1):
s += sqrt(1. - x * x)
x += step
return s * 4. / nЯ могу интегрировать по Симпсону!
from math import fsum
def simpson_pi(n):
x, step, res = 0, 1. / n, [.5]
for _ in range(n):
x += step
res.append(sqrt(1. - x * x))
return (fsum(res[::2]) + fsum(res[1::2]) * 2.) * 8. / (n * 3)
Правда, это даёт выигрыш в точности против трапеции всего 2.5 раза. Всё из-за особенности в точке C - там касательная к окружности идёт отвесно. Так это можно обойти: отдельно посчитаем площадь сегмента AB и четырехугольника OABC.
from math import fsum, sqrt
def simpson45_pi(n):
x, step, res, s5 = 0., 1. / n, [.0], sqrt(.5)
for _ in range(n):
x += step
res.append(sqrt(1. - x * x * .5) - 1. + (1. - s5) * x)
AB = (fsum(res[::2]) + fsum(res[1::2]) * 2.) * s5 * 2. / (n * 3)
OABC = s5 # взял аналитически
return (OABC + AB * 2.) * 4.Да, а как же цифры? Вот они:
Абсолютная погрешность против библиотечного значения π для n = 2 ** 3 == 8
(разбиение интервала на степень двойки дает мне выигрыш в точности)
estimate_pi 0.47564011559266456 # усредненно по большой выборке
trapezoid_pi 0.05177350923261992
simpson_pi 0.02040348381437518
simpson45_pi 0.00003003695260295
Погрешность для n = 2 ** 13, мельчить сильнее вроде незачем
estimate_pi 0.01486375361227077 # усредненно
trapezoid_pi 0.00000158604010281
simpson_pi 0.00000061939277884
simpson45_pi 0.00000000000000000Ну что тут скажешь? Друзья, не суйте Монте-Карло куда попало.
А можно еще и с NumPy, но уж это как-нибудь в другой раз.
А где генератор случайного числа? С таким же успехом можно арксинус от единицы на два умножить.
Ну раз питон-питон, то тогда так :)
def estimate_pi(n: int) -> float:
return sum(4
for _ in range(n)
if (x := random()) * x + (y := random()) * y < 1) / n
Львиную долю ускорения в вашем варианте дает замена random.uniform на random.random, из вызова которого первый, собственно, и состоит, убирая лишний вызов функции. На втором месте замена возведения в степень на умножение, эффект от которой не столь впечатляющий, но хорошо заметный.
Не могли бы вы пояснить смысл остальных оптимизаций, в частности, замены int на float и инкремента на 4 вместо 1 в счетчике?
Питоновский int произвольной длины инкрементируется програмно, а нативный для процессора float - аппаратно, одним процессорным опкодом за один процессорный такт. Хотя здесь фактические вычисления ведутся с малыми числами и, по факту, короткой арифметикой, предварительно производится уточнение, что и в каком виде хранится в переменной.
В python2 было два целочисленных типа - короткий, размером в машинное слово, и длинный, в python3 их заменили одним int - ввиду того, что серьёзную арифметику стали считать в NumPy, а в эпизодической проигрыш в быстродействии не критичен.
4 вместо 1 - не оптимизация, так, для красоты.
Вы еще упускаете импорт конкретной функции вместо модуля, её содержащего - вычисление атрибута random.random в цикле тоже чего-то стоит. Смотрите сюда:
import random
from random import random as rnd
from dis import dis
def f(): return random.random()
def g(): return rnd()
dis(f)
print("-------------")
dis(g)
Я вижу по коду, что на самом деле разрешается не только RNG, но и сложения, умножения, возведения в степень. Не проще ли тогда сразу взять и вычислить ряд, например, а на RNG забить? Так и быстрее, и точнее.
Кстати задача довольно интересная... Для проверки качества функции псевдослучайных чисел.
Когда я запускал такую программку почти 40 лет назад на агате, точность оказалась так себе...
Например у нас есть кубик. Какая вероятность что выпадет грань с четными значениями? 1/2
Набор всех исходов 6
А вот и нет, решение неверное. В задаче называется "кубик", у кубика есть не только грани (6), но и рёбра (12) и их вершины (8). И какова же вероятность, что кубик выпадет не на чёт.числе/грани, а на вершине или ребре? явно не 1/2, более того кубик на практике реально иногда встает не на грань.
На отрезок
.
на отрезке бесконечно много точек
Тоже не верно, отрезок конечный и точек у него также конечное число, зависит от шага.
И какова же вероятность, что кубик выпадет не на чёт.числе/грани, а на вершине или ребре?
Ноль. С математическими абстракциями вы не знакомы, похоже...
Тоже не верно, отрезок конечный
...как и с теорией множеств и определениями конечного множества и отрезка...
Ноль. С математическими абстракциями вы не знакомы, похоже...
Извините не удержался, какой же это стыд интерпретировать беспомощно статистику в свою сторону, прикрываясь математическими абстракциями и не приведя даже хоть какого решения, подогнав свой ответ под 0. В некоторых уравнениях Максвелла присутствует абстракция, чтобы их можно было решить. Какая у кубика абстракция с перечисленными в комментарии исходами? Ноль? Перечитайте, что вы написали и ужаснитесь.
Эм... где я что под что подгоняю? В подобных задачах с кубиком в статистике всегда подразумевается идеальный абстрактный кубик (если не оговорено иного), который падает исключительно на одну из своих граней, и на вершину или ребро упасть не может в принципе - таких событий в пространстве вероятных исходов просто нет и достичь такого исхода невозможно. Вероятность невозможного события - ноль. Чему я должен ужасаться? Тому, что вы пытаетесь в известной задаче с абстрактным кубиком притянуть за уши кубик реальный или же какой-то особый кубик, выдуманный лично вами, по каким-то бредовым соображениям? Ну да, этому стоит ужасаться...
Вот пример задачи из курса на Python, которая просто абсурдная, потому что её верное решение — абстрактное, т.е. в реальности такой исход — не существует. А теперь задумайтесь, если бы эти или подобные данные были бы жизненно важны и на них опирались бы в дальнейшем, или подумайте о принятых законах, у которых внезапно двойное толкование.
Hidden text
1 строка - расстояние, 2 и 3 - скорости старушек.
Решение: t = s / v1+v2. Проблема в том, что в реальном мире ни одна старушка не может идти со скоростью 60,75км/ч. Но в задаче утверждается, что старушки именно идут, а не едут и они очень быстрые. Это работает лишь в теории (абстракция), но в природе такого не бывает: Error.
По кубику, у вас он всегда абстрактный — это проблема. Рекомендую ознакомиться с произведением, которое я выше упомянул.
или подумайте о принятых законах, у которых внезапно двойное толкование.
Че о них думать, люди всю жизнь этим занимаются, а как только правительство обнаруживает что появилось второе толкование, в закон вносят поправки.
которая просто абсурдная, потому что её верное решение — абстрактное, т.е. в реальности такой исход — не существует.
Должен ли я из этого сделать вывод, что любая постановка задачи с входными данными скорости - абсурдна, потому что скорость любого тела выше скорости света (или какого либо другого лимита) невозможна?
Зумеры изобрели метод стат. анализа (Монте-Карло)?
P=lambda n:sum([(1-(1/n/2+i/n)**2)**.5/n for i in range(0,n)])*4
P(1_000_000)
Метод Монте-Карло именно на примере числа пи описан в школьном учебнике информатике (Кушниренко и другие) издательство 1989 года. Этому детей учили
Но не все дети, видать, учились)
У меня метод монте карло ни в школе не проходили (13 классов гимназии в Германии), ни в институте по статистике при обучении на бакалавра по психологии (статистика была как предмет из блока методологии в первых двух семестрах по 4 академических часа в неделю в каждом).
Статья довольно баянистая, хотя мне данная иллюстрация нравится) мне кажется стоило добавить оценку погрешности , обычно такое рассматривается в численных методах
Всё проще.
print(random(0,0))
Выводит число pi с точностью до pi.
Метод Монте-Карло
Ищем значение числа Пи, используя генератор случайных значений