• Алгоритм Форчуна на C++ для построения диаграммы Вороного на плоскости

      Приветствую, уважаемые читатели данной статьи! В статье я дам описание имплементации алгоритма Форчуна (англ. Fortune's algorithm) для построения диаграммы Вороного (англ. Voronoi diagram) с использованием нативных сбалансированных двоичных деревьев поиска (для уникальных элементов) (англ. BST, binary search tree), предусмотренных стандартом C++, — ассоциативных упорядоченных контейнеров std::map и std::set.


      Читать дальше →
    • Об относительной яркости, или насколько живучим бывает легаси

        Я уверен, что многим программистам знакома формула:

        Y = 0.299 R + 0.587 G + 0.114 B

        А уж тот, кто плотно работал с графикой, знает эти цифры буквально наизусть — как в былые времена эникейщики запоминали серийники Windows. Иногда коэффициенты округляют до второго знака, иногда уточняют до четвертого, но каноническая форма именно такая.

        Вычисляет она относительную яркость цвета (relative luminance или в некоторых контекстах luma; не путать с lightness и brightness) и широко применяется для преобразования цветного RGB-изображения в Grayscale и связанных с этим задач.

        Формула растиражирована и процитирована в тысячах статей, форумных обсуждений и ответов на StackOverflow… Но дело в том, что единственно-правильное её место — на свалке истории. Использовать её нельзя. Однако же используют.

        Но почему нельзя? И откуда же взялись именно такие коэффициенты?
        Мини-экскурс в историю
      • Суперскалярный стековый процессор: оптимизация


          Продолжение серии статей, разбирающих идею суперскалярного процессора с
          OoO и фронтендом стековой машины. Тема данной статьи — оптимизация обращений к памяти.

          Предыдущие статьи:
          1 — описание работы на линейном куске
          2 — вызов функций, сохраняем регистры
          3 — вызов функций, взгляд изнутри
          Читать дальше →
        • Суперскалярный стековый процессор: подробности



            Продолжение серии статей, разбирающих идею суперскалярного процессора с OoO и фронтендом стековой машины.
            Тема данной статьи — вызов функций, вид изнутри.
            Читать дальше →
            • +12
            • 7,2k
            • 3
          • Помехоустойчивое кодирование с иcпользованием различных кодов

              Это продолженеие статьи о помехоустойчивом кодировании, которая очень долго лежала в черновиках. В прошлой части нет ничего интересного с практической точки зрения — лишь общие сведения о том, зачем это нужно, где применяется и т.п. В данной части будут рассматриваться некоторые (самые простые) коды для обнаружения и/или исправления ошибок. Итак, поехали.
              Читать дальше →
            • За один проход

                Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
                С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
                Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:

                Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число

                Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.
                Другие задачи
              • Об одной изящной конструкции

                  Введение


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

                  Распечатать в порядке возрастания все несократимые дроби, знаменатель которых не превосходит n, n<=100.

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

                  Такое решение верно и задача прошла все назначенные ей тесты. Однако, мой преподаватель сказал, что задачу можно решить намного красивее (он уже сталкивался с этой конструкцией). Так я и познакомился с этой замечательной конструкцией — деревом Штерна-Броко.
                  Читать дальше →
                • Суперскалярный стековый процессор: продолжаем скрещивать ужа и ежа


                    Продолжение статьи, где удалось продемонстрировать, что фронтенд стековой машины вполне позволяет спрятать за ним суперскалярный процессор с OoO.
                    Тема данной статьи — вызов функций.
                    Читать дальше →
                    • +12
                    • 6,2k
                    • 3
                  • Исследование: Считавшаяся «неуязвимой» память DDR4 подвержена уязвимости Rowhammer



                      Американские исследователи из компании Third I/O на состоявшейся в Китае конференции Semicon China представили доклад, в котором рассказали о том, что уязвимости Rowhammer подвержены и чипы DDR4. Ранее считалось, что память этого типа не подвержена данной уязвимости, которую весной 2015 года обнаружили ИБ-специалисты из Google.
                      Читать дальше →