С удивлением обнаружил, что на русском языке трудно отыскать информацию по данной проблеме, как будто мало кого волнует, что математические библиотеки, используемые в современных компиляторах, иногда не дают корректно-округлённого результата. Меня эта ситуация волнует, так как я как раз занимаюсь разработкой таких математических библиотек. В иностранной литературе эта проблема освещена хорошо, вот я и решил в научно-популярной форме изложить её на русском языке, опираясь на западные источники и пока ещё небольшой личный опыт.
Читать полностью »
Рубрика «Алгоритмы» - 30
Table-Maker’s Dilemma, или почему почти все трансцендентные элементарные функции округляются неправильно
2020-09-21 в 8:32, admin, рубрики: Алгоритмы, вычисления, математика, округлениеКвантовый хакинг, вычисления, алгоритмы и машинное обучение на практике — дайджест Университета ИТМО
2020-09-20 в 7:33, admin, рубрики: Алгоритмы, Блог компании Университет ИТМО, вычисления, квантовые технологии, квантовый хакинг, машинное обучение, Университет ИТМО, учебный процесс, Учебный процесс в ITЭто подборка текстовых материалов и тематических подкастов с участием представителей Университета ИТМО — студентов, аспирантов, научных сотрудников и преподавателей. Мы обсуждаем научные статьи, делимся личным опытом разработки проектов различного уровня и говорим о возможностях для развития, которыми располагает «первый неклассический».
Immutable Trie: найди то, не знаю что, но быстро, и не мусори
2020-09-20 в 6:45, admin, рубрики: javascript, postgresql, trie, Алгоритмы, Блог компании Тензор, префиксное дерево, Программирование, структуры данныхПро префиксное дерево (Trie) написано немало, в том числе и на Хабре. Вот пример, как оно может выглядеть:

И даже реализаций в коде, в том числе на JavaScript, для него существует немало — от «каноничной» by John Resig и разных оптимизированных версий до серии модулей в NPM.
Зачем же нам понадобилось использовать его для сервиса по сбору и анализу планов PostgreSQL, да еще и «велосипедить» какую-то новую реализацию?..
Читать полностью »
SQL HowTo: курсорный пейджинг с неподходящей сортировкой
2020-09-05 в 17:45, admin, рубрики: limit, postgresql, sql, sql tips and tricks, union, Алгоритмы, Блог компании Тензор, ненормальное программированиеЭтот пост родился как расширенный ответ на умозрительную задачу, обозначенную в статье «Хроники пэйджинга».
Пусть у нас есть реестр документов, с которым работают операторы или бухгалтеры в СБИС, вроде такого:
Традиционно, при подобном отображении используется или прямая (новые снизу) или обратная (новые сверху) сортировка по дате и порядковому идентификатору, назначаемому при создании документа — ORDER BY dt, id
или ORDER BY dt DESC, id DESC
.
Типичные возникающие при этом проблемы я уже рассматривал в статье «PostgreSQL Antipatterns: навигация по реестру». Но что если пользователю зачем-то захотелось «нетипичного» — например, отсортировать одно поле «так», а другое «этак» — ORDER BY dt, id DESC
? Но второй индекс мы создавать не хотим — ведь это замедление вставки и лишний объем в базе.
Можно ли решить эту задачу, эффективно используя только индекс (dt, id)
?
Читать полностью »
Определяем пульс по вебкамере в 50 строчек кода
2020-09-01 в 17:47, admin, рубрики: python, Алгоритмы, Лайфхаки для гиков, Научно-популярное, Программирование, пульсометрПривет.
Однажды мне попалось описание приложения для Android, которое определяло пульс по камере телефона, просто по общей картинке. Камера не прикладывалась к пальцу, не просвечивалась светодиодом. Интересный момент был в том, что ревьюеры не поверили в возможность такого определения пульса, и приложение было отклонено. Чем дело кончилось у автора программы, не знаю, но стало интересно проверить, возможно ли это.
Для тех кому интересно что получилось, продолжение под катом.
Разумеется, я не буду делать приложение под Android, гораздо проще проверить идею на языке Python.
Получаем данные с камеры
Циркулярные кривые 2-го порядка
2020-09-01 в 16:11, admin, рубрики: wolfram mathematica, Алгоритмы, безье, интерполяция, комплексные числа, кривые, математика, сплайныКак известно, кривыми Безье нельзя построить дугу окружности или эллипса. В этой статье рассматриваются кривые, лишённые такого недостатка.

