• Сортировка n-нарной пирамидой


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

      n-нарная куча; куча куч, основанная на числах Леонардо; дерамида (гибрид кучи и двоичного дерева поиска); турнирная мини-куча; зеркальная (обратная) куча; слабая куча; юнгова куча; биномиальная куча; и бог весть ещё какие кучи…

      И умнейшие представители computer science в разные годы предложили свои алгоритмы сортировки с помощью этих пирамидальных структур. Кому интересно, что у них получилось — для тех начинаем небольшую серию статей, посвящённую вопросам сортировки с помощью этих структур. Мир куч многообразен — надеюсь, вам будет интересно.
      Траффик
      • +23
      • 5.3k
      • 5
    • Руководство по JavaScript, часть 4: функции

      • Translation
      • Tutorial
      Сегодня публикуем четвёртую часть перевода руководства по JavaScript, которая посвящена функциям.

      Часть 1: первая программа, особенности языка, стандарты
      Часть 2: стиль кода и структура программ
      Часть 3: переменные, типы данных, выражения, объекты
      Часть 4: функции
      Часть 5: массивы и циклы
      Часть 6: исключения, точка с запятой, шаблонные литералы
      Часть 7: строгий режим, ключевое слово this, события, модули, математические вычисления
      Часть 8: обзор возможностей стандарта ES6
      Часть 9: обзор возможностей стандартов ES7, ES8 и ES9



      Функции в JavaScript


      Поговорим о функциях в JavaScript, сделаем их общий обзор и рассмотрим подробности о них, знание которых позволит вам эффективно ими пользоваться.
      Читать дальше →
      • +27
      • 21.1k
      • 2
    • Браузерные расширения для GitHub, которые увеличат продуктивность вашей работы



        Сейчас GitHub — самый популярный среди разработчиков сервис для совместной разработки программного обеспечения и размещения исходников в «облаке». Его используют как независимые разработчики, у которых в портфолио 1-2 приложения, так и технологические гиганты, включая Microsoft, Google и Facebook, у которых тысячи проектов.

        Собственно, рассказывать на Хабре о том, что такое GitHub, смысла нет; этот пост посвящен его браузерным расширениям, которые позволяют увеличить скорость и продуктивность работы. Вообще говоря, расширений этих очень много, поэтому мы выбрали те из них, которые используем в своей работе сами или которые порекомендовали коллеги.
        Читать дальше →
        • +32
        • 14.5k
        • 6
      • Запуск кластера RabbitMQ в Kubernetes

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

        В наших решениях мы используем интеграцию и с помощью Kafka, и с помощью gRPC, и с помощью RabbitMQ.

        В этой статье мы поделимся нашим опытом кластеризации RabbitMQ, ноды которого размещены в Kubernetes.

        image

        До RabbitMQ версии 3.7 его кластеризация в K8S была не очень тривиальной задачей, со множеством хаков и не очень красивых решений. В версии 3.6 использовался autocluster плагин из RabbitMQ Community. А в 3.7 появился Kubernetes Peer Discovery Backend. Он встроен плагином в базовую поставку RabbitMQ и не требует отдельной сборки и установки.

        Мы опишем итоговую конфигурацию целиком, попутно комментируя происходящее.
        Читать дальше →
      • C#: обратная совместимость и перегрузки

        • Translation
        Здравствуйте, коллеги!

        Напоминаем всем, что у нас вышла отличная книга Марка Прайса "C# 7 и .NET Core. Кросс-платформенная разработка для профессионалов". Обратите внимание: перед вами уже третье издание, первое издание было написано по версии 6.0 и на русском языке не выходило, а 3-е издание вышло в оригинале в ноябре 2017 года и охватывает версию 7.1.


        После выхода такого компендиума, который прошел отдельную научную редактуру для проверки обратной совместимости и прочей корректности изложенного материала, мы решили перевести интересную статью Джона Скита о том, какие известные и малоизвестные сложности с обратной совместимостью могут возникать в языке C#. Приятного чтения.
        Читать дальше →
        • +19
        • 8.9k
        • 5
      • А вы еще не платите премию за вовремя сделанные проекты?

          Беседовал я как-то с техническим директором одного из крупнейших банков России. В какой-то момент речь у нас зашла о премировании сотрудников. Тогда я ему говорю, что у нас в компании есть премирование сотрудников за вовремя сделанные проекты и задачи. Тут он завис секунд на пять, долгое молчание, недоумение в глазах:
          – Кхм… Так за это же программистам зарплату платят! – говорит он.
          – Да, платят. Но если изучить статистику успешных проектов в IT, становится грустно и хочется платить премию за выполненные в срок задачи.

          Попрощались мы, так и не придя к общему мнению по этому вопросу. В этой статье я и предлагаю разобраться, следует ли платить премию программистам за вовремя сделанные задачи и проекты. И вообще, когда стоит платить премии.
          Читать дальше →
        • [DotNetBook] Реализация IDisposable: правильное использование

          • Tutorial
          С этой статьей я начинаю публиковать целую серию статей, результатом которой будет книга по работе .NET CLR, и .NET в целом. Тема IDisposable была выбрана в качестве разгона, пробы пера. Вся книга будет доступна на GitHub: DotNetBook. Так что Issues и Pull Requests приветствуются :)

          Disposing (Disposable Design Principle)



          Сейчас, наверное, практически любой программист, который разрабатывает на платформе .NET, скажет, что ничего проще этого паттерна нет. Что это известный из известнейших шаблонов, которые применяются на платформе. Однако даже в самой простой и известнейшей проблемной области всегда найдется второе дно, а за ним еще ряд скрытых кармашков, в которые вы никогда не заглядывали. Однако, как для тех, кто смотрит тему впервые, так и для всех прочих (просто для того, чтобы каждый из вас вспомнил основы (не пропускайте эти абзацы (я слежу!))) — опишем все от самого начала и до самого конца.

          IDisposable



          Если спросить, что такое IDisposable, вы наверняка ответите что это

          public interface IDisposable 
          {
          	void Dispose();
          } 
          


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

          Примечание


          Глава, опубликованная на Хабре не обновляется и возможно, уже несколько устарела. А потому, прошу обратиться за более свежим текстом к оригиналу:




          Читать дальше →
        • Геометрия данных 5. Преобразование базиса

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



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

              В прошлых статьях я разобирал моделирование объектов, типов и атрибутов.

              Понятия: множество, тип, атрибут
              Как запутать аналитика. Часть первая
              Как запутать аналитика. Часть вторая: что такое моделирование предметной области?
              Как запутать аналитика. Часть третья. Глаголы и числительные

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

              Как запутать аналитика — 4. Вероятность и точность

              Далее я начал рассмотрение моделирования операций, функций и объектов с единой точки зрения.

              Как запутать аналитика — 5. Понятийный аппарат

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

              Для создания адаптера нам надо научиться моделировать одно и то же разными способами: как объект и как действие. Для философской мысли это не ново, потому что объекты не существуют вне времени, и действия не могут быть совершены без объектов. Фактически, нам предстоит посмотреть на мир так, как смотрят на него буддисты: объект и действие – одно и то же. Необходимость такого мировоззрения проистекает из необходимости объединения разных точек зрения на одно и то же происходящее. в данной статье я рассмотрю возможные представления реальности и мереологические отношения (отношения часть-целое) между ними.
              Читать дальше →
            • А вы уже применяете R в бизнесе?

                Настоящая публикация не содержит ни кода, ни картинок, поскольку суть вопроса несколько шире, а на конкретные вопросы всегда можно ответить в комментариях.


                За последние пару лет мне довелось применять R для решения весьма разнообразных задач в различных вертикалях. Естественно, что применение R заведомо подразумевает решение задач, связанных с той или иной математической обработкой цифровых данных, а разнообразность задач определялась, в первую очередь, самой предметной областью в которой эти прикладные задачи возникали. Частично отдельные задачи кратко упоминались в предыдущих публикациях. Разные предметные области, от земли (АПК) и заканчивая применением для прикладных задач с использованием летательных аппаратов, вплоть до космических.


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


                Независимое подтверждение этого тезиса можно получить путем наблюдения за экспоненциальным ростом успешного применения R в обычном бизнесе (не ИТ) на Западе. Например, практически половина докладов с конференции EARL 2017 (Enterprise Applications of the R Language), прошедшей в сентябре этого года, содержат кейсы по использованию R для решения бизнес-задач. В докладах есть примеры по анализу данных в недвижимости, автоматизация деятельности аудиторов, анализ транспортных систем, анализ системы канализации и многие другие отрасли...

                Читать дальше →
              • Геометрия данных 1. Симплексы и графы

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



                  Введение


                  Это первая статья серии, посвященной описанию свойств базисов пространств на основе элементов (а не векторов). Базис определяет систему координат — описание элементов пространства в виде набора чисел, характеризующих положение элемента относительно базиса.
                  Читать дальше →
                • Текстонезависимая идентификация по голосу

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


                  Однако, я не умею строить летающие тарелки или синтезировать вирусы, а потому речь пойдет про терминаторов, а точнее о том как этим трудягам помочь отыскать Джона Коннора.


                  image


                  Мой рукодельный терминатор будет несколько упрощён — он не сможет ходить, стрелять, говорить "I'll be back". Единственное на что он будет способен — распознать голос Коннора, ежели он его услышит (ну или, например, Черчилля, если его тоже надо будет найти).

                  Читать дальше →
                  • +35
                  • 13.3k
                  • 6
                • «Магическая константа» 0x5f3759df

                  • Translation
                  В этой статье мы поговорим о «магической» константе 0x5f3759df, лежащей в основе элегантного алгоритмического трюка для быстрого вычисления обратного квадратного корня.

                  Вот полная реализация этого алгоритма:

                  float FastInvSqrt(float x) {
                    float xhalf = 0.5f * x;
                    int i = *(int*)&x;  // представим биты float в виде целого числа
                    i = 0x5f3759df - (i >> 1);  // какого черта здесь происходит ?
                    x = *(float*)&i;
                    x = x*(1.5f-(xhalf*x*x));
                    return x;
                  }

                  Этот код вычисляет некоторое (достаточно неплохое) приближение для формулы

                  image

                  Сегодня данная реализация уже хорошо известна, и стала она такой после появления в коде игры Quake III Arena в 2005 году. Её создание когда-то приписывали Джону Кармаку, но выяснилось, что корни уходят намного дальше – к Ardent Computer, где в середине 80-ых её написал Грег Уолш. Конкретно та версия кода, которая показана выше (с забавными комментариями), действительно из кода Quake.
                  В этой статье мы попробуем разобраться с данным хаком, математически вывести эту самую константу и попробовать обобщить данный метод для вычисления произвольных степеней от -1 до 1.

                  Да, понадобится немного математики, но школьного курса будет более, чем достаточно.
                  Читать дальше →
                • TSP problem. Mixed algorithm

                    Всем доброго времени суток. В прошлых статьях мы сравнивали два эвристических алгоритма оптимизации на симметричной задаче коммивояжера таких как: ACS (ant colony system — муравьиный алгоритм) и SA (simulating annealing — алгоритм имитации отжига). Как мы убедились у каждого свои плюсы и минусы.


                    Читать дальше →
                    • +20
                    • 7.2k
                    • 5
                  • Математический детектив: поиск положительных целых решений уравнения

                    • Translation
                    «Я экспериментировал с задачами кубического представления в стиле предыдущей работы Эндрю и Ричарда Гая. Численные результаты были потрясающими…» (комментарий на MathOverflow)
                    Вот так ушедший на покой математик Аллан Маклауд наткнулся на это уравнение несколько лет назад. И оно действительно очень интересно. Честно говоря, это одно из лучших диофантовых уравнений, которое я когда-либо видел, но видел я их не очень много.

                    Я нашёл его, когда оно начало распространяться как выцепляющая в сети нердов картинка-псевдомем, придуманная чьим-то безжалостным умом (Сридхар, это был ты?). Я не понял сразу, что это такое. Картинка выглядела так:


                    «95% людей не решат эту загадку. Сможете найти положительные целочисленные значения?»

                    Вы наверно уже видели похожие картинки-мемы. Это всегда чистейший мусор, кликбэйты: «95% выпускников МТИ не решат её!». «Она» — это какая-нибудь глупая или плохо сформулированная задачка, или же тривиальная разминка для мозга.

                    Но эта картинка совсем другая. Этот мем — умная или злобная шутка. Примерно у 99,999995% людей нет ни малейших шансов её решить, в том числе и у доброй части математиков из ведущих университетов, не занимающихся теорией чисел. Да, она решаема, но при этом по-настоящему сложна. (Кстати, её не придумал Сридхар, точнее, не он полностью. См. историю в этом комментарии).

                    Вы можете подумать, что если ничего другое не помогает, то можно просто заставить компьютер решать её. Очень просто написать компьютерную программу для поиска решений этого кажущегося простым уравнения. Разумеется, компьютер рано или поздно найдёт их, если они существуют. Большая ошибка. Здесь метод простого перебора компьютером будет бесполезен.
                    Читать дальше →
                  • Нестандартная кластеризация, часть 3: приёмы и метрики для кластеризации временных рядов

                      Часть первая — Affinity Propagation
                      Часть вторая — DBSCAN
                      Часть третья — кластеризация временных рядов
                      Часть четвёртая — Self-Organizing Maps (SOM)
                      Часть пятая — Growing Neural Gas (GNG)

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

                      Кластеризация временных рядов — неблагодарное дело. Даже при группировке статических данных часто получаются сомнительные результаты, что уж говорить про информацию, рассеянную во времени. Однако нельзя игнорировать задачу, только потому что она сложна. Попробуем разобраться, как выжать из рядов без меток немного смысла. В этой статье рассматриваются подтипы кластеризации временных рядов, общие приёмы и популярные меры расстояния между рядами. Статья рассчитана на читателя, уже имевшего дело с последовательностями в data science: о базовых вещах (тренд, ARMA/ARIMA, спектральный анализ) рассказываться не будет.

                      Читать дальше →
                      • +18
                      • 24.1k
                      • 5
                    • Тестовая документация. Превращаем таблицы в деревья



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

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

                        Вид тестовой документации также зависит от ситуации на проекте и ожиданий заказчика.
                        Читать дальше →
                      • Вещи, которые мне надо было знать прежде, чем создавать систему с очередью

                          Фото очереди в мавзолей Мао Цзэдуна —  BrokenSphere / Wikimedia Commons

                          В проекте, над которым я сейчас работаю, применяется распределённая система обработки данных: сначала несколько десятков машин одновременно производят некоторые сообщения, затем эти сообщения отправляются в очередь, из очереди три потока извлекают сообщения и после финальной обработки выкладывают данные в базу Redis. При этом имеется требование: от «зарождения» события в машине, производящей сообщение, до выкладывания обработанных данных в базу должно проходить не более четырёх секунд в 90% случаев.

                          В какой-то момент стало очевидно, что мы это требование не выполняем, несмотря на затрачиваемые усилия. Несколько произведённых измерений и маленький экскурс в теорию очередей привели меня к выводам, которые я бы хотел донести до себя самого несколько месяцев назад, когда проект только начинался. Отправить письмо в прошлое я не могу, но могу написать заметку, которая, возможно, избавит от неприятностей тех, кто только задумывается над тем, чтобы применять очереди в собственной системе.
                          Читать дальше →
                        • Делаем data science-портфолио: история через данные

                          • Translation
                          • Tutorial
                          Предисловие переводчика

                          Перевод внезапно удачно попал в струю других датасайенсных туториалов на хабре. :)
                          Этот написан Виком Паручури, основателем Dataquest.io, где как раз и занимаются подобного рода интерактивным обучением data science и подготовкой к реальной работе в этой области. Каких-то эксклюзивных ноу-хау здесь нет, но очень подробно рассказан процесс от сбора данных до первичных выводов о них, что может быть интересно не только желающим составить резюме на data science, но и тем, кто просто хочет попробовать себя в практическом анализе, но не знает, с чего начать.


                          Data science-компании всё чаще смотрят портфолио, когда принимают решение о приёме на работу. Это, в  частности, из-за того, что лучший способ судить о практических навыках — именно портфолио. И хорошая новость в том, что оно полностью в вашем распоряжении: если постараетесь – сможете собрать отличное портфолио, которым будут впечатлены многие компании.

                          Читать дальше →
                        • Лучше один раз услышать чем семь раз прочитать

                          • Tutorial
                          Большинство статей о музыке и нотной записи страдают большим недостатком: текстовое описание, скажем, отличия септаккорда от трезвучия, есть, а звука, чтоб это отличие услышать — нет.

                          image

                          Хорошим обратным примером является интерактивный мини-учебник по теории музыки от Ableton
                          Читать дальше →