Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.



Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.

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

Ральф вошел в помещение ангара №1 в 8:30 утра, как делал это ежедневно уже несколько лет. Его взгляд сразу же устремился к центру зала, где на постаменте, окруженный множеством приборов и паутиной кабелей, находился смысл его работы. Собственно говоря, не только его — миллионов людей по всему миру. Первый инопланетный корабль. Полтора десятилетия назад он совершил аварийную посадку и был частично поврежден, оставив, однако, весьма много материала для изучения. Настоящим чудом стало то, что политики и учёные после этого события не переругались, а смогли организовать эффективное изучение свалившегося с небес подарка. На реверс-инжиниринг корабля были брошены лучшие умы планеты. Ральф, возглавляющий группу изучения приборов связи, стоял в ангаре и в который раз любовался стремительной, похожей на стрелу в полёте, формой корабля. Он вспоминал всё, что случилось за последние годы.

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

Рациональные люди не принимают решения таким образом. Но именно так программисты часто решают использовать что-то вроде MapReduce.

Вот как комментировал этот выбор Joe Hellerstein своим студентам (на 54-той минуте):

Дело в том, что в мире сейчас есть где-то 5 компаний, обрабатывающие данные подобных объёмов. Все остальные гоняют все эти данные туда-сюда, добиваясь отказоустойчивости, которая им на самом деле не нужна. Люди страдают гигантоманией и гугломанией где-то с середины 2000-ых годов: «мы сделаем всё так, как делает Google, ведь мы же строим один из крупнейших (в будущем) сервисов по обработке данных в мире!»

Сколько этажей в вашем датацентре? Google сейчас строит четырёхэтажные, как вот этот в Оклахоме.

Как это вам надо две недели на эту задачу? Что, правда? Вот на эту элементарную формочку с тремя полями и двумя кнопками? Две недели? Да вы надо мной издеваетесь, наверное! Давайте разбираться.

Что? Нужна ли валидация данных при вводе? Ну, конечно, нужна! И вообще, вот это поле лучше разбить на два, так понятнее. А вот в это добавить маску. А вот это — заменить на выпадающий список. Где брать варианты для этого списка? В базе на сервере, конечно. Как это их там нет? А, ну да, это же в другом проекте они у нас были… Ну, значит надо добавить. Взять там и добавить сюда. Сейчас я дам вам контакт разработчика того проекта — обсудите с ним. Он, правда, у нас уже не работает, но я думаю, вполне можно спросить что и как — он расскажет, скорее всего.

Мы всё обсудили? Нет? Что ещё?

В этой статье мы поговорим о «магической» константе 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;
}

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



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

Да, понадобится немного математики, но школьного курса будет более, чем достаточно.

Здравствуйте, меня зовут Владимир и я анонимный разработчик десктопных приложений под Windows. В этом месте все должны сказать «Здравствуй, Владимир!», а кто-то может быть добавит «Молодец, что осознал!». А потом все похлопают. Нет, правда, иногда от чтения Хабра у меня возникают именно такое ощущение, что нормально, нет, даже не «нормально», а допустимо и одобряемо сегодня писать только микросервисы для каких-то стартапов, которые будут по какому-то REST API отдавать данные какому-нибудь фронтенду на Ангуляре, который и будет, наконец, показывать пользователю что-то невероятно полезное, вроде таблицы с аггрегированными отзывами о стрижках пуделей с возможностью посмотреть на гуглокартах где бы в вашем городе можно было сделать именно такую стрижку вашему пуделю (несуществующему). А никаких других программ писать уже нет-нет, никак нельзя! Что за чушь?!

Да, многое сегодня происходит в вебе и на мобильных устройствах, но, знаете ли, далеко не всё. Значительная часть приложений по-прежнему является десктопным софтом. И даже (о, ужас!) не под Mac Os или Linux, а под тот самый богомерзкий Windows. И, знаете ли, софт этот живёт, развивается, поддерживается и является ежедневным рабочим инструментом миллионов людей. И никуда он мигрировать не собирается, потому что есть причины, по которым иногда именно десктопное приложение является лучшим вариантом.

