B-Tree — сбалансированный куст поиска

Не знаю, одному мне так везёт, или нет, но буквально на каждом собеседовании на позицию BE разработчика я слышал и продолжаю слышать вопрос про индексы в реляционных СУБД. Затем речь часто заходит про "а что там под капотом?", и, как правило, сходу вспоминаются B-Tree и Hash, причём первый - это дефолт и собственно то, что мы чаще всего видим. Ну Hash это конечно Hash Map, да и с B-Tree по названию вроде всё логично и понятно: Tree в названии однозначно указывает на дерево, ну а В это, конечно, Binary? Или Balanced? Или Balanced Binary? Почему-то долгое время я полагал, что это Balanced Binary, и эта версия даже "прокатывала".

На самом деле Binary здесь, конечно, лишнее. B-Tree сбалансированное дерево поиска, но никак не бинарное. В статье я постараюсь привести базовую идею этой структуры, его преимущества и примеры использования. Для иллюстрации рассуждений также реализую Set с B-Tree под капотом на Java и сравню его с родным TreeSet (который в свою очередь "под капотом" имеет как раз таки бинарное Red-Black Tree).

https://habr.com/ru/articles/884232/

Алгоритмы и Структуры данных

Kotlin Coroutines под капотом: CoroutineContext и CoroutineScope

Structured Concurrency это одна из главных фишек Kotlin Coroutines, позволяющая оперировать иерархиями корутин через единый интерфейс, благодаря такой организации можно легко отменить сразу все корутины, имея ссылку только на самый высокоуровневый объект. В этой статье я разберу две базовые штуки на основе которых строится Structured Concurrency - CoroutineContext и CoroutineScope. Поехали!

https://habr.com/ru/articles/883588/

Алгоритмы и Структуры данных

Введение в многокритериальную оптимизацию, или как потерять чуть меньше денег на крипте

я Data Scientist и последние несколько месяцев я изучал применение методов многокритериальной оптимизации в машинном обучении. Сейчас хочу познакомить вас с этой интереснейшей задачей и показать довольно забавный пример её применения.

Я очень старался сделать статью максимально понятной для широкого круга читателей, но я довольно часто использую определение "Генетический алгоритм". Это интересная и полезная штука о которой можно почитать тут и посмотреть хороший курс Сергея Балакирева тут. Это облегчит восприятие статьи. Но в целом, генетические алгоритмы можно воспринимать, как просто чёрный ящик, который находит наименьшую точку любой функции.

https://habr.com/ru/articles/884426/

Алгоритмы и Структуры данных

SQL HowTo: подбираем значение ветвлением (Advent of Code 2024, Day 17: Chronospatial Computer)

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

В этой задаче мы немного потренируемся подбирать коды с помощью ветвящейся рекурсии.

https://habr.com/ru/companies/tensor/articles/884522/

Алгоритмы и Структуры данных

Задача о рюкзаке. Простое решение, но где-то должен быть подвох

Продолжаю свой крестовый поход по NP-полным задачам. От судоку и латинских квадратов немного устал, потому давеча решил переключиться на что-то другое. Выбор пал на задачу о рюкзаке, которая звучит следующим образом, цитата из Вики.

https://habr.com/ru/articles/884708/

Алгоритмы и Структуры данных

Способ представления числовых ключей для обратного поискового индекса

Хабр! Меня зовут Андрей Коваленко (Keva), я занимаюсь лингвистическими задачами и делаю поисковые движки. В МойОфис возглавляю разработку корпоративного полнотекстового поиска.

Существует две основные проблемы поиска численных значений в текстовых массивах (и массивах текстов).

Первая из них — многообразие способов представления одного и того же значения в тексте. Для одного и того же числа это может быть и 3600, и 3,600, и 3.6*10^3, и просто "три тысячи шестьсот". Решается это аккуратным прописыванием способов выделения таких объектов из текста.

Вторая проблема связана с поиском числовых интервалов.

Напомню, что, как правило, поисковые системы работают с так называемым обратным индексом, отличной метафорой которого будет алфавитный указатель в конце книги: все использованные термины приведены в нормальной форме и упорядочены лексикографически — проще говоря, по алфавиту, и после каждого указан номер страницы, на которой этот термин встречается. Разница только в том, что такая координатная информация в поисковиках, как правило, значительно подробнее. Например, корпоративный поиск МойОфис (рабочее название — baalbek), для каждого появления слова в документе хранит, кроме порядкового номера, ещё и его грамматическую форму и привязку к разметке.

