• Алгоритм резервуарной выборки

      Резервуарная выборка (eng. «reservoir sampling») — это простой и эффективный алгоритм случайной выборки некоторого количества элементов из имеющегося вектора большого и/или неизвестного заранее размера. Я не нашел об этом алгоритме ни одной статьи на Хабре и поэтому решил написать её сам.

      Итак, о чём же идёт речь. Выбрать один случайный элемент из вектора — это элементарная задача:

      // C++
      std::random_device rd;
      std::mt19937 gen(rd());
      std::uniform_int_distribution<> dis(0, vect.size() — 1);
      
      auto result = vect[dis(gen)];
      

      Задача «вернуть K случайных элементов из вектора размером N» уже хитрее. Здесь уже можно ошибиться — например, взять K первых элементов (это нарушит требование случайности) или взять каждый из элементов с вероятностью K/N (это нарушит требование взять ровно K элементов). Кроме того, можно реализовать и формально корректное, но крайне неэффективное решение «перемешать случайно все элементы и взять K первых». И всё становится ещё интереснее, если добавить условие того, что N — число очень большое (нам не хватит памяти сохранить все N элементов) и/или не известно заранее. Для примера представим себе, что у нас есть какой-то внешний сервис, присылающий нам элементы по одному. Мы не знаем сколько их придёт всего и не можем сохранить их все, но хотим в любой момент времени иметь набор из ровно K случайно выбранных элементов из уже полученных.

      Алгоритм резервуарной выборки позволяет решить эту задачу за O(N) шагов и O(K) памяти. При этом не требуется знать N заранее, а условие случайности выборки ровно K элементов будет чётко соблюдено.
      Читать дальше →
    • Нагрузочное тестирование с locust. Часть 2

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

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

      Читать дальше →
    • Страдать на работе — не обязательно

        Смотрел я тут на днях выступление Kate Gregory на конференции Pacific++ 2018.

        Видео выступления


        Кейт — хороший программист и отличный спикер. Сам доклад поднимает много интересного о программировании на С++ и программировании вообще (стоит посмотреть). Но больше всего меня зацепила одна высказанная ею (буквально вскользь) мысль. Кейт удалось очень кратко и по делу обозначить мотивацию программистов. Звучала она так: «Программист во время работы стремится максимизировать своё счастье». Это звучит банально, но ведь так оно и есть.

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

        Сразу хочу вынести за скобки вопросы оплаты труда, условий работы, начальства, коллектива и прочего. Если вы работаете там, где работаете — то всё это вас примерно устраивает. Давайте сфокусируемся на том, что делает нас счастливыми и несчастными при непосредственной работе над кодом.
        Читать дальше →
      • Нагрузочное тестирование с locust

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

        Когда речь заходить о тестировании производительности — в первую очередь все думают о JMeter’е — он бесспорно остается самым известным инструментом с самым большим количеством плагинов. Мне же JMeter никогда не нравился из-за неочевидного интерфейса и высокого порога вхождения, как только возникает необходимость протестировать не Hello World приложение.

        И вот, окрыленный успехом проведения тестирования в двух различных проектах, решил поделится информацией об относительно простом и удобном софте — Locust

        Для тех, кому лень идти под кат, записал видео:


        Читать дальше →
      • Будущее WebAssembly в виде «дерева навыков»

        • Перевод
        Некоторые люди как-то неправильно поняли WebAssembly. Есть те, кто считает, что раз браузеры уже поддерживают выполнение WebAssembly (ещё с 2017 года), значит всё уже готово. Даже и близко ещё нет, готов лишь MVP (минимально жизнеспособный продукт). Я могу предположить откуда произрастает корень этого заблуждения: после релиза MVP его разработчики пообещали поддерживать обратную совместимость на уровне «любой написанный сейчас код будет работать и в будущем». Но это ведь не значит, что разработка WebAssembly закончена, совсем нет! Множество фич разрабатывается прямо сейчас и планируется к разработке в ближайшем будущем. И когда они будут реализованы — всё очень сильно изменится.

        Все эти фичи можно попробовать представить себе в виде дерева навыков в какой-нибудь игре. У нас есть пару «базовых» (уже реализованные фичи) и целое дерево со множеством веток и листьев, которые будут со временем открываться, давая нам всё больше и больше могущества.
        image
        Давайте посмотрим на то, что у нас уже есть сейчас и что нам ещё предстоит открыть.
        (Под катом много картинок, трафик)
        Читать дальше →
      • Как правильно и неправильно спать

          Не так давно мимо нас пробегала неплохая статья об ужасном состоянии производительности современного ПО (оригинал на английском, перевод на Хабре). Эта статья напомнила мне об одном антипаттерне кода, который встречается весьма часто и в общем кое-как работает, но приводит к небольшим потерям производительности то тут, то там. Ну, знаете, мелочь, пофиксить которую руки никак не дойдут. Беда лишь в том, что десяток таких «мелочей», разбросанных в разных местах кода начинают приводить к проблемам типа «вроде у меня последний Intel Core i7, а прокрутка дёргается».

          Я говорю о неверном использовании функции Sleep (регистр может отличаться в зависимости от языка программирования и платформы). Итак, что же такое Sleep? Документация отвечает на этот вопрос предельно просто: это пауза в выполнении текущего потока на указанное количество миллисекунд. Нельзя не отметить эстетическую красоту прототипа данной функции:

          void Sleep(DWORD dwMilliseconds);

          Всего один параметр (предельно понятный), никаких кодов ошибок или исключений — работает всегда. Таких приятных и понятных функций очень мало!

          Ещё большим уважением проникаешься к этой функции, когда читаешь, как она работает
          Функция идёт к планировщику потоков ОС и говорит ему «мы с моим потоком хотели бы отказаться от выделенного нам ресурса процессорного времени, сейчас и ещё на вот столько-то миллисекунд в будущем. Отдайте бедным!». Слегка удивлённый подобной щедростью планировщик выносит функции благодарность от имени процессора, отдаёт оставшийся кусок времени следующему желающему (а такие всегда найдутся) и не включает вызвавший Sleep поток в претенденты на передачу ему контекста выполнения на указанное количество миллисекунд. Красота!

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

          • Перевод
          Один из пользователей компилятора Visual C++ привёл следующий пример кода и спросил, почему его цикл с условием выполняется бесконечно, хотя в какой-то момент условие должно перестать выполняться и цикл должен закончиться:

          #include <windows.h>
          
          int x = 0, y = 1;
          int* ptr;
          
          DWORD CALLBACK ThreadProc(void*)
          {
            Sleep(1000);
            ptr = &y;
            return 0;
          }
          
          int main(int, char**)
          {
           ptr = &x; // starts out pointing to x
          
           DWORD id;
           HANDLE hThread = CreateThread(nullptr, 0, ThreadProc, 0, &id);
          
           // Ждём, пока другой поток изменит значение по указателю ptr
           // на некоторое ненулевое число
           while (*ptr == 0) { }
          
           return 0;
          }
          Читать дальше →
        • Мой любимый файл в кодовой базе Chromium

            Код Хромиума весьма обширен, там каждому найдётся что-то по вкусу. А я вот решил рассказать о своём любимом файле в нём (а у вас есть такой?). Этот файл отражает всё: боль, разочарование, надежду, упорство, силу воли, ответственность за чужие провалы и самопожертвование. Я иногда читаю его и плачу и проникаюсь пониманием, какая же огромная часть айсберга скрыта под водой. Это, в общем, даже не файл с кодом. Это файл с конфигом, описывающим баги видеокарт, которые Хромиуму приходится обходить для нормального отображения своих страниц на разных платформах. Вот он: https://cs.chromium.org/chromium/src/gpu/config/gpu_driver_bug_list.json

            О чём вообще идёт речь? Давайте вспомним, как работает браузер: вы набираете какой-то адрес в адресной строке, браузер загружает контент и отображает его. Чуть детальнее об этом рассказывает хорошая статья «What happens when you type google.com into your browser and press enter?» (и сразу несколько её переводов на Хабре). В ней одним из последних пунктов упоминается, мол, «а теперь, когда всё готово, отрисовываем картинку на экране». Ага, вот так берём и отрисовываем, конечно.
            Читать дальше →
          • Не пытайтесь предугадать завтрашние проблемы

            • Перевод
            Ну или начните делать это правильно.

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

            «Нам нужно реализовать решение {Х}, несмотря даже на то, что есть значительно более простое и подходящее нам сейчас решение {Y}, ведь когда в будущем произойдёт {Z}, то {X} сработает гораздо лучше, чем {Y}».

            При этом точной информации о вероятности наступления события {Z} нет и быть не может.

            Вот пара примеров:

            • Нам нужно использовать kubernetes и docker! Да, с текущей нагрузкой отлично справляется один сервер и его легко настроить и поддерживать, но ведь когда нам нужно будет дюжина серверов — будет легче их разворачивать с kubernetes и docker.
            • Нам нужна архитектура распределенной обработки данных! Да, пока со всем справляется один средненький ПК, но когда у нас будет решение промышленного уровня и заказчики потребуют аптайм в пять девяток в SLA — мы будем к этому готовы.
            • Нам нужно нанять команду разработчиков и создать сайт с нуля, не смотря на то, что значительно быстрее было бы развернуть что-то на базе wordpress, ведь когда у нас будет в 100 раз больше клиентов, чем сейчас, то wordpress станет не так удобен.
            • Нам нужно использовать наследование вместо композиции, ведь через 5 лет кодовая база разрастётся так, что без этого будет никак.
            • Нам нужно написать вот этот код на С++, не смотря на то, что на Python это будет в разы быстрее, ведь спустя годы он будет обрабатывать терабайты данных и Python может здесь не справится.

            Недавно я писал статью о воображаемых проблемах — тех, решением которых люди развлекают себя, ведь их решать интереснее, чем реальные. Сюда же можно отнести и вот эти попытки предвидеть будущее. Даже можно сказать больше — это любимая воображаемая проблема большинства маленьких начинающих компаний.
            Читать дальше →
          • Когда не нужно использовать алгоритмы из STL

            • Перевод
            Я боролся с соблазном назвать статью как-то типа «Ужасающая неэффективность алгоритмов STL» — ну, знаете, просто ради тренировки в мастерстве создания кричащих заголовков. Но всё же решил оставаться в рамках приличий — лучше получить от читателей комментарии по содержанию статьи, чем негодование по поводу её громкого названия.

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

            Алгоритмы


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

            Каждый раз, когда вам хочется написать очередной for — следует сначала вспомнить, нет ли в STL (или в boost) чего-то, что уже решает эту задачу в одну строку. Если есть — чаще лучше использовать это. Нам, однако, и в этом случае следует понимать, что за алгоритм лежит за вызовом стандартной функции, каковы его характеристики и ограничения.

            Обычно, если наша проблема в точности совпадает с описанием алгоритма из STL, будет хорошей идеей взять и применить его «в лоб». Беда только в том, что данные не всегда хранятся в том виде, в котором их хочет получить реализованный в стандартной библиотеке алгоритм. Тогда у нас может возникнуть идея сначала преобразовать данные, а потом всё же применить тот же алгоритм. Ну, знаете, как в том анекдоте про математика «Затушить огонь из чайника. Задача сведена к предыдущей».
            Читать дальше →
            • +14
            • 7,2k
            • 4
          • Основы работы с фьютексами

            • Перевод
            Фьютекс (futex — сокращение от «Fast userspace mutex») — это механизм, предложенный разработчиками Linux из IBM в 2002 году и вошедший в ядро в конце 2003 года. Основной идеей было предоставить более эффективный способ синхронизации пользовательских потоков с минимальным количеством обращений к ядру ОС.

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

            Важный момент: фьютексы — это достаточно низкоуровневый инструмент, напрямую его использовать стоит лишь при разработке фундаментальных библиотек, вроде стандартной библиотеки C/C++. Очень маловероятно, что вам понадобится использовать фьютексы в обычном прикладном приложении.
            Читать дальше →
            • +30
            • 8,4k
            • 2
          • Воображаемые проблемы — корень плохого ПО

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

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

            История о подкастах


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

            И вот вы решаете нанять людей, которые сделают для вас этот сайт. Вы пишете для них абсолютно чёткие требования:

            • Быстрая загрузка сайта в Северной Америке
            • Поддержка загрузки прошлых выпусков подкастов и трансляции в реальном времени текущих
            • Трансляция не должна падать или замирать в течении первых 15 минут для 99.99% пользователей. Желательно вообще никогда, но хотя бы так.
            • Интеграция с Google Adwords (а в будущем, возможно, и с аналогами)
            • Интеграция с трансляциями Facebook, поскольку там вы проводите свои передачи. Если можно создать альтернативное решение, которое будет позволять стримить более удобно — ещё лучше.

            Вы даёте эти требования разработчикам и, возможно, немного общаетесь с ними. Проходит 2 месяца. Они показывают вам демо и вы покрываетесь красными пятнами. Становится понятно, что вы только что выбросили в пропасть 15 000 $. То, что вам показали, совершенно неприемлемо ни с какой стороны, просто куча мусора. Вы хотите назад свои деньги, но поезд уже ушел.
            Читать дальше →
          • epoll и Windows IO Completion Ports: практическая разница

              Введение


              В этой статье мы попробуем разобраться чем на практике отличается механизм epoll от портов завершения (Windows I/O Completion Port или IOCP). Это может быть интересно системным архитекторам, проектирующим высокопроизводительные сетевые сервисы или программистам, портирующим сетевой код с Windows на Linux или наоборот.

              Обе эти технологии весьма эффективны для обработки большого количества сетевых соединений.

              Они отличаются от других методов по следующим пунктам:

              • Нет ограничений (кроме общих ресурсов системы) на общее количество наблюдаемых дескрипторов и типов событий
              • Масштабирование работает достаточно хорошо — если вы уже мониторите N дескрипторов, то переход к мониторингу N + 1 займёт очень мало времени и ресурсов
              • Достаточно легко задействовать пул потоков для параллельной обработки происходящих событий
              • Нет никакого смысла использовать при единичных сетевых соединениях. Все преимущества начинают проявляться при 1000+ соединений

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

              (Upd: данная статья — перевод)

              Читать дальше →
            • select / poll / epoll: практическая разница

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

              В этой статье мы рассмотрим:

              • select()
              • poll()
              • epoll()
              • libevent
              Читать дальше →
            • Психология читабельности кода

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

              Каждый программист старается писать хороший код. Читабельность — один из главных признаков такого кода. О ней написано достаточно много книг, но всё же в теме есть пробелы. Например, те самые книги сфокусированы больше на советах КАК написать читабельный код, а не на причинах того, почему один код является хорошо читабельным, а другой — нет. Книга говорит нам «используйте подходящие названия переменных» — но что делает одно название более подходящим, чем другое? Работает ли это для всех примеров подобного кода? Работает ли это для всех программистов, которым попадётся на глаза этот код? Как раз о последнем я и хотел бы поговорить чуть детальнее. Давайте погрузимся немного в человеческую психику. Наш мозг — главный наш инструмент, хорошо бы изучить специфику его работы.
              Читать дальше →
            • Портируем код с Qt 1.0 на Qt 5.11

              • Перевод
              Недавно вышел Qt 5.11 и мне подумалось, что сейчас самое время обновить до него кое-какие мои проектики на Qt 1.0… Ладно, шучу :) На самом деле мне стало интересно, насколько хорошо за все эти годы развития фреймворка Qt нам удавалось сохранять обратную совместимость кода.

              Qt гарантирует совместимость на уровне кода и бинарников при обновлении между минорными версиями фреймворка (и мы серьёзно относимся к этому обещанию). Вы не должны переписывать (или даже перекомпилировать) свой код при переходе на другую минорную версию Qt. Однако переходы между мажорными версиями требовали от нас идти на некоторые жертвы ради прогресса. С релиза Qt 1.0 в 1996 году мы ломали совместимость кода четыре раза: в версиях 2.0, 3.0, 4.0 (ох, это было болезненно!) и 5.0.

              Мы старались даже в мажорных версиях сломать как можно меньше всего, но всё же это приходилось делать. Отсюда возникает вопрос: насколько сложно портировать приложение, написанное во времена Qt 1.0 до современного Qt 5.11?

              Для ответа на этот вопрос я взял пример кода, который поставлялся с документацией на Qt 1.0 и постарался собрать его с помощью Qt 5. Наши публичные архивы содержат изменения начиная с версии 1.41, так что мне пришлось изрядно покопаться в дрейнейшей истории, пройти через логи четырёх разных систем контроля версий… но это я уже отвлекаюсь. Проект, который я планирую собрать, называется «t14» — поскольку это иллюстрация к 14-ой (и последней) главе оригинального руководства.

              И вот, что мне пришлось проделать для его сборки.
              Читать дальше →
            • Полное руководство по стратегии обнаружения изменений Angular onPush

              • Перевод

              image


              Default cтратегия обнаружения изменений


              По умолчанию Angular использует ChangeDetectionStrategy.Default стратегию обнаружения изменений.


              ChangeDetectionStrategy.Default работает таким образом, что каждый раз, когда что-то меняется в нашем приложении, в результате различных пользовательских событий, таймеров, XHR, промисов и т.д., обнаружение изменений будет запускаться по всем компонентам.

              Читать дальше →
              • +19
              • 8,6k
              • 3
            • Сделаем Windows медленнее! Часть первая: файловый доступ

              • Перевод
              imageОС Windows долгое время попрекали за медлительность её файловых операций и медленное создание процессов. А почему бы не попробовать сделать их ещё более медленными? Эта статья покажет способы замедления файловых операций в Windows примерно в 10 раз от их нормальной скорости (или даже больше), причём способы эти практически не поддаются отслеживанию обычным пользователем.

              А ещё, конечно же, мы научимся подобные ситуации обнаруживать и исправлять. Весь текст написан на основе проблемы, с которой я столкнулся пару месяцев назад, так что всё, написанное ниже, полностью реально.
              Читать дальше →
              • +70
              • 38,7k
              • 9
            • Как передать полиморфный объект в алгоритм STL

              • Перевод
              Как мы можем прочесть в первой главе книги Effective C++, язык С++ является по сути своей объединением 4 разных частей:

              • Процедурная часть, доставшаяся в наследство от языка С
              • Объектно-ориентировання часть
              • STL, пытающийся следовать функциональной парадигме
              • Шаблоны

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

              image
              Читать дальше →
              • +32
              • 8,3k
              • 8
            • Property Injection своими руками (Xamarin/.Net)

                В данной статье мы рассмотрим, чем отличается Property Injection от Constructor Injection и реализуем первое в дополнение к последнему на базе небольшого DI-контейнера в исходниках.

                Это обучающий материал начального уровня. Будет полезен тем, кто ещё не знаком с DI-контейнерами или интересуется, как оно устроено изнутри.
                Читать дальше →
                • +10
                • 3,3k
                • 5

              Самое читаемое