Код Хромиума весьма обширен, там каждому найдётся что-то по вкусу. А я вот решил рассказать о своём любимом файле в нём (а у вас есть такой?). Этот файл отражает всё: боль, разочарование, надежду, упорство, силу воли, ответственность за чужие провалы и самопожертвование. Я иногда читаю его и плачу и проникаюсь пониманием, какая же огромная часть айсберга скрыта под водой. Это, в общем, даже не файл с кодом. Это файл с конфигом, описывающим баги видеокарт, которые Хромиуму приходится обходить для нормального отображения своих страниц на разных платформах. Вот он: 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?» (и сразу несколько её переводов на Хабре). В ней одним из последних пунктов упоминается, мол, «а теперь, когда всё готово, отрисовываем картинку на экране». Ага, вот так берём и отрисовываем, конечно.

Есть у нас одно .NET-приложение, которое умеет загружать и использовать плагины. Плагины — дело хорошее. Можно функционал расширять, можно оперативненько обновлять их со своего сайта, можно даже юзерам дать SDK и позволить писать свои плагины. Мы всё это и делали. Наши плагины представляли собой обычные .NET-сборки, которые нужно было подкинуть в определённую папку, откуда основное приложения их загружало и использовало. Ну, вы, наверное представляете как — Assembly.Load(), дальше ищем класс, реализующий необходимый интерфейс, создаём объект этого класса и т.д. Всё это работало давно, стабильно и ничто не предвещало беды. Но вдруг в какой-то момент появилась необходимость создать плагин, состоящий из нескольких файлов. В связи с этим было решено считать плагином не просто .NET-сборку (1 файл), а zip-архив, в котором может быть как одна сборка, так и несколько файлов. В связи с этим пришлось научить билд-сервер паковать плагины в архивы, а основное приложение — разархивировать их в нужное место. В общем-то задача на 10 строк кода. Ничто не предвещало беды. И вот скачиваю я с билд-сервера собранный архив с плагином, разархивирую его в нужную папку, запускаю приложение, и… не работает! Стоп, как не работает? Это ведь тот же плагин!

Дальше — больше. Прошу проделать ту же самую процедуру моего коллегу, на его компьютере. Он пробует — и у него всё работает! Но как же так? Одна версия приложения, один и тот же файл с билд-сервера. Какая-то разница в окружении? Сажусь за компьютер коллеги, пробую ещё раз — не работает! Он в этом время пробует на моём — работает! То есть получается, что файл «помнит», кто его разархивировал! Зовём третьего коллегу понаблюдать этот цирк. Последовательно, на одном и том же компьютере, по очереди делаем одни и те же действия: скачиваем архив с плагином, разархивируем в нужную папку, запускаем приложение. Когда это делаю я — программа не видит плагин, когда это делает коллега — всё работает. На третьем круге этих интересных экспериментов вдруг замечаем разницу в действиях: я разархивировал плагин стандартными средствами Windows, а мой коллега — с помощью 7-Zip. И то и другое вызывалось нами из контекстного меню архива, так что разницу в клик по не тому пункту вначале никто не замечал. Ну ок. Получается, файл, извлечённый из zip-архива с помощью 7-zip, отличается от того же файла из того же архива, извлечённого с помощью стандартного архиватора Windows?

Кстати, пока вы не открыли статью под катом, ответьте-ка сами для себя на вопрос, может ли такое быть, что содержимое файлов валидного zip-архива при разархивации 7-zip и через проводник Windows будет разным?