https://habr.com/ru/companies/ncloudtech/articles/688230/

Алгоритмы и Структуры данных

Кто же такой этот многорукий бандит?

Представьте на секунду, что вы очень азартный игрок, который только что попал в казино и не может выбрать, за какой игровой автомат ему сесть. Или один муравей из колонии, выбирающий по какому пути ему пойти на поиски пищи. Или даже вы – это целый маркетплейс, который думает, какую же цену, ему поставить на тот или иной товар!

На первый взгляд может показаться, что все эти странные ситуации никак не связаны. Но это только на первый взгляд. Если откинуть всю необычность ситуации, то перед нами дилемма исследования-использования. Посудите сами: как азартный игрок, вы хотите найти автомат, дающий больше всего денег – это использование, но вы не знаете, какой это автомат и ищите его, дергая ручки и сравнивая выигрыши – это исследование. Как часто вам нужно подходить к игровому автомату, который, по вашему мнению, самый прибыльный, а как часто нужно сомневаться в этом и пробовать другие? Как часто муравью нужно идти по тому пути, где товарищи-муравьи уже протоптали тропинку, а как часто стоит рискнуть и пойти своей дорогой? Как часто нужно менять цену, чтобы поспевать за инфляцией и спросом пользователей, а еще при этом максимизировать прибыль?

Откинем красивые слова и перед тем, как кинуться в море алгоритмов и сбора данных, и формально опишем нашу модель:

https://habr.com/ru/articles/689364/

Алгоритмы и Структуры данных

Децентрализованный поиск для свободного веба

Статья состоит из нескольких частей. В первых частях описаны необходимые для создания децентрализованного поиска и доступные в 2022 году библиотеки и технологии. В последней части техники соединяются в единую поисковую систему и описано как запустить такой поиск самостоятельно.

https://habr.com/ru/articles/690252/

Алгоритмы и Структуры данных

Простейшая реализация HashMap на Go

Всем доброго времени суток. Для начинающего программиста (коим я и являюсь) реализация базовых структур данных, по типу бинарных деревьев и связных списков, довольно легка. Чего не скажешь о хэш картах. В этой статье мы и разберём пример её реализации.

https://habr.com/ru/articles/688964/

Алгоритмы и Структуры данных

Решение головоломки Fillwords на Python

Игра Fillwords популярна благодаря своей простоте и увлекательности: она развивает словарный запас, тренирует внимательность и логику. Миллионы игроков по всему миру используют её как способ расслабиться и одновременно размять мозг, а сложные уровни делают процесс поиска слов настоящим вызовом.

Играя в Fillwords, я заметил, что сложные уровни требуют всё больше времени. Это натолкнуло меня на идею создать программу-помощник на Python.

Я считаю, что это решение будет полезным упражнением как для начинающих программистов, так и для игроков, которым сложно находить подходящие слова.

Это моя первая публикация на Хабре, и я буду признателен за ваши советы и конструктивную критику.

https://habr.com/ru/articles/885008/

Алгоритмы и Структуры данных

Что такое компьютерная лингвистика и как технологии на её основе помогают людям с ограниченными возможностями здоровья

Многие из нас ежедневно пользуются поисковыми системами, голосовыми помощниками и переводчиками текстов. Появление этих технологий стало возможным благодаря компьютерной лингвистике — области искусственного интеллекта, которая занимается описанием естественных языков при помощи математических моделей. Рассказываем, что такое компьютерная лингвистика и обработка естественного языка, какие задачи они решают и как помогают расширять возможности людей с инвалидностью.

https://habr.com/ru/companies/netologyru/articles/656485/

Алгоритмы и Структуры данных

Модель составного полупростого числа

В предлагаемой статье приводится полная списочная многострочная модель (СММ) составного полупростого числа N и перечень вопросов, сопровождающих ее описание. Ответы на вопросы предлагается находить самим читателям. Найденные правильные ответы, либо комментируемые другими читателями, обеспечат глубокое понимание проблем, связанных с подобными числами и задачами. Выбор самих чисел предопределен их широким использованием в области информационной безопасности.
Рассматривая строки модели, особенно ее средней части читателя могут удивлять появления в строках квадратичных вычетов полных квадратов, возникающие интервалы между строками с кратными значениями делителей числа N, поведение средних вычетов и, возможно, что-то еще.

В предлагаемой вниманию читателей модели роль исследуемого числа отводится модулю N КЧКВ, т.е. N задан (может быть большим) и требуется в одной из задач отыскивать делители N. Для моделирования выбрана простая зависимость (линейная) N = х1 + хо. Очевидно, что список представлений такой модели конечен, и для чисел ограниченного размера может быть легко построен в форме таблицы, содержащей S =½ (N –1) строк. Модель названа списочной многострочной моделью и кратко обозначается (СММ, СМ-модель).

https://habr.com/ru/articles/880142/

Алгоритмы и Структуры данных

Как мы ускоряли виртуальные фоны в Толке

Началось все с того, что осенью прошлого года я общался со своим другом-коллегой на кухне. Ему хотелось ускорить виртуальные фоны, а у меня было немного времени.

Виртуальный фон – это важная фича Толка, которая позволяет обрезать все сзади тебя и вклеить одну фотографию. Например, вот фотография той самой кухни, где все и обсуждалось:

https://habr.com/ru/companies/skbkontur/articles/883094/

Алгоритмы и Структуры данных

Инвентарь в Godot

Разбираю один из многообразных способов создания инвентаря в игре на примере движка Godot. Рассматривается вариант написания его вручную, относительно простым образом, без использования классов и каких-то плагинов.

https://habr.com/ru/articles/885174/

Алгоритмы и Структуры данных

Глубокое обучение: Слой линейного преобразования и полносвязная нейросеть. Теория и реализация на самодельном autograd

Идею для реализации я взял из книги «Грокаем глубокое обучение». Здесь рассмотрим как использовать самодельный алгоритм автоматического дифференцирования при создании и обучении нейросети, про который я сделал разбор ранее.

https://habr.com/ru/articles/885466/

Алгоритмы и Структуры данных

Как Яндекс перепридумал поиск для разработчиков

Сегодня я расскажу непростую историю. Она про проблему, до решения которой у нас слишком долго не доходили руки. Из поста вы узнаете, почему стандартная метрика качества поиска не учитывала интересы разработчиков и как мы её улучшили. Расскажу про новую нейросеть CS YATI, обученную понимать таких же айтишников, как и мы. Ну и про грабли на нашем пути тоже расскажу, куда без них.

https://habr.com/ru/companies/yandex/articles/688952/

Алгоритмы и Структуры данных

Реализация метода принятия решений в
экспертных группах

Рассмотрим основные положения теории принятия решений. Приведем условия и порядок использования методов принятия групповых решений. Исследуем практический пример применения метода принятия решений в экспертной группе.

https://habr.com/ru/articles/885784/

Алгоритмы и Структуры данных

SQL HowTo: поиск пути и дихотомия (Advent of Code 2024, Day 18: RAM Run)

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

Сегодня напишем для решения простую реализацию алгоритма Ли и дихотомии.

https://habr.com/ru/companies/tensor/articles/885882/

Алгоритмы и Структуры данных

Теория сильного ИИ

В данной статье рассматриваются алгоритмы абстрактного мышления и механизм побуждения разума к действию. Это мышление - главная загадка современности и есть мнение, что компьютер не в силах ее решить, что только душа человека на это способна. Что сначала будет создана урезанная версия ИИ, а только потом будет создан сильный ИИ похожий на человеческий.

https://habr.com/ru/articles/688898/

Алгоритмы и Структуры данных

После прочтения сжечь. Или алгоритмы обработки данных вслепую (oblivious)

Так уж вышло, что я неплохо разбираюсь в разных PET (Privacy-Enhancing Technologies) и уже писал на хабре про совместные конфиденциальные вычисления. Сегодня повышаю градус и рассказываю про магию следующего порядка: слепую (забывчивую) передачу или oblivious transfer. Как обычно, на примере.

https://habr.com/ru/articles/886112/

Алгоритмы и Структуры данных

Я заставил новую модель Claude 3.7 Sonnet пройти собес по алгоритмам

Недавно в мире GenAI появились захватывающие новости: компания Anthropic представила новую языковую модель Claude 3.7 Sonnet. Эта модель объединяет в себе высокую скорость реакции и способности «глубокого» рассуждения (deep reasoning), что делает её одной из самых универсальных и продвинутых моделей на рынке коммерческих LLM. Благодаря инновационному подходу к гибридноcти, Claude 3.7 Sonnet способна как быстро отвечать на запросы, так и предоставлять подробное пошаговое обоснование своих выводов в зависимости от выбранного режима.

https://habr.com/ru/articles/886130/

Алгоритмы и Структуры данных