На изображении, как я понял, аккреционный диск черной дыры в центре галактики M87. Из википедии узнаю, что диаметр этого диска — 0.39 световых лет (это одна из самых больших известных черных дыр), расстояние — 53 млн. световых лет.
Я понимаю, что это много телескопов, которые работают как один большой радио-телескоп размером с Землю, но для понимания масштабов, давайте представим, если бы у нас был оптический телескоп с таким разрешением.
МКС летает на высоте 400км. Тогда такой угловой диаметр соответствует размеру
400 000 * 0.39 / (53 * 10^6) м = 0.0029 м То есть мы бы разглядели форму родинки астронавта МКС?
Или я напутал в расчетах?
Хотелось бы посмотреть последние четыре графика с более точной детализацией, как у синих вначале. Такое ощущение, что значение списка years осталось урезанным после построения бар чартов.
Мне в RabbitMQ всегда казалось странным, что продюсеры и консьюмеры должны декларировать exchange, при этом указывая ее тип. То есть если мы внедряем мониторинг и меняем тип на fanout, то мы должны сделать исправления во всех консьюмерах и продюсерах, когда они декларируют эту exchange. Хотя они не должны знать, как она работает внутри. Это не критика вашей статьи, просто вещь, которая мне кажется странной.
Ну да, в этом и идея статьи: если нам надо найти значения полинома в подряд идущих равноудаленных точках, зная значения в первых нескольких, то можно использовать не стандартные методы интерполяции, а гораздо более простую формулу. Получается trade-off: мы нашли более простую, но менее общую формулу.
Скажите, а есть ли стандартное решение для продвинутого кеширования в микросервисах? Проблема такая: в один момент времени может поступить множество одинаковых запросов от разных других микросервисов. Принимающий микросервис понимает, что они одинаковые, выполняет только один запрос и возвращает его результат (через REST) всем тем, кто его запросил. Плюс хранит его некоторое время.
Обозначение 1. Введем разностный оператор Δ. Он принимает на вход полином f и возвращает полином Δ(f) такой, что выполняется (Δ(f))(x) = f(x + 1) — f(x).
Лемма 1. Если f имеет степень n, то Δf имеет степень n — 1, если f имеет степень 0 (константа), то Δf = 0.
Обозначение 2. Обозначим Δ^k (f) = Δ(Δ(...Δ(f)...)) — k-кратное применение Δ.
Следствие 1. Если f имеет степень n, то Δ^k (f) имеет степень n — k, в частности Δ^(n+1) (f) равен 0.
Лемма 2. Δ^(n+1) (f) = вашей формуле, но внутри суммы k пробегает диапазон от 0 до n + 1 (у вас k=1..n+1).
В итоге получаем, что 0 = Δ^(n+1) (f) = ваша формула без первого члена, равного f(x)
Следовательно, f(x) = ваша формула
Для обобщения вашей формулы на произвольный шаг воспользуемся следующим утверждением:
Лемма 3. Пусть мы доказали, что для любого полинома степени n выполняется некоторое соотношение на f(1), ..., f(k). Тогда для любого полинома степени n выполняется точно такое же соотношение, но на значения аргумента из любой арифметической прогрессии длины k.
Доказательство. Допустим, мы хотим доказать соотношение для последовательности a, a + b, a + 2b,… Рассмотрим линейную функцию h(x) = a + bx. Обозначим g — полином, являющийся композицией f и h, то есть для которого выполняется g(x) = f(h(x)). Заметим, что g имеет степень n, а следовательно мы можем заключить, что для g(1), ..., g(k) выполняется то самое соотношение.
Так как g(i) = f(a + bi), мы получаем, что соотношение выполняется для f(a), f(a + b),… f(a+kb), что и требовалось доказать.
Относительно использования этой формулы для доказательства того, что полиномы степени n определяются значениями в n + 1 различных точках, есть некоторая проблема:
Обычное доказательство следующее. Предположим противное и нашлись два полинома f и g степени n, которые совпадают в n + 1 точке. Тогда рассмотрим их разность — это тоже полином степени не больше n, у которого n + 1 корень. Но согласно следствию из основной теоремы алгебры ненулевой полином степени n может иметь не более n корней. Следовательно разность f и g тождественно равна 0 и они совпадают. Получаем, что полином степени n однозначно определяется значениями в n+1 точке.
То есть это утверждение сводится к основной теоремы алгебры, которая в свою очередь доказывается жестким комплексным анализом.
Проблема в том, что вся теория манипуляций с полиномами, которая применялась мною выше, основана на фундаментальном соответствии между функциями и наборами коэффициентов. А для этого соответствия необходимо доказать, что не бывает полиномов с разными коэффициентами и одинаковыми значениями, что сводится к основной теореме алгебры.
В итоге то доказательство вашей формулы, что я привел, скорее всего где-то внутри себя уже опирается на факт о том, что полином степени n однозначно определяется значениями в n + 1 точке.
Ваш комментарий заставил меня задуматься. Это правда, что любые две не связанные величины, которые изменяются во времени строго линейно, будут иметь полную корреляцию?
Для тех, кто не любит R: ggplot2 есть такоже для python: ggplot.yhathq.com
С анимацией графиков в python хуже, можно покадрово сохранить графики в png файлы и склеить при помощи ffmpeg.
Просто в начале статьи рекламируются курсы по python, а в статье R, можно было бы немного адаптировать код. Я понимаю, что это перевод, но все же.
Спасибо за статью, думаю многие знают эту формулу для линейной функции, у нас на численных методах всплывало соотношение для второй степени. Но лично я как-то не задумывался о том, что линейное соотношение существует для полиномов произвольной степени и произвольным шагом, при этом коэффициенты не зависят от длины шага.
Очевидно, что это соотношение должно быть хорошо известно, но загуглить его было непросто. Мне кажется, ближе всего написано в разделе «Polynomial sequences» статьи в английской википедии en.wikipedia.org/wiki/Constant-recursive_sequence. Там сама общая формула не указана, но проговорено, что коэффициенты берутся из биномиального преобразования значений полинома в подряд идущих точках, что в точности совпадает с формулой автора статьи.
Скажите пожалуйста, как была выведена общая формула? Потому что в приложенном файле есть подробные выкладки для 1 и 2 степени, а потом просто приводится общая формула для n-ной степени.
Когда формула известна, доказать ее — дело техники. Во-первых приведенная формула очень похожа на развернутую формулу конечной разности (n+1)-ой степени, только первый член перенесен в левую часть. Во-вторых, ключевая идея состоит в том, что конечная разность (n+1)-ой степени всегда равна нулю для полинома n-ной степени (по аналогии с (n+1)-ой производной полинома n-ной степени, которая всегда 0). Собственно, вот и все доказательство.
Относительно произвольной длины шага: если мы доказали некоторое соотношение на значения произвольных полиномов с шагом 1, то оно же будет верно с любым другим шагом. Это тривиальное следствие, но, опять же, оно очевидно только после того, как было сформулировано, спасибо автору за это.
Практическое применение этой формулы довольно узкое. Я представляю себе такой сценарий: мы рисуем график, который изображает количество пользователей в реальном времени каждый час и хотим быстро экстраполировать это число на следующий час. Обычно я явно реализую что-то типа полинома Лагранжа, что занимает десяток строк. А так можно вставить вашу формулу для второй степени в одну строчку.
Про численную устойчивость у меня большие сомнения. Мне кажется, ошибка при однократном возведении в степень гораздо меньше, чем при повторении линейной рекуррентной формулы миллиарды раз. Я проверил на python (к сожалению я не изучал внимательно Ваш репозиторий, мог что-то упустить) для случая линейной функции: если мы вычисляем 10^8 подряд идущих значений типа double, то по вашей формуле ошибка составит -0.03:
def f(x):
return x / 3 + 1 / 7
vals = {0: f(0), 1: f(1)}
for t in range(2, 10 ** 8):
vals[t] = 2 * vals[t - 1] - vals[t - 2]
vals[t] - f(t) == -0.03673642501235008
# "стандартный" способ интерполирования линейной функции
vals[0] + (vals[1] - vals[0]) * t == f(t)
Конечно, никто не заставляет нас применять эту формулу миллиарды раз, если это делать тысячу раз, погрешность пренебрежительно малая. К тому же у меня «игрушечный» пример для линейной функции, может быть при возведении в большую степень действительно будет большая ошибка при обычных методах интерполирования. Нужно аккуратно это изучить. К тому же в приложенном документе уже присутствуют функции ε во всех рассчетах.
Резюмируя: автор обратил внимание на занимательный факт из теории конечных разностей, который позволяет в одну строчку интерполировать значение полинома в следущией точке сетки по предыдущим значениям. Такая потребность возникает не очень часто, но для общего математического развития полезно.
То, о чем говорит автор, следует из короткой формы интерполяционной формулы Ньютона, но не тривиальным образом. Формула автора проще: она содержит один биномиальный коэффициент, а в короткой форме Ньютона двойное суммирование с произведением биномиальных коэффициентов. Упрощение получается подставлением x = n + 1 и схлопыванием знакомеременной суммы произведений биномиальных коэффициентов.
Это получился торрент-клиент. Когда я устроился уже на работу, я с огромным наслаждением удалил его с гитхаба. Спустя год после написания мне уже было стыдно смотреть на его код.
Сурово! Не ожидал, что BitTorrent клиент на плюсах подходит в качестве пет-проекта, с учетом того, что BitTorrent Inc. с 2001 до 2008 года вела разработку основного клиента на питоне.
Если речь идет об этой реализации правила 110, то она требует действий пользователя: постоянного нажатия Tab + space (сначала нужно накликать желаемое начальное состояние в первой строке, потом следовать инструкции). С таким же успехом Тьюринг-полными можно назвать комментарии на Хабре и камни на берегу моря. Мне кажется, это не совсем честная Тьюринг-полнота, т.к. требует активного участия человека в вычислениях, по крайней мере для меня как любителя портировать трехмерные движки на все подряд.
Я первые два курса на факультете компьютерных наук ВШЭ тоже записывал в Emacs + LaTeX большинство лекций: t-arxiv.appspot.com. Даже сложилась традиция: в каждом поколении первокурсников находится человек, который решает ТеХать конспекты. При этом иллюстрации, оформление и объем обычно лучше, чем у предыдущего поколения.
Мне кажется, в использовании площади для сравнения нет ничего предосудительного, особенно как дополнительный источник информации, например, в диаграммах рассеяния, графах, иерархических диаграммах. Нужно только в легенде подписать, что радиус узла пропорционален площади.
В данном случае у них в презентации и так много столбчатных диаграмм и гистограмм, они решили «развлечь» читателя сравнением площадей. Спасибо, что хоть не круговой диаграммой.
Согласен, на вопрос «во сколько раз» сравнением площадей ответить трудно. Но и бар чарт разницу в 20 раз тоже не покажет интуитивно. Но в заголовке уже было написано про 95% и читатель как бы должен догадаться, что в 20 раз. Наверное, лучше всего было написать про 20 раз текстом.
Формула W3C для контрастности довольно сложная, тем не менее, насколько я понимаю, она не учитывает эффект Гельмгольца-Кольрауша. Парадокс этого эффекта состоит в том, что если вы светите белым фонарем на сцену, а затем добавляете красный фильтр, то субъективно сцена становится ярче, хотя вы уменьшили число фотонов.
Этот эффект еще не до конца изучен, известно, что он зависит от цвета окружения и, возможно, по-разному воспринимается разными людьми. При этом им нельзя пренебрегать т.к. разница между рассчитанной яркостью и субъективной составляет десятки процентов. В связи с этим, мне кажется, все автоматически сгенерированные палитры и рассчеты контрастности нужно корректировать вручную и больше доверять своим глазам.
Проблема подхода реализации компьютеров в духе Wang tiles «в лоб» на ДНК в том, что при таких вычислениях часто возникают ошибки. В этой статье указана частота 1 ошибка на 3000 плиток (я мог что-то напутать т.к. читал только abstract по диагонали). С учетом того, что число используемых плиток для самых простых алгоритмов пропорционально размеру входа в битах, умноженному на «число тактов» работы алгоритма, т.е. >100 – это довольно часто.
Вот картинка из одной из первых статей на эту тему от этих же авторов, где делали треугольник Серпинского
Если увеличить правильный кусок, то складывается впечатление, что все работает идеально, однако вокруг происходит хаос из-за этих самых ошибок
Теперь представьте, что вы реализовали на них алгоритм, который работает с бинарными данными и некоторые биты в процессе вычислений произвольно инвертируются. Алгоритмов, которые устойчивы к таким ошибкам крайне мало.
Тем не менее, эти проблемы решаемы и я как раз недавно читал ряд интересных статей от этих авторов.
Между тем observablehq.com вышел из беты. У него большая часть тоже opensource, есть поддержка markdown, формул на MathJax, WebGL, WebVR, реактивное вычисление ячеек, также есть возможность совместной работы над одним документом. Единственное, его нельзя развернуть в своей локальной сети. Ну и не планируют поддерживать другие языки кроме JS.
Очень круто! Не могу понять, почему на Хабре хорошие статьи по визуализации данных так мало плюсуют?
По моему опыту, визуализации такого уровня требуют настолько кастомизированных алгоритмов, что в итоге d3 используется лишь как API для сериализации SVG (плюс несколько удобных функций типа импорта csv)
Получаем угловой диаметр: arcsin(0.39 / (53 * 10^6)) = 4 * 10^-7 градусов.
Я понимаю, что это много телескопов, которые работают как один большой радио-телескоп размером с Землю, но для понимания масштабов, давайте представим, если бы у нас был оптический телескоп с таким разрешением.
МКС летает на высоте 400км. Тогда такой угловой диаметр соответствует размеру
400 000 * 0.39 / (53 * 10^6) м = 0.0029 м
То есть мы бы разглядели форму родинки астронавта МКС?
Или я напутал в расчетах?
aio-pikaругается, если при объявлении уже существующей exchange тип не совпадает.yearsосталось урезанным после построения бар чартов.Для обобщения вашей формулы на произвольный шаг воспользуемся следующим утверждением:
Так как g(i) = f(a + bi), мы получаем, что соотношение выполняется для f(a), f(a + b),… f(a+kb), что и требовалось доказать.
Относительно использования этой формулы для доказательства того, что полиномы степени n определяются значениями в n + 1 различных точках, есть некоторая проблема:
С анимацией графиков в python хуже, можно покадрово сохранить графики в png файлы и склеить при помощи ffmpeg.
Просто в начале статьи рекламируются курсы по python, а в статье R, можно было бы немного адаптировать код. Я понимаю, что это перевод, но все же.
Очевидно, что это соотношение должно быть хорошо известно, но загуглить его было непросто. Мне кажется, ближе всего написано в разделе «Polynomial sequences» статьи в английской википедии en.wikipedia.org/wiki/Constant-recursive_sequence. Там сама общая формула не указана, но проговорено, что коэффициенты берутся из биномиального преобразования значений полинома в подряд идущих точках, что в точности совпадает с формулой автора статьи.
Скажите пожалуйста, как была выведена общая формула? Потому что в приложенном файле есть подробные выкладки для 1 и 2 степени, а потом просто приводится общая формула для n-ной степени.
Когда формула известна, доказать ее — дело техники. Во-первых приведенная формула очень похожа на развернутую формулу конечной разности (n+1)-ой степени, только первый член перенесен в левую часть. Во-вторых, ключевая идея состоит в том, что конечная разность (n+1)-ой степени всегда равна нулю для полинома n-ной степени (по аналогии с (n+1)-ой производной полинома n-ной степени, которая всегда 0). Собственно, вот и все доказательство.
Относительно произвольной длины шага: если мы доказали некоторое соотношение на значения произвольных полиномов с шагом 1, то оно же будет верно с любым другим шагом. Это тривиальное следствие, но, опять же, оно очевидно только после того, как было сформулировано, спасибо автору за это.
Практическое применение этой формулы довольно узкое. Я представляю себе такой сценарий: мы рисуем график, который изображает количество пользователей в реальном времени каждый час и хотим быстро экстраполировать это число на следующий час. Обычно я явно реализую что-то типа полинома Лагранжа, что занимает десяток строк. А так можно вставить вашу формулу для второй степени в одну строчку.
Про численную устойчивость у меня большие сомнения. Мне кажется, ошибка при однократном возведении в степень гораздо меньше, чем при повторении линейной рекуррентной формулы миллиарды раз. Я проверил на python (к сожалению я не изучал внимательно Ваш репозиторий, мог что-то упустить) для случая линейной функции: если мы вычисляем 10^8 подряд идущих значений типа double, то по вашей формуле ошибка составит -0.03:
Конечно, никто не заставляет нас применять эту формулу миллиарды раз, если это делать тысячу раз, погрешность пренебрежительно малая. К тому же у меня «игрушечный» пример для линейной функции, может быть при возведении в большую степень действительно будет большая ошибка при обычных методах интерполирования. Нужно аккуратно это изучить. К тому же в приложенном документе уже присутствуют функции ε во всех рассчетах.
Резюмируя: автор обратил внимание на занимательный факт из теории конечных разностей, который позволяет в одну строчку интерполировать значение полинома в следущией точке сетки по предыдущим значениям. Такая потребность возникает не очень часто, но для общего математического развития полезно.
Сурово! Не ожидал, что BitTorrent клиент на плюсах подходит в качестве пет-проекта, с учетом того, что BitTorrent Inc. с 2001 до 2008 года вела разработку основного клиента на питоне.
В данном случае у них в презентации и так много столбчатных диаграмм и гистограмм, они решили «развлечь» читателя сравнением площадей. Спасибо, что хоть не круговой диаграммой.
Согласен, на вопрос «во сколько раз» сравнением площадей ответить трудно. Но и бар чарт разницу в 20 раз тоже не покажет интуитивно. Но в заголовке уже было написано про 95% и читатель как бы должен догадаться, что в 20 раз. Наверное, лучше всего было написать про 20 раз текстом.
Этот эффект еще не до конца изучен, известно, что он зависит от цвета окружения и, возможно, по-разному воспринимается разными людьми. При этом им нельзя пренебрегать т.к. разница между рассчитанной яркостью и субъективной составляет десятки процентов. В связи с этим, мне кажется, все автоматически сгенерированные палитры и рассчеты контрастности нужно корректировать вручную и больше доверять своим глазам.
Теперь представьте, что вы реализовали на них алгоритм, который работает с бинарными данными и некоторые биты в процессе вычислений произвольно инвертируются. Алгоритмов, которые устойчивы к таким ошибкам крайне мало.
Тем не менее, эти проблемы решаемы и я как раз недавно читал ряд интересных статей от этих авторов.
По моему опыту, визуализации такого уровня требуют настолько кастомизированных алгоритмов, что в итоге d3 используется лишь как API для сериализации SVG (плюс несколько удобных функций типа импорта csv)