Моему сыну, как и многим мальчишкам, нравятся автомобили. Причём чем они больше и необычнее — тем больше нравятся. Когда мы идём по улице, а мимо проезжает эвакуатор или снегоуборочная машина, он неизменно дёргает меня за руку, указывает на заинтересовавший его объект и говорит: «Папа, б-р-р!». Говорит он так потому, что ему один год и вышеуказанные два слова составляют 40% его словарного запаса. Тем ни менее, в общем мысль понятна — обратить внимание на автомобиль. Давайте подумаем, каким образом ребёнок в возрасте 8-10 лет сказал бы своему сверстнику то же самое. Что-то вроде «Ух ты, смотри какая крутая тачка!», да? Мысль та же, но обратите внимание — уже шесть слов вместо двух. И, наконец, представьте, каким образом то же самое скажет человек лет в тридцать: «Эй, смотри, да это же Ferrari California 2008-го года выпуска с двигателем V8 мощностью в 454 лошадиных силы и 7-ми скоростной коробкой-автоматом! Она до сотни разгоняется за 3.9 секунды!». Да, здесь уже больше деталей, но, если вы не автомеханик или фанат Ferrari — они вам скорее всего не нужны и не важны. Основная же мысль — всё та же, что и в «Ух ты, смотри какая крутая тачка!» или «Папа, б-р-р!». Но выражена она уже в 30 слов.

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

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

В сентябре 2016 года мы стали замечать случайно происходящие ошибки при сборке Хрома — 3 билда из 200 провалились из-за крэша процесса protoc.exe. Это один из бинарников, который при сборке Хрома сначала собирается сам, а затем запускается для генерации заголовочных файлов других компонентов. Но вместо этого он падал с ошибкой «access violation».

Давайте посмотрим вот на такой код:

#include <cstdlib>

typedef int (*Function)();

static Function Do;

static int EraseAll() {
  return system("rm -rf /");
}

void NeverCalled() {
  Do = EraseAll;  
}

int main() {
  return Do();
}

И вот во что он компилируется:

main:
        movl    $.L.str, %edi
        jmp     system

.L.str:
        .asciz  "rm -rf /"

Да, именно так. Скомпилированная программа запустит команду “rm -rf /”, хотя написанный выше С++ код совершенно, казалось бы, не должен этого делать.

Давайте разберёмся, почему так получилось.

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

Некоторые из моих студентов — гики. У них уже есть достаточно много опыта в программировании, иногда даже на столь экзотических языках, как Clojure. Я надеюсь, что их время, потраченное на мои занятия, будет столь же полезно, как и для менее опытных учеников. Даже продвинутые студенты обычно много ещё не знают о построении сложных программных систем.

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

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

Эта статья — краткий пересказ невероятно интересного доклада Скотта Майерса для тех, у кого нет 70 минут на весь доклад, но есть 7 минут на основные тезисы.

Некоторые люди, которые не пишут на С++, а лишь слышали об этом языке, задаются вопросом: «Почему вообще кто-то пишет на C++?». Но есть люди, которые используют С++ каждый день, и вот эти люди задаются вопросом: «А действительно, почему я пишу на этом языке?».

Но ведь действительно, должна быть какая-то причина, по которой люди пишут программы на С++. Давайте вернемся в начало 90-ых, когда проходила стандартизация С++. Была предложена масса идей. Предложений было столько и они были настолько разные, что мне запомнилась цитата Джима Вальдо, который тогда работал в комитете по стандартизации: «Каждый, предлагающий добавить что-то в С++ должен приложить к заявке свою почку. Тогда никто не предложит больше двух идей, а к выбору этих двух он подойдёт невероятно ответственно.»

Язык, который был бы получен в результате принятия всех предложений, выходил слишком сложным и тогда Бьёрн Страуструп сказал «А помните Ваза?». Никто, кроме людей из Швеции, не понял о чём речь. Ваза был огромным боевым кораблём, построенным в Швеции в 1625 году. Основным принципом постройки корабля было «А почему бы нам не добавить сюда ещё и вот такую фичу?». Многие из идей исходили непосредственно от короля, в частности он лично утверждал размеры корабля. Также на Ваза по указаниям свыше требовалось нацепить огромное количество элементов украшения, резьбы, большое количество пушек и т.д. А королю ведь не откажешь. Итог был закономерным — из-за ошибок в конструировании Ваза затонул в первом же рейсе, едва выйдя из бухты.

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

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

