Пользователь
Всем привет. В этой статье я расскажу про дерево отрезков. Очень мощной структуры данных, которая позволяет делать много разных операций над массивом чисел. Я постараюсь по полочкам разложить эту тему и объяснить возможности дерева отрезков. Также я разберу несколько нетривиальных задач на дерево отрезков. Помимо самого дерева отрезков я расскажу и про связанные темы: дерево Фенвика и разреженные таблицы.
Viam supervadet vadens (дорогу осилит идущий)
Есть много счастливчиков, которым повезло работать в ситуации, когда объёмы по-настоящему огромны и требования кажутся невыполнимыми. Но есть те, кому по настоящем крупно повезло! Я говорю о тех, кто решал задачи в пространствах, где размерность больше 1.
Давайте разбросаем осколки по всей земле?
В данной публикации я поделюсь двумя основными причинами, по которым я предпочитаю избегать использования автоинкрементных полей в PostgreSQL и MySQL в будущих проектах. Вместо этого я предпочитаю использовать UUID-поля, за исключением случаев, когда есть очень веские аргументы против этого подхода.
В статье будет рассказано про основные алгоритмы, которые ядро Linux использует для планирования задач, готовых к выполнению. Как влияет приоритет задач и указанная для неё политика на то, как она будет получать процессорное время и сколько.
А давайте возьмём простейший процессор и напишем его эмулятор на Python. Будем кормить его бинарниками и дебажить.
Статья для тех, кто всегда хотел разобраться в машинном коде, но боялся начать.
Это цикл статей где мы создаем базу данных с нуля. За образец автор взял sqlite, так как простая база данных, где вся база данных храниться в одном файле и меньше фич по сравнению с mysql.
Мы ответим на эти вопросы: В каком формате данные будут сохранены(в памяти или на диске), Когда они должны сохраняться на диск? Почему первичный ключ(primary key) является единственным на одну таблицу?, и так далее
В этой части мы создадим REPL, которое принимает команды, обрабатывает ошибки.
Привет! Меня зовут Дмитрий Королёв, я бэкенд-разработчик в Авито. В этой статье я расскажу про ключевые аспекты и концепции работы с наиболее популярными алгоритмами и структурами данных. Это поможет и в реальных проектах, и чтобы глубже понять алгоритмические принципы. Статья подойдёт специалистам, которые хотят углубить свои знания в программировании, и укрепить навыки нахождения оптимальных решений алгоритмических задач.
У современного читателя может возникнуть резонный вопрос — почему программисты, а не IT‑ишники? Ответ кроется в самом заголовке. В 70-х, 80-х годах прошлого столетия, а точнее в СССР не было понятия IT‑и. Были понятия «кибернетика», «вычислительная техника», «электронно‑вычислительные машины» (или просто ЭВМ), и были понятия «программист» и «машинист». Если с программистом все понятно, то машинисты отвечали за эксплуатацию ЭВМ, их ремонт, обслуживание и т. п. Их еще называли электронщиками. Современный IT‑шник может задаться вопросом — какое обслуживание, какой ремонт? И будет прав, но прав применительно к современности. А тогда ЭВМ занимали огромные помещения и требовали большого штата различных специалистов:
В мире компьютерных наук мало что может сравниться с созданием собственной операционной системы. В этой статье мы погрузимся в увлекательный мир разработки операционных систем, создав 16-битную ОС с помощью языка ассемблера NASM под архитектуру процессоров Intel x86-64. Мы рассмотрим каждый этап разработки, начиная с основ и заканчивая реализацией ключевых компонентов.
СУБД PostgreSQL способна бысто работать с огромными массивами данных благодаря множеству различных механизмов, таких как карта свободного пространства, позволяющая за короткий промежуток времени найти страницу из основного слоя с необходимым свободным пространством для вставки новых версий строк.
В этой статье мы разберемся в устройстве карты свободного пространства, а также познакомимся с алгоритмом получения страницы с необходимым свободным пространством.
У каждого разработчика есть набор инструментов для решения различных задач. Однако со временем возникает необходимость расширять этот набор, чтобы эффективно справляться с более сложными задачами. В этой статье я хочу познакомить вас с инструментом, которым вы, скорее всего, раньше не пользовались. И хотя он подходит для решения узкого спектра задач, его использование может оказаться весьма полезным. Знакомьтесь — "фильтр Блума" (Bloom filter).
Формат изображений JPEG появился ещё в конце прошлого века, причём актуальность он не теряет, а, наоборот, набирает. Казалось бы, что можно изменить в технологии, которой столько лет? В Google посчитали, что сейчас самое время для оптимизации формата, а именно повышения эффективности компрессии. Что предложили в Google и как работает новая технология?
По работе стояла задача оптимизации поиска по адресам (улицы, дома и объекты). Главный критерий - нахождение адреса, если написано с ошибками или не дописан он в полной мере. Bert’ы, косинусные расстояния эмбеддингов и т.д. не подходили, так как они заточены под смысловой поиск, а в адресах смысла нет. TF-IDF c лемматизацией тоже не очень подходил для этой задачи, результаты были плохие.
Для реализации начал использовать расстояние Дамерау-Левенштейна, и в последствие, развил это до собственного алгоритма, который находит расстояние между двумя строками.
Цель данного поста описание только алгоритма.
При реализации Cosmo Router, open-source замена Apollo Router, мы столкнулись с проблемой поддержания нашего кода для решения проблемы N+1. Реализация маршрутизатора для федеративных служб GraphQL в значительной степени зависит от возможности группировать вложенные запросы GraphQL для сокращения числа запросов к подграфам.
Чтобы решить эту проблему, мы разработали новый алгоритм, который решает проблему N+1 более эффективно и проще для поддержания, чем наше предыдущее решение, которое было основано на шаблоне DataLoader, обычно используемом в сообществе GraphQL. Вместо разрешения сначала по глубине, мы загружаем данные сначала по ширине, что позволяет нам сократить параллелизм с O(N^2) до O(1) и улучшить производительность до 5 раз, сокращая сложность кода.
Если вы заинтересованы в проверке кода, вы можете найти его на GitHub.
Я также провел лекцию на эту тему на GraphQL Conf 2023, которую вы можете посмотреть здесь.
Всем привет! Я Сергей, работаю в B2B-команде Яндекс Маркета последние 3,5 года. Как уже понятно из заголовка, сейчас я вам расскажу про yet-another-миграцию с базы на базу, которая началась в середине 2021 года и заняла почти год. Получается, мемуары.
Вас ждёт рассказ о том, как мы:
- несколько месяцев чинили тесты и делали трансформер;
- десятки раз переливали данные;
- чинили баги незаметно для пользователей;
- заставили сервис работать на PostgreSQL быстрее, чем он работал на Oracle.
21 марта Redis Ltd. объявила, что, начиная с Redis 7.4, ее «in-memory data store» будет выпускаться под несвободными лицензиями с доступным (source-available) исходным кодом. Новость малоприятная, но вполне ожидаемая. Необычно в этой ситуации обилие альтернатив для тех, кто хочет остаться со свободным ПО: есть как минимум четыре варианта замены, включая уже существующий форк под названием KeyDB и недавно анонсированный проект Valkey от Linux Foundation. Вопрос теперь в том, что предпочтут пользователи, провайдеры и создатели дистрибутивов Linux.
Divide et impera (разделяй и властвуй) – древний принцип для управления чем-то большим и сложным.
Многие из нас программируют. Многие из нас делают системы, сложные системы. Но некоторым повезло работать в ситуации, когда объёмы по-настоящему огромны и требования кажутся невыполнимыми. Шардировние – один из излюбленных счастливчиками, которых зовут приключения, приемов.
Что-нибудь разбить на кусочки – это круто! Переходите на сторону шардирования у нас есть печеньки!