Как стать автором
Обновить
16.5
Карма
0.5
Рейтинг

Пользователь

  • Подписчики 5
  • Подписки
  • Публикации
  • Комментарии

Декартово дерево: Часть 1. Описание, операции, применения

Алгоритмы *

Оглавление (на данный момент)


Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных. Что характерно, на Хабрахабре единственное его упоминание я нашел в обзорном посте многоуважаемого winger, но тогда продолжение тому циклу так и не последовало. Обидно, кстати.

Я постараюсь покрыть все, что мне известно по теме — несмотря на то, что известно мне сравнительно не так уж много, материала вполне хватит поста на два, а то и на три. Все алгоритмы иллюстрируются исходниками на C# (а так как я любитель функционального программирования, то где-нибудь в послесловии речь зайдет и о F# — но это читать не обязательно :). Итак, приступим.

Введение


В качестве введения рекомендую прочесть пост про двоичные деревья поиска того же winger, поскольку без понимания того, что такое дерево, дерево поиска, а так же без знания оценок сложности алгоритма многое из материала данной статьи останется для вас китайской грамотой. Обидно, правда?

Следующий пункт нашей обязательной программы — куча (heap). Думаю, также многим известная структура данных, однако краткий обзор я все же приведу.
Представьте себе двоичное дерево с какими-то данными (ключами) в вершинах. И для каждой вершины мы в обязательном порядке требуем следующее: ее ключ строго больше, чем ключи ее непосредственных сыновей. Вот небольшой пример корректной кучи:


На заметку сразу скажу, что совершенно не обязательно думать про кучу исключительно как структуру, у которой родитель больше, чем его потомки. Никто не запрещает взять противоположный вариант и считать, что родитель меньше потомков — главное, выберите что-то одно для всего дерева. Для нужд этой статьи гораздо удобнее будет использовать вариант со знаком «больше».

Сейчас за кадром остается вопрос, каким образом в кучу можно добавлять и удалять из нее элементы. Во-первых, эти алгоритмы требуют отдельного места на осмотр, а во-вторых, нам они все равно не понадобятся.
А теперь собственно про декартово дерево
Всего голосов 166: ↑161 и ↓5 +156
Просмотры 125K
Комментарии 30

Вертебро-базилярная недостаточность — болезнь программиста с тысячью лиц

Блог компании Маклауд Здоровье


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

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

Однако в то же время все перечисленные симптомы, столь непохожие друг на друга, характерны и для вертебро-базилярной недостаточности (ВБН), а причиной развития данного недуга может оказаться искривление шейного отдела позвоночника, вызванное неправильной осанкой при длительной работе за компьютером. Что же это за болезнь и как не допустить ее развития? Об этом мы и расскажем в сегодняшнем материале.
Читать дальше →
Всего голосов 52: ↑50 и ↓2 +48
Просмотры 18K
Комментарии 24

Идиомы С++. Type erasure

C++ *
Хотите получить представление о том, как устроен boost::function, boost::any “под капотом”? Узнать или освежить в памяти, что скрывается за непонятной фразой “стирание типа”? В этой статье я постараюсь кратко изложить мотивацию, стоящую за этой идиомой и ключевые элементы реализации.
Читать дальше →
Всего голосов 36: ↑34 и ↓2 +32
Просмотры 38K
Комментарии 25

Свод правил по работе с целыми числами в C/C++

Блог компании RUVDS.com Программирование *C++ *
Перевод

В основу статьи легли мои собственные выработанные нелегким путем знания о принципах работы и правильном использовании целых чисел в C/C++. Помимо самих правил, я решил привести список распространенных заблуждений и сделать небольшое сравнение системы целочисленных типов в нескольких передовых языках. Все изложение строилось вокруг баланса между краткостью и полноценностью, чтобы не усложнять восприятие и при этом отчетливо передать важные детали.
Читать дальше →
Всего голосов 78: ↑70 и ↓8 +62
Просмотры 21K
Комментарии 100

Использование быстрых клавиш в командной строке Linux (BASH)

Блог компании ГК ЛАНИТ Настройка Linux **nix *

Эта статья посвящена наиболее часто используемым комбинациям клавиш при работе в командной строке Linux (в основном в командном интерпретаторе bash).

Она точно будет полезна начинающим своё знакомство с Linux и, уверен, пригодится тем, кто уже имеет опыт (не всегда годы практики учат работать быстрее).

Никогда не развивал навыка быстрой печати, но знание не одного десятка hotkey'ев, перечисленных в этом материале, позволяет набирать команды со скоростью мысли.

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

Читать далее
Всего голосов 143: ↑142 и ↓1 +141
Просмотры 47K
Комментарии 64

Почему линукс использует swap-файл

Настройка Linux *Серверное администрирование *