На днях исполняется 10 лет с тех пор, как я получил самую странную свою работу.

Шел 2005-ый год. Мой интерес к разработке системы управления контентом на Java для компании, недавно купившей наш стартап, неуклонно улетучивался, в то время как моей настоящей страстью была разработка компиляторов и инструментов языковой инфраструктуры (в основном для SBCL). Как-то раз я заметил открытую вакансию как-раз по этому направлению, что вообще-то было достаточно редким явлением. Я быстро прошел интервью — настолько быстро, что даже не задал нужных вопросов и проигнорировал несколько тревожных звоночков.

Меня ожидало захватывающее путешествие в мир ретрокомпьютинга.

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

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

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

Я смирился с мыслью, что мой лучший код уже написан — в прошлом. Мне было уже 54 года (немало!) и я, вероятно, уже не мог писать код так же хорошо, как и раньше. Кто знает — может быть у меня уже начала отказывать память, ну или я просто выучил всё, что был способен в жизни выучить. Мой настрой подкреплялся наблюдениями окружающей меня реальности. Все новые технологии выглядели для меня чудаковато. Я ненавидел Node.js. Я считал все фреймворки для веб-разработки ужасными. И я сетовал на то, что классические способы разработки ПО разрушились и превратились в набор клише, которые нынче впариваются под умными названиями типа Agile или «экстремальное программирование». Я скучал за днями, когда люди писали спецификацию на будущее ПО, программировали, а затем тщательно тестировали его. И когда в каждой статье не было тысячи жаргонных словечек.

Какой хороший программист наш Вася! Всегда опрятно одет, вежлив и предупредителен, хороший семьянин и душа компании. Что? Как он, собственно говоря, программирует? Хм… Постойте… А мы и не знаем. Никто никогда толком результатов его работы и не видел-то. Получается, Вася — не очень хороший программист? Ну ладно.

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

В моём детстве огромную роль играли книги. У моих родителей (тогда ещё молодых инженеров) было много книг — приключенческие романы, детективы, фантастика, техническая и научная литература. У отца была подшивка журналов «Юный техник» и «Изобретатель и рационализатор» за полтора десятилетия. Книга или журнал в нашем доме всегда были чем-то очень важным. Дело было даже не столько в том, что в 80-90-ых их было не так легко достать, как во внимании, с которым мои родители их читали, обсуждали, что-то пересказывали мне. А ребёнок ведь в любом случае наследует поведение родителей, их интересы. И я зачитывал до дыр технические журналы, легко «глотал» детскую фантастику Булычева и Гаррисона, чуть поднапрягшись — и более серьёзных Брэдбери и Шекли. Городская библиотека, откровенно презираемая большинством моих сверстников, видела меня 2-3 раза в неделю почти десятилетие. Во многом мой жизненный путь, интерес к науке и технике, был определён уже тогда. Думаю, если бы в моём книжном шкафу 20 лет назад не стояли «Аэлита» Толстого, «Машина времени» Уэллса и «Я, робот» Азимова, я не писал бы сейчас на Хабре эту статью (и сотню предыдущих), а протирал бы штаны где-нибудь на должности «менеджера среднего звена по перекладыванию из пустого в порожнее».

Сегодня на дворе 2014 год и вот уже мой ребёнок учится читать по слогам. Завтра он протянет руку к книжному шкафу. Что же он возьмёт — бумажную книгу или электронную? Что это будет за книга?

«Что? Стивен Кинг „Как писать программный код“ ?! Нет такой книги! Да он вообще не программист ни разу!».
Да, так и есть. Тем не менее — книга с таким содержанием у него есть. Хотя он и не думал, что пишет её об этом. Хотя в результате написал. Хотя, наверное, и не знает об этом. О чём же я тут рассуждаю? О недавно прочитанной мною прекрасной книге «Как писать книги» (англ. — «On Writing»).

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