• Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней

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


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

      Тема сегодняшней лекции


      В прошлый раз мы с вами познакомились — скажем прямо, очень обширно познакомились — с понятием декартового дерева и основным его функционалом. Только до сих мы с вами использовали его одним-единственным образом: как «квази-сбалансированное» дерево поиска. То есть пускай нам дан массив ключей, добавим к ним случайно сгенерированные приоритеты, и получим дерево, в котором каждый ключ можно искать, добавлять и удалять за логарифмическое время и минимум усилий. Звучит неплохо, но мало.

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

      Ищем индекс


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

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

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


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

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

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

        Введение


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

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


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

        Сейчас за кадром остается вопрос, каким образом в кучу можно добавлять и удалять из нее элементы. Во-первых, эти алгоритмы требуют отдельного места на осмотр, а во-вторых, нам они все равно не понадобятся.
        А теперь собственно про декартово дерево
      • Пишем свою ОС: Выпуск 1

          Данный цикл статей посвящён низкоуровневому программированию, то есть архитектуре компьютера, устройству операционных систем, программированию на языке ассемблера и смежным областям. Пока что написанием занимаются два хабраюзера — iley и pehat. Для многих старшеклассников, студентов, да и профессиональных программистов эти темы оказываются весьма сложными при обучении. Существует много литературы и курсов, посвящённых низкоуровневому программированию, но по ним сложно составить полную и всеохватывающую картину. Сложно, прочитав одну-две книги по ассемблеру и операционным системам, хотя бы в общих чертах представить, как же на самом деле работает эта сложная система из железа, кремния и множества программ — компьютер.

          Каждый решает проблему обучения по-своему. Кто-то читает много литературы, кто-то старается поскорее перейти к практике и разбираться по ходу дела, кто-то пытается объяснять друзьям всё, что сам изучает. А мы решили совместить эти подходы. Итак, в этом курсе статей мы будем шаг за шагом демонстрировать, как пишется простая операционная система. Статьи будут носить обзорный характер, то есть в них не будет исчерпывающих теоретических сведений, однако мы будем всегда стараться предоставить ссылки на хорошие теоретические материалы и ответить на все возникающие вопросы. Чёткого плана у нас нет, так что многие важные решения будут приниматься по ходу дела, с учётом ваших отзывов.
          Читать дальше →
        • Использование boost::variant для описания состояний модели

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

            Например, если у вас в программе пользователь может переключаться между двумя экранами, вы заводите enum screen { screen_one, screen_two }; и переменную screen cur_screen_. Отрисовщик должен получить у модели «текущий выбранный экран», и затем отрисовать его, запрашивая у модели дополнительные данные, относящиеся именно к этому экрану. Что-то вроде:

            switch (model.cur_screen())
            {
            case screen_one:
              model.get_screen_one_elements();
              ...
            case screen_two:
              model.get_screen_two_elements();
              ...
            }


            При использовании такой модели, программист может запрашивать данные, которые для текущего состояния совершенно не актуальны. Например, вызвать метод get_screen_two_elements() для получения списка элементов второго экрана, когда текущий экран — первый. Хорошей практикой является использование ассертов вида ASSERT(cur_screen_ == screen_one) в методах, зависимых от конкретного экрана. Это обеспечивает некоторый контроль времени выполнения.

            Но есть способ обеспечить контроль времени компиляции и более явное разделение состояний с помощью boost::variant.

            Читать дальше →
          • Миграция с RAID1 на RAID5 в mdadm без потери данных

              Допустим есть у нас под Linux софтварный RAID1 собранный с помощью mdadm:
              # cat /proc/mdstat
              Personalities : [raid1]
              md0 : active raid1 sdb[1] sda[0]
                    8387572 blocks super 1.2 [2/2] [UU]

              И появился у нас еще один винчестер который хотелось бы воткнуть в данную машину расширив доступное дисковое пространство не потеряв при этом в отказоустойчивости т.е. перейти с RAID1 на RAID5.
              Читать дальше →
            • Согласованные в конечном счете (Eventually Consistent)

              • Перевод
              В последнее время на хабре чаще стали встречаться обсуждения масштабируемых систем и NoSQL решений. Эта статья, написанная техническим директором Amazon — одна из лучших вводных, на мой взгляд, показывающая, какие проблемы возникают при построении масштабируемых систем, что нужно учесть при выборе инструментария, что имеют ввиду авторы кассандры, говоря про обеспечение AP в кассандре и CP в HBase и многое другое.
              Читать дальше →
            • Другое видение скучных GTD планировщиков через призму RPG игр

                10 слов об идее.


                GTD планировщик в виде многопользовательской RPG для команд разработчиков, вот.

                Коротко.


                Все вы знаете, что такое GTD. Проекты, таски, майлстоуны и дедлайны. Множество контор и команд разработчиков используют ту или иную систему на базе (или не на базе) GTD для контроля задач в проектах в своей повседневной работе. Я предлагаю заменить основные понятия этой методологии на термины многопользовательских RPG, добавить плюшек, статистику, достижения, красивости и фан. Получим тот же планировщик, но не такой скучный и с дополнительной мотивацией.

                Lol, это шутка? Да, так и есть, это шутка. Но в каждой шутке, как говорится, есть доля шутки.

                …Говоря о лени и ММО, сейчас я задумываюсь, если мне так влом утром вставать на работу, если мне так лень было ходить на пары, если мне нужно огромное количество усилий потратить, чтобы заставить себя наконец открыть Flex Builder и дописать этот глупый проект, почему я 4 месяца не получая за это зарплаты, вставал в 6 часов утра и весь день «работал» в игре? …

                Дла заинтересовавшихся или тех, кому просто любопытно — велкам за хабракат. А вот пока картинка на затравку.



                Читать дальше
              • 5 способов, которыми игры пытаются вызвать зависимость

                • Перевод
                Итак, в новостях снова пишут, что кто-то еще умер из-за игромании. Да, опять Корея.

                Какого ...? послушайте, я не пытаюсь доказать что видео игры — это героин. Я полностью понимаю, что в данном случае у жертвы было много проблем в жизни. Но, половина из вас знает что World of Warcraft затягивает и что доктора считают игровую зависимость серьёзной проблемой. А вопрос вот в чем: может быть какие-то игры намеренно разрабатывались, чтобы заставлять вас играть в них, даже если вы не получаете от этого удовольствия?
                Давайте посмотрим как это работает
              • Обнаружена серьезная уязвимость в протоколе защиты данных WPA2

                  image

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

                  Читать дальше →
                • Обзор генераторов псевдослучайных чисел для CUDA

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

                    Читать дальше →
                  • Полноценный доступ ко всем Linux-файловым системам в Windows 2000/XP/Vista/7 с помощью coLinux

                      В данной статье я расскажу вам, как получить практически полноценный доступ для чтения и записи ко всем файловым системам, используемым в Linux (Ext2/3/4, ReiserFS, XFS, JFS, etc) из-под сабжевых операционных систем. Статья является вольным переводом данного руководства, причем написано оно уже довольно давно, но догуглился я до него только сейчас. :)
                      Читать дальше →
                    • Эффективное использование встроенного в Opera блокировщика рекламы

                        Доброго времени суток, уважаемые Хабровчане!

                        Многие уже давно это знают, а многие — еще нет. Речь идет о том, как в браузере Opera, что называется — from-the-box, грамотно настроить блокировку рекламы, а также отключить «следящие» за пользователем скрипты google ad-sense и yandex direct.

                        Читать дальше →
                      • Материалы продвинутого уровня по Питону

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

                          После прочтения Dive into Python или подобной ей и ознакомления с документацией возникает вопрос, а что читать дальше? Можно обратиться к списку книг на python.org. Там есть раздел Advanced Books, но в нем всего лишь 6 книг (седьмая не выходила), и только одну я бы назвал по-настоящему стоящей.

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

                          Ниже собраны сложные материлы про Питон, его устройство и возможности. Все на английском (грех, не знать технический английский). Про Dive into Python я слукавил. Большинство приведенных материалов требуют хорошее знание Питона и наличие опыта программирования на нем.

                          Подробнее