Ронго-ронго: нерасшифрованная письменность острова Пасхи
2020-08-30 в 21:12, admin, рубрики: natural language processing, Алгоритмы, дешифровка, Занимательные задачки, криптография, Научно-популярное, омофоническая замена, остров Пасхи, письменность, ронго-ронго, ронгоронго, шифрИзобретатели
Письменность — один из столпов, на которых стоит современная цивилизация. Хотя мы и воспринимаем её как естественную часть нашей повседневной жизни, когда-то она была изобретена. Такое случалось всего несколько раз, в статье речь пойдет как раз про один из таких случаев — письменность острова Пасхи, также называемого Рапа Нуи. Это маленький уединенный остров длиной 24 километра, до ближайшего населенного острова плыть от него 1600 километров по прямой. Полинезийские мореходы попали туда примерно в 1200 году, а европейцам он стал известен в 1722. Европейцев впечатлили сотни каменных статуй, созданных островитянами, до 10 метров высотой и до 80 тонн веса каждая. Этим Рапа Нуи отличался ото всех прочих полинезийских островов, на которых если и делали каменные статуи, то весьма скромных размеров. Несмотря на это, европейцы обращались с местным населением как с дикарями: ловили их и продавали в рабство, захватили их землю, превратили весь остров в пастбище и, наконец, выживших обратили в христианство, запрещав говорить на родном языке и воспроизводить местную культуру.
Открытие
В 1864 году миссионер Эйро сделал удивительной открытие: чуть ли не в каждой хижине хранились небольшие дощечки, покрытые мелкой резьбой, которые как будто бы можно было читать до того, пока все грамотные островитяне не умерли в рабстве. Мы точно не знаем, что именно произошло, по-видимому, Эйро объявил таблички запретными, препятствующими попаданию в рай и призвал их сжигать. Помимо христианства Эйро привез на остров туберкулёз, эпидемия которого за несколько лет выкосила четверть населения. После его смерти в 1868 другой священник, пришедший на смену Эйро, всё же решил рассказать о табличках начальству. Епископ Жоссан на Таити тут же понял, каково значение находки, но к тому моменту осталось всего две дюжины артефактов с надписями. Так мир узнал про ронго-ронго — письменность острова Пасхи.
Читать полностью »
Интерактивная визуализация алгоритмов на базе Jupyter
2020-08-29 в 16:32, admin, рубрики: jupyter, python, Алгоритмы, визуализация, визуализация данныхJupyter уже давно зарекомендовал себя как удобную платформу для работы в различных областях на стыке программирования, анализа данных, машинного обучения, математики и других. Вот например очень известная книга по анализу данных, состоящая из Jupyter блокнотов. Поддержка , markdown, html дает возможность использовать использовать Jupyter в качестве платформы для удобного оформления научного-технического материала. Преимущество таких блокнотов заключается в интерактивности, возможности сопровождать сухой материал примерами программ, при этом эта интерактивность очень естественна и проста в использовании. В этой статье хотелось бы рассказать про возможность создания в Jupyter анимированных примеров работы различных алгоритмов и привести несколько из них с исходным кодом. В качестве кликбейта алгоритм Дейкстры.
Поиски фундаментальных данных для акций через API Financial Modeling Prep
2020-08-24 в 1:25, admin, рубрики: api, javascript, node.js, Алгоритмы, биржа, биржевая торговля, инвестиции, котировка, облигации, парсинг, статистика, финансы в IT, ценные бумагиНедавно мне понадобилось обработать экономические показатели для нескольких тысяч американских акций.
Их невозможно было получить через привычный скринер бумаг вроде яху финанс, потому что методика расчёта нестандартная.
В качестве поставщика данных использовался сервис FinancialModelingPrep, который в 2019 году был бесплатен, но в 2020 году уже нет.
В статье разбираюсь в нюансах формирования запросов к базе данных сервиса. А ещё исследую глубину доступных финансовых отчетов компаний за прошлые годы.
Читать полностью »
Как я html-парсер на php писал, и что из этого вышло. Заключительная часть
2020-08-15 в 15:02, admin, рубрики: html, html5, php, Алгоритмы, синтаксический анализаторЗдравствуйте.
Представляю вам заключительную главу цикла. В ней пойдет речь о реализации самого парсера, его модулей, вроде функции анализа, построения стека и dom дерева. Помимо этого поговорим и об обработке комментариев. Как оказалось, комментарии могут обрабатываться по разному.
Напишем свой поиск элементов, подробнее поговорим о поиске по классам и идентификаторам. И многое другое!
Читать полностью »