Сортировки слиянием работают по такому принципу:

1. Ищутся (как вариант — формируются) упорядоченные подмассивы.
2. Упорядоченные подмассивы соединяются в общий упорядоченный подмассив.

В 2010 году Патрик Маккензи написал знаменитую статью «Заблуждения программистов об именах», перечислив 40 фактоидов, которые не всегда верны в отношении человеческих имён.

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

Резервуарная выборка (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 элементов будет чётко соблюдено.

Наверное, все, работающие с Java, знают об управлении памяти на уровне, что для ее распределения используется сборщик мусора. Не все, к сожалению, знают, как именно этот сборщик (-и) работает, и как именно организована память внутри процесса Java.

DJI снова продолжает удивлять и радовать своими разработками. Полмесяца назад они отлично подогрели интерес к себе и своей продукции, разослав ведущим hi-tech изданиям приглашение на презентацию 28 ноября. В анонсе было указано только время и место проведения мероприятия, а также изображение со слоганом Because Life is Big! Аналитики и журналисты наперебой стали строить предположения, какой же продукт следует ожидать в конце месяца. Но, благодаря различным утечкам, со временем стало ясно, что в студии Good Morning America речь пойдет не о следующем поколении коптеров Phantom. Новым продуктом стала портативная, скорее даже карманная модель из линейки OSMO.

Очередная статья в серии «Инструменты мониторинга Logicify» рассказывает о Grafana. Это программное средство мы используем для визуализации и анализа данных как внутренних, так и внешних проектов. Статья может быть полезна техническим директорам, разработчикам, DevOps, системным администраторам, менеджерам проектов, а также всем заинтересованным лицам.

Месяц назад Лента запустила конкурс, в рамках которого та самая Говорящая Шляпа из Гарри Поттера определяет предоставивших доступ к социальной сети участников на один из четырех факультетов. Конкурс сделан неплохо, звучащие по-разному имена определяются на разные факультеты, причем схожие английские и русские имена и фамилии распределяются схожим образом. Не знаю, зависит ли распределение только от имен и фамилий, и учитывается ли как-то количество друзей или другие факторы, но этот конкурс подсказал идею этой статьи: попробовать с нуля обучить классификатор, который позволит распределять пользователей на различные факультеты.

Насколько я помню, в 70-80 годах лозунг «секс — двигатель рекламы» был невероятно притягателен. Было такое ощущение, что предметом общего согласия в рекламе был образ полуодетой красавицы, которую достаточно поставить перед неким продуктом и сфотографировать, после чего этот продукт разлетится как горячие пирожки. Это касалось джинсов, лосьонов после бритья, автомобилей, да всего чего угодно, щедро приправляемого двусмысленными образами, призванными вытягивать деньги из карманов альфа-самцов. Где-то этот приём использовался утончённо и элегантно, где-то — более грубо, пожалуй, найти можно самые разные примеры.

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

Всё это началось с игры Computer Space. Пожалуй, лучше всего начать наш разговор именно с неё, так как она была представлена первым игровым автоматом, получившим широкое распространение. Автомат выпустила в 1971 году компания Nutting Associates. Тогда явно чувствовалось, что для того, чтобы эту игру продавать, нужно немного гламура. В результате игровая индустрия, с самого начала, прибегала к услугам женщин-моделей для того чтобы привлечь внимание аудитории.

Кто хоть раз тестировал свой WebAPI знает такие инструемнты, как Postman или Advanced REST (экстеншены для Chrome). Эти инструемнты всем удобны, кроме того, что не умеют сами узнавать какие модели принимает API, какие отдает и не предоставляет информацию обо всех возможных эндпоинтах. Это неудобство решает пакет Swashbuckle, который встраивает в проект генерацию Swagger спецификации и UI. Под катом коротко о том, как его прикрутить к проекту и некоторые детали относительно авторизации и работы с «перегруженными» эндпоинтами.

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

Прим. перев.: Эта статья продолжает цикл материалов от технического писателя из Google, работающего над документацией для Kubernetes (Andrew Chen), и директора по software engineering из SAP (Dominik Tornow). Их цель — доступно и наглядно объяснить основы организации Kubernetes. В прошлый раз мы переводили статью про high availability, а теперь речь пойдет про такое базовое понятие в Kubernetes, как pod.



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

Pods (Поды) — базовые строительные блоки Kubernetes, однако даже опытные пользователи Kubernetes не всегда могут объяснить, что же это такое.

Данная публикация предлагает лаконичную мысленную модель, которая проливает свет на определяющие характеристики pod'ов Kubernetes. Ради этой краткости пришлось опустить некоторые другие особенности Pod'ов, такие как liveness и readiness probes, разделение ресурсов (включая появившееся недавно namespace sharing — прим. перев.), работу с сетью.

Разработка программ высокого качества подразумевает, что программа и её части подвергаются тестированию. Классическое модульное (unit) тестирование подразумевает разбиение большой программы на маленькие блоки, удобные для тестов. Либо, если разработка тестов происходит параллельно с разработкой кода или тесты разрабатываются до программы (TDD — test driven development), то программа изначально разрабатыватся небольшими блоками, подходящими под требования тестов.

Одной из разновидностей модульного тестирования можно считать propery-based testing (такой подход реализован, например, в библиотеках QuickCheck, ScalaCheck). Этот подход основан на нахождении универсальных свойств, которые должны быть справедливы для любых входных данных. Например, сериализация с последующей десериализацией должна давать такой же объект. Или, повторная сортировка не должна менять порядок элементов в списке. Для проверки таких универсальных свойств в вышеупомянутых библиотеках поддерживается механизм генерации случайных входных данных. Особенно хорошо такой подход работает для программ, основанных на математических законах, которые служат универсальными свойствами, справедливыми для широкого класса программ. Есть даже библиотека готовых математических свойств — discipline — позволяющая проверить выполнение этих свойств в новых программах (хороший пример повторного использования тестов).

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

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

От переводчика: Этот забавный репозиторий уже с неделю находится в трендах гитхаба, и сейчас у него фееричное количество из 5000 звёздочек и 400 форков — поэтому я подумал, что было бы интересно перевести про него статью, хотя она короткая, да и тематика для хабра не очень стандартная.
Если интересно, в оригинале статьи (ссылка около заголовка) есть ссылки на примеры работы программы.

Я всегда хотел написать подробное руководство для начинающих о том, как создать roguelike, содержащее как общие, так и более специфические советы. Проведённый в этом году очередной праздник Roguelike Celebration показался мне отличной возможностью наконец-то заставить себя это сделать, поэтому я подготовил получасовой доклад по этой теме.

У меня есть довольно большой опыт — в течение последних семи лет я работал только в этом жанре (Cogmind, Cogmind 7DRL, POLYBOT-7, REXPaint, X@COM), и в течение последних пяти эта работа была моей основной. К тому же, все эти годы я помогал превращению r/RoguelikeDev в крупнейшее сетевое сообщество разработчиков roguelike.

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

Это лишь немногие примеры, и они вполне типичные!

Мария Андерсон в роли Маленькой феи и её паж Любовь Рябцова в балете «Спящая красавица» в Императорском театре, Санкт-Петербург, Россия, 1890

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



Однако в цикле жизни любой компании есть период взрывного кадрового роста с поиском путей решения этой проблемы. Все вы знаете этот этап. Вот, вчерашний локальный продукт захватывает ощутимую долю рынка, аудитория кратно увеличивается и команда сталкивается с проблемами, о которых даже не подозревала. Как-то незаметно у руководителей отделов появляются «приемные часы» и согласование совещаний через почту, заметно разрастается HR-департамент, а времена, когда весь коллектив мог заказать десяток пицц по акции и устроить пятничные посиделки в офисе остались в прошлом. Владелец компании и по совместительству ее директор набирает 15-20 кило лишнего веса, все меньше появляется в коридорах и кабинетах, и все больше времени проводит в своем кабинете куда ему носит кофе личный секретарь, либо вовсе улетает на Кипр.

Вот как раз в этот момент компанию начинают захватывать «эффективные менеджеры».

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

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

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

Прим. перев.: Оригинальная статья была написана техническим писателем из Google, работающим над документацией для Kubernetes (Andrew Chen), и директором по software engineering из SAP (Dominik Tornow). Её цель — доступно и наглядно объяснить основы организации и реализации high availability в Kubernetes. Нам кажется, что у авторов получилось, поэтому мы рады поделиться переводом.



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

Kubernetes — масштабируемый и надёжный движок оркестровки контейнеров. Масштабируемость здесь определяется отзывчивостью в присутствии нагрузки, а надёжность — отзывчивостью в присутствии отказов.

Привет, Хабр. Под этим пафосным заголовком я бы хотел поговорить о том, что такое «инженерная наука», в чём состоит главная обязанность инженера и что бывает, если он с ней не справляется — мне кажется, в последнее время эта тема становится всё более актуальной, при этом её публичного обсуждения я не вижу.

Сподвигла меня на это разразившаяся (при моём активном участии) в минувшие выходные история с «нейроинтерфейсами» компании Bitronics Lab — детскими учебными наборами для снятия ЭЭГ и мышечной активности, которые при ближайшем рассмотрении оказались попросту небезопасны в использовании из-за несоблюдения их производителем базовых требований к электробезопасности медицинского оборудования.

История это очень показательна в том, что она демонстрирует, как по мере роста сложности система, составленная из кажущихся её авторам безопасными компонентов, становится опасной — причём на примере системы простой, бытовой и интуитивно понятной, а не атомного реактора или реактивного лайнера, которые любят брать в качестве примеров авторы книг вроде моей любимой "Inviting Disaster".

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

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



Казалось бы, что может пойти не так?

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

И конечно, статья также расскажет, как обнаружить и избежать этой проблемы.

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

• Замедляем Windows, часть 0: произвольное замедление VirtualAlloc
• Замедляем Windows, часть 1: файловый доступ