Жажда тюнинга может завести в неведомые дебри. И, пожалуй, едва ли не самая частая неправильная оптимизация - отключение swap-файла. Если прикинуть частоту, с которой эта ошибка встречается, то, наверное, она входит в негласный top-10 (а может и top-5) самых распространенных, самых бесполезных и самых вредных оптимизаций - потому что swap-файл это одна из самых интересных, сложно понимаемых и недооцененных  сущностей в подсистеме управления виртуальной памятью.

Читать далее
Всего голосов 110: ↑100 и ↓10 +90
Просмотры 78K
Комментарии 403

Примеры C++ кода до и после Ranges

Блог компании OTUS Программирование *C++ *
Перевод
Снова здравствуйте. Перевод следующего материала подготовлен специально для студентов курса «Разработчик C++», занятия по которому стартуют уже 27 июня.



Библиотека Ranges была принята в C++20 на совещании стандартного комитета в Сан-Диего в ноябре прошлого года. Библиотека предоставляет компоненты для обработки диапазонов значений, направленных на упрощение нашего кода. К сожалению, библиотека Ranges не очень хорошо документирована, из-за этого ее труднее понять тем, кто хотел бы ее освоить. Этот пост предназначен для ознакомления с примерами кода, написанного с использованием Ranges и без нее.
Читать дальше →
Всего голосов 52: ↑47 и ↓5 +42
Просмотры 29K
Комментарии 49

Ref-qualified member functions

C++ *
В этом посте я расскажу о новой и (как мне кажется) относительно малоизвестной фиче C++ - reference-qualified member functions. Расскажу о правилах перегрузки таких функций, а также, в качестве примера использования, расскажу, как с помощью ref-qualified функций можно попытаться улучшить схему управления ресурсами, реализуемую с помощью другой идиомы С++ — RAII.
Читать дальше →
Всего голосов 53: ↑49 и ↓4 +45
Просмотры 16K
Комментарии 24

Makefile для самых маленьких

Программирование *
Tutorial
Не очень строгий перевод материала mrbook.org/tutorials/make Мне в свое время очень не хватило подобной методички для понимания базовых вещей о make. Думаю, будет хоть кому-нибудь интересно. Хотя эта технология и отмирает, но все равно используется в очень многих проектах. Кармы на хаб «Переводы» не хватило, как только появится возможность — добавлю и туда. Добавил в Переводы. Если есть ошибки в оформлении, то прошу указать на них. Буду исправлять.

Статья будет интересная прежде всего изучающим программирование на C/C++ в UNIX-подобных системах от самых корней, без использования IDE.

Компилировать проект ручками — занятие весьма утомительное, особенно когда исходных файлов становится больше одного, и для каждого из них надо каждый раз набивать команды компиляции и линковки. Но не все так плохо. Сейчас мы будем учиться создавать и использовать Мейкфайлы. Makefile — это набор инструкций для программы make, которая помогает собирать программный проект буквально в одно касание.
Читать дальше →
Всего голосов 89: ↑77 и ↓12 +65
Просмотры 544K
Комментарии 32

Ликбез по передаче параметров по значению в конструкторы и сеттеры (современный C++, примеры)

Программирование *Системное программирование *
Судя по комментам habr.com/ru/post/460831/#comment_20416435 в соседнем посте и развернувшейся там дискуссии, на Хабре не помешает статья, как правильно передавать аргументы в конструктор или сеттер. На StackOverflow подобного материала полно, но тут что-то я не припомню.

Потому что пример в той статье полностью корректен, и автор статьи абсолютно прав. Вот этот пример:

// Хорошо.
struct person {
  person(std::string first_name, std::string last_name)
    : first_name{std::move(first_name)} // верно
    , last_name{std::move(last_name)} // std::move здесь СУЩЕСТВЕНЕН!
  {}
private:
  std::string first_name;
  std::string last_name;
};

Такой код позволяет покрыть все (ну ладно, почти все) возможные варианты использования класса:
Читать дальше →
Всего голосов 46: ↑45 и ↓1 +44
Просмотры 16K
Комментарии 76

Variadic templates. Tuples, unpacking and more

C++ *
В этом посте я поговорю о шаблонах с переменным числом параметров. В качестве примера будет приведена простейшая реализация класса tuple. Также я расскажу о распаковке tuple'а и подстановки, хранимых там значений в качестве аргументов функции. И напоследок приведу пример использования вышеописанных техник для реализации отложенного выполнения функции, которое может быть использовано, например, в качестве аналога finally блоков в других языках.
Читать дальше →
Всего голосов 53: ↑51 и ↓2 +49
Просмотры 66K
Комментарии 7

Информация

В рейтинге
1,541-й
Зарегистрирован
Активность