Начну с громкого заявления: я придумал способ найти точку пересечения двух отрезков, заданных координатами концов. Придумал давно, лет 7 назад, в 2017 году, примерно, да, путь к этой публикации был долог, в основном из-за лени.
И да, я его придумал потому что не смог нагуглить, может он где-то и без меня описан был, может за эти 7 лет кто-то написал что-то похожее, а может я придумал какую-то фигню, которую умные люди изобретать не станут...
Привет, друзья!
В этой серии статей мы разбираем структуры данных и алгоритмы, представленные в этом замечательном репозитории. Это пятая часть серии.
Сегодня мы рассмотрим систему непересекающихся множеств, фильтр Блума и кэш актуальных данных.
Код, представленный в этой и других статьях серии, можно найти в этом репозитории.
Интересно? Тогда прошу под кат.
В этой статье я продемонстрирую, как динамически компилировать математические выражения из строк в runtime в C#, исключительно просто и быстро. Это решение поддерживает различные математические контексты, включая логические выражения, научные вычисления и C#, а также позволяет расширять эти контексты пользовательскими переменными, операторами и функциями.
В 1970-х годах известный программист Эдгар Кодд разработал математически выверенную теорию организации данных в виде таблиц (реляций). С тех пор утекло немало воды — появилось большое количество различных коммерческих и open-source реляционных систем управления базами данных (РСУБД). Скоро стало понятно, что эффективное получение данных из базы — задача далеко не тривиальная. Если говорить прямо, она нелинейная и в общем случае NP-сложная.
Когда SQL-запрос становится немного сложнее: SELECT * FROM table, у нас появляется огромная вариативность его исполнения внутри системы — и не всегда понятно, какой из возможных вариантов эффективнее как по памяти, так и по скорости. Чтобы сократить огромное количество вариантов до приемлемого, обычно используются так называемые эвристики — эмпирические правила, которые придуманы человеком для сокращения пространства поиска на несколько порядков. Понятное дело, эти правила могут отсечь и сам оптимальный план выполнения запроса, но позволяют получить хоть что-то приемлемое за адекватное время.
В последние годы в связи с активным развитием ML начали развиваться и нейронные оптимизаторы запросов —особенность которых в том, что они самостоятельно, без участия человека, находят необходимые закономерности в выполнении сложных планов исходя из обучения на огромном количестве данных. Тенденция началась приблизительно в 2017 году и продолжается до сих пор. Давайте посмотрим, что уже появилось в этой области в хронологическом порядке и какие перспективы нас ждут.
Перед тем, как смотреть решение обязательно попробуйте одолеть самостоятельно!
Автор решений: телеграм канал "Поступашки — ШАД, Стажировки и Магистратура".
Задача 1 (Линейность)
Рассмотрим линейное пространство многочленов степени не выше 3 над полем 
На нём задано отображение 
где 
- многочлен наивысшей степени, являющийся одновременно делителем и 
, и 
, у которого старший коэффициент совпадает со старшим коэффициентом . Дополнительно доопределим 
.
Пример: 
Является ли данное отображение линейным?
Судя по откликам, рассказы как я не стал миллионером или как мне не удалось спасить американскую АЭС, пользуются большим спросом на хабре. Поэтому продолжу публикацию кейсов из жизни быдлокодера и дам несколько бизнес-советов тем, кто собирается заработать миллионы продавая софт. Требую лайков, подписки и донатов, как настоящий инфоцыганбизнесмен.
Эта история произошла после того, как я вернулся из США в 2008 году, где благополучно потратил все свои деньги, полученные от разграбления советских заводов бандой прихатизаторов, во главе с Кахой Бендукидзе. В США я пытался запустить свой стартап, но не преуспел, но это история для мамкиных стартаперов с сайта VC. Здесь же расскажу, что было потом, поскольку это касается разработки и продвижения ПО. И бесплатно дам несколько бизнес-советов, которые за большие деньги можно получить только на курсах Тони Робинсона.
В России, как и во всем мире, в это время, кроме кризиса 2008 года, разворачивалась менее заметная, но не менее эпическая и трогательная история освобождения евреев от пленения фараоном. Для тех, кто не читал библию, напомню, что Моисей своих евреев, отпущенных из египетского плена, водил 40 лет по пустыне, (навигаторов и Яндекс-карт тогда не было, и назад никто свалить не мог). Ведомые плевались, плакали, матюкались, ругались, но шли по пустыне за Моисеем. Тот же самый библейский сюжет разворачивался в области разработки софта, cо специалистами из французской фирмы-разработчика, той-которую-нельзя-называть, и которая проектирует боевые самолеты Рафал. В недрах этой конторы была разработана система 3D-проектирования CATIA.
В детстве меня всегда завараживали игры с динамическим ландшафтом: The Castle и Worms Armageddon. В то время я не понимал, как реализована эта удивительная механика разрушения и изменения мира. Позже я узнал, что секрет заключался в использовании растровой графики, но интерес к теме не исчез. В этой статье я хочу рассказать о векторном решении аналогичной задачи.
Наше сообщество в телеграм "Поступашки — ШАД, Стажировки и Магистратуры" в частности специализируется на подготовке к стажировкам. В этой статье наши выпускники трех самых популярных направлений расскажут, как они проходили отбор. Далее представлен слегка отредактированный текст наших выпускников.
Аналитика
Сначала ждал контест. Мне и моему другу хватило всего 3 из 6 задач, чтобы позвали дальше на собеседования.
Аналитическая секция проходила так. Была одна алгоритмическая задача: есть массив целых чисел отсортированный, надо у всех отрицательных чисел знак поменять и снова отсортировать. Потом была стандартная задача на формулу Байеса: вычислить вероятность болезни, если тест показал положительный результат. В конце был бизнес кейс в духе как оценивать качество работы службы поддержки Яндекс такси. Поговорили про метрики, пользователей и тд. Прошел без каких-либо трудностей и напрягов. На все ушел час.
Алгоритмическая секция проходила так. Всего было две задачи. Первая задача: есть строка из Х, У, О наподобие "O,O,O,O,X,X,OY,O,O,X" найти минимальное расстояние между Х и У.
Вторая задача: есть массив целых чисел надо вывести границы отрезка с заданной суммой чисел, или если такого отрезка нет, то вывести (-1,-1). Опять же прошел собес без каких-либо трудностей. На все ушел час.
Интервью с командами прошли так. На финалах в основном были беседы за жизнь и спрашивали всякую фигню типо бизнес кейсов.
На первом финале были разговоры за жизнь и кейс: придумать метрики оценки системы рекомендаций фильмов на умных телевизорах.
На другом финале дали простейшую задачу на sql, которую я даже не запомнил, ибо на столько элементарная она была. Еще был бизнес кейс по оценке работы пуш уведомлений Яндекс лавки.
Но прям норм задачи были на финале в команде, которую я по итогу и выбрал. Было несколько задач по теор веру типо рассчитать оптимальный размер гардеробов в театре с двумя входами, если известно что приходят 400 человек (мы даже такую задачу решали на семинарах). Потом спросили: у тебя десять А/Б экспериментов проводится (цвета кнопки тестируются, ну 10 разных цветов ) и один из тестов показал значимый результат (ошибка первого рода 0.1) , так вот приходит дизайнерша и говорит что её цвет кнопки показал значимый результат, что ей стоит ответить. Более типичный вопрос про множественное тестирование, я немного потупил, но решил. Ещё две задачи чисто были на теор вер, но там длинные условия и я их не понял и особо не запомнил.
В статье рассмотрены примеры использования длинных (sapscript) текстов для построения шаблонов с использованием вложенности шаблонов, переменных и условных конструкций. Статья будет полезна для разработок рассылок на основе SAP NetWeaver, формирование печатных форм, рекомендательной/пояснительной документации.
Привет! Меня зовут Юрий Беляков, я старший ML-инженер в Купере. Сегодня предлагаю вместе разобраться, что такое плановая доставка и как устроен алгоритм управления слотами в Купере. Обсудим, как проходило тестирование и масштабирование от одного магазина до всех гипермаркетов, на какие грабли мы наступили и как на той же базе реализовать динамическое ценообразование.
Как вы считаете, если выполнить java.util.Arrays.sort(), то какая сортировка будет вызвана? Quicksort? Timsort? И та, и другая, потому что для объектов вызывается Timsort, а для примитивов (чисел int, long, float и так далее) — Dual-Pivot Quicksort. В JDK 6 для объектов использовался стандартный Merge sort, а для чисел классическая реализация Quicksort с одним опорным элементом, предложенная Джоном Бентли и Дугласом МакИлрой. В JDK 7 оба алгоритма поменялись: теперь объекты сортируются с помощью Timsort, автор Тим Петерс, а для простых типов данных используется Dual-Pivot Quicksort, предложенный мною вместе с Джоном Бентли и Джошем Блоком в 2009 году. Эта сортировка используется более 15 лет не только в JDK, но и в Android (хотя и немного устаревшая версия).
А зачем нам вообще второй алгоритм сортировки, если есть Timsort? Почему не использовать один и для объектов, и для примитивов? Сегодня я, как автор, расскажу историю Dual-Pivot Quicksort: как он начинался, как развивался и как продолжает развиваться сейчас.
Привет, Хабр! Меня зовут Вадим, я — младший научный сотрудник группы Controllable Generative AI лаборатории FusionBrain в AIRI. Последние несколько лет я занимаюсь исследованием генеративных моделей в контексте задачи редактирования фотографий. Мы с командой накопили большую экспертизу и хотели бы поделиться ей.
Совсем недавно мы выложили препринт статьи, которую мы представим на ECCV этой осенью (сама статья, её код, demo на HuggingFace). Там мы предложили метод редактирования реальных изображений с помощью диффузионных моделей, который достигает лучшего компромисса между качеством редактирования и сохранением структуры исходного изображения, а также эффективен с вычислительной точки зрения. В данной статье я хотел бы рассказать о том, почему приходится делать такой выбор, и как мы эту проблему обошли. Приятного чтения!
Всем привет! Для тех кто не знает, меня зовут Ш. Сергей!
Я хоть и программирую на Pascal/Assembler, но думаю что для людей, использующих другие ЯП, данная информация может быть полезна. Полностью рассмотреть вопросы оптимизации программ/игр практически не возможно, думаю для этого надо написать достаточно не малую книгу и всё равно что-нибудь да будет упущено.
Помните, оптимизация - это достаточно не простая задача. Код, который хотят оптимизировать, могут перебирать десятки раз и практически не получить результата. А иногда малейшие изменения в коде, могут дать хороший результат. Потому, желательно знать и понимать как можно оптимизировать код и стоит ли заниматься этим в данный момент.
Эта работа является заключением пятилетнего марафона по поиску самого быстрого способа нахождения минимального точного решения для задачи коммивояжёра в общем виде.
Тут я хочу подытожить все опробованные подходы и выбрать лучший по моему мнению.
Попалась на Stack Overflow интересная задачка: написать программу как можно короче и в одну строку. Что подразумевается под одной строкой? Это значит использовать только один оператор (statement) верхнего уровня с точкой с запятой в конце и не использовать блоки кода. Вложенные операторы допускаются.
Что происходит, когда мы отправляем сигнал приложению на node.js? Когда вызываются обработчики? А где хранятся? Во всем этом мы разберемся в данной статье, начиная от пользовательского кода на javascript и до встречи с операционной системой.
Решаем судоку на pytorch. Можно ли делать нейросети без обучения? Без кучи тестовых примеров? Попробую ответить на этот вопрос.
Многие знакомы с ELF-файлами и их структурой. Поговорим о программерах. Программер – это файл в формате ELF (расширение может быть BIN, MBN или ELF), который предназначен для работы с памятью смартфонов на Android с процессорами от Qualcomm в режиме аварийной загрузки (EDL mode – emergency download, 9008). Также его некоторые называют «пожарный шланг» (от английского firehose) или просто «шланг». Файл представляет из себя контейнер с набором команд для базовой работы с памятью, которые подписаны цепочкой сертификатов. Иногда возникает необходимость подобрать для своего устройства подходящий программер. Вот и попробуем разобраться в этом.
Привет, Хабр, я Павел Бузин, работаю аналитиком в компании Cloud.ru и занимаюсь решением задач, требующих применения различных математических методов, в том числе используемых для машинного обучения.
С появлением нейронных сетей почти каждый может попробовать себя в роли художника или дизайнера. Уверен, что будет неплохо максимально простым языком рассказать, каких правил стоит придерживаться, чтобы ваши работы получались на профессиональном уровне. В основе этих правил лежат закономерности, которые описаны на языке математики. Надеюсь, что понимание сути методов поможет вам найти новые и интересные дизайнерские решения.
В этой статье обсудим общие закономерности, так что если вы дизайнер, промпт-инженер или просто неравнодушны к прекрасному, вас ждет путешествие от Древней Греции до современных компьютеров с CAD и генеративными моделями. Математики и технари, добро пожаловать под кат, здесь вы будете чувствовать себя как дома. Гуманитарии, не пугайтесь, всё будет страшно только на первый взгляд.
