Don't hesitate

Записки @schmooser.

Франция 2014 — день 1 — Марсель

На самом деле сегодня уже 4-й день нашего путешествия по Франции, но я решил писать по заметке на каждый день и постепенно наверстаю пропущенные дни, пока воспоминания еще свежи.

Летели AirFrance’ом из Шереметьево в Марсель. Шереметьево, надо сказать, порадовал. Гораздо больше места и простора, чем в Домодедово. Новый терминал E, ничем не отличается от многих других европейских аэропортов. Все равно моим любимым московским аэропортом отстается уютное Внуково.

Из еды в самолете был непонятного вида салат из макарон, есть можно, но ничего необычного. Горячего не было. Зато было пиво Хайнекен и французское вино в бутылочках. В целом — ЭрФрансу зачет, все хорошо.

Надя еще при подлете увидела аэропорт Марселя, мы заходили на него справа. Аэропорт с воздуха видится просто как две ВВП, построек не видно совсем, поэтому мы сначала решили, что летим в другое аэропорт. Одна из полос выдается на несколько десятков метров прямо в море.

Из аэропорта доехали на автобусе, они ходят каждые 15 что-ли минут по 8€ за билет. Приехали на вокзал. Вокзал хороший, с одной стороны автобусная станция, с другой – поезда. В холле стоит фортепиано и каждый желающий может сесть и поиграть. Мы были там уже раза 3 и каждый раз кто-нибудь играл. Один раз это точно был пассажир (ребенок с бабушкой). Еще прямо внутри вокзала растут деревья. Да да, прямо под крышей. Первый раз такое вижу, это здорово.

Про Марсель говорят, что это грязный портовый город. Пока е могу сказать, правда это или нет, надо съездить в Париж для сравнения. Если Марсель и грязный, то только в смысле бытовых отходов. Да, пакеты, коробки от сигарет, упаковки бургеров из Макдональдса здесь валяются прямо на траве и под деревьями. Такого больше нигде в Европе я пока не видел. Грязи как в Москве после дождя тут, конечно, нет.

… tbc

Американское время

Американцы все-таки очень странные. Они единственные в мире, кто остался жить в имперской системе. Весь остальной мир уже давно живет в метрической системе. Напомню, имперская система, это та, в которой единицы измерения не кратны 10. Длина у американцев измеряется в футах и дюймах (1 фут = 12 дюймов, они же инчи, 1 дюйм это 2.54 см, длина 3-х ячменных зернышек). Расстояния — в милях (1 миля = 1280 футов), объемы жидкостей — в галлонах (1 галлон = 3.785 литра). На википедии есть отличная статья про историю измерений.

Хорошо хоть деньги (доллары которые) десятичные. Великобритания, из которой и пришла в США имперская система жила с шиллингами, пенсами и фунтами до 60-х годов, когда волевым решением все деньги поменяли на десятичные фунты и пенсы. Про переход на новые деньги был очень хороший подкаст — Listen to English - Old money, New money, послушайте. Там Питер Картер рассказывает, как в детстве они учили таблицы умножения денег, как называли монету в пол-шиллинга. Очень интересно.

old money new money

Примерно в то же время англичане и в расстояниях и весах перешли на десятичную систему.

Если построить карту стран, не использующих метрическую систему, то на ней окажутся только США, Бирма и Либерия.

metric system map adoption

Еще американцы используют 12-ти часовое время. AM до полудня, PM — после полудня. Вроде бы все легко. Но если попросить перевести в AM/PM скажем 00:30 ночи, то сделать будет довольно нелегко. Ответ — 12:30 AM. После 12:59 AM идет 01:00 AM. Ни разу не интуитивно. Точно также 12:59 дня (после идет 13:00) у американцев это 12:59 PM, а после идет 01:00 PM. Особенно странно, что 12:30 PM < 11:30 PM.

Нарисовал вот себе картинку:

12-day clock

Heartbleed bug

7 апреля стало известно про наличие уязвимости в библиотеке OpenSSL версий 1.0.1. Уязвимость позволяет взломать сайт, использующий HTTPS или у которого открыт SSH и увидеть пароли в открытом виде.

Эта версия была по-умолчанию установлена во множестве операционных систем с 2011-го года и использовалась в качестве библиотеки в популярных веб-серверах Apache и Nginx. Подробное описание на http://heartbleed.com.

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

Что надо сделать:

  1. Подробная информация размещена на http://heartbleed.com Нужно идти туда и делать, как там написано.

  2. На всех серверах, к которым вы имеете отношение, нужно обновить openssl. Официальная пропатченная версия — 1.0.1g, но некоторые (Red Hat, например — касается RHEL, CentOS, Fedora) выпустили заплатку в рамках текущей версии, 1.0.1e. Проверить версию можно так:

     $ openssl version -a
     OpenSSL 1.0.1e-fips 11 Feb 2013
     built on: Tue Apr  8 02:39:29 UTC 2014
     platform: linux-x86_64
    

    Если дата билда после 07.04.2014 (7-е или 8-е число), значит исправляли именно heartbleed bug. Подробности я нашел тут.

    На Mac OS X 10.9 Mavericks стоит OpenSSL 0.9.8y, он не содержит уязвимости.

    Также тут есть описание как спасаться.

  3. Читать в почте сообщения от сервисов, как они пропатчили свое ПО и делать что они скажут. В большинстве случаев они настоятельно рекомендуют сменить пароль от сервера. Некоторые написали, что им heartbleed нипочем, т.к. они использовали собственные имплементации протокола TLS. Для сервисов PaaS или SaaS (heroku, mongolab) нужно перегенерировать ssh-ключи.

  4. Поменять пароли и перегенерировать ssh-ключи. Это конечно та еще проблема — у меня для каждого сервиса уникальный пароль, генерируемый с помощью http://supergenpass.com и уникального же мастер-пароля. Придется сменить мастер-пароль и по очереди менять пароли на всех сервисах. Ключи тоже придется перегенерировать.

Эх, memory-лики…

белки-истерички

Числа Каталана и Map Reduce

Решая 15-ю задачу с ProjectEuler наткнулся на числа Каталана. В задаче предлагается найти количество путей в решетке размерности 20х20.

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

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

catalan

Когда я начал делать расчет центрального биномиального коэффициента для n=20, пришлось писать функцию факториала. Способов написать функцию факториала несколько, влоб - это рекурсия:

fact 1 = 1
fact n = n * fact (n-1)

Но есть более простой способ — факториал это свертка массива [1..n] с помощью функции умножения:

fact n = foldr (*) [1..n]

Вообще, в функциональном программировании очень часто делают свертку массивов с помощью какой-то функции чтобы получить конечное значение. И тут меня осенило — функция foldr Хаскелля на Питоне называется reduce. Если бы мы вычисляли не факториал, а скажем, сумму квадратов чисел в массиве, то код был бы немного другим:

sumSquared xs = foldr (+) $ map (^2) xs

Мы сначала применили одну функцию ко всем элементам массива (map), а затем свернули эти значения в одно с помощью функции свертки (reduce). Вот мы и получили глубинный смысл технологии MapReduce. Только там “мапим” по узлам кластера, а затем сворачиваем на каком-то другом узле. Но базовый принцип — такой.

Матричные вычисления

Сейчас прохожу курс Machine Learning на Coursera, даже писал небольшие конспекты по нему, но потом забросил — есть отличная wiki, где дается краткое содержание лекций, есть слайды. Описывать все довольно муторно, к тому же надо подбирать русские эквиваленты американских терминов, а в случае технической литературы меня почти всегда коробит от русскоязычного перевода. Поэтому, я стараюсь читать техническую литературу только на английском.

Так вот, домашнее задание на курсе надо выполнять на Octave или MATLAB. В студенчестве я ставил MATLAB и пытался с ним поиграться. Но т.к. там вообще нет никаких символьных вычислений, а мне нужны были именно они, я так и не нашел применение матлабу и забросил его изучение и разбирался в Maple, Mathematica и Mathcad. Сейчас же, поигравшись с Матлабом, я понимаю, насколько это крутая штука.

В случае машин-лернинга когда имеем дело с supervised learningом, т.е. есть обучающий набор данных, весь этот набор можно представить как матрицу, где строки это значения обучающего набора (факты), а столбцы - “features”, т.е. штуки, от которых зависит результат.

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

Теперь я понимаю всю силу линейной алгебры. Как жаль, что нам в ВУЗе не объясняли приложений к реальным задачам. Понимаю, что прослушал некоторые курсы бы еще раз с удовольствием.

КПЗ “матрица друг человека”

ProjectEuler

В посте Am I really a developer or just a good googler? для проверки своих способностей советуют порешать задачки на сайте ProjectEuler.

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

Первые несколько штук достаточно простые и решаются прямо “влоб” простым перебором. Дальше посложнее, пришлось писать “эффективную” функцию расложения числа на множители, решето Эратосфена. Очень порадовала реализация на Хаскелле через zip всевозможных “найти максимальное произведение 5 последовательных цифр 1000-значного числа” или “найти максимальную сумму 4-х соседних чисел в матрице”.

При написании часто смотрю в код Prelude Хаскелля. Например, написав свой метод расчета НОК и НОД (довольно простой, подсмотрел в Википедии), посмотрел как сделано в Prelude — написано очень красиво. Также очень красиво реализованы почти все функции. Про это напишу отдельный пост.

Задачу 25, где нужно найти номер первого числа Фибоначчи из 1000 цифр, я вообще пытался решить аналитически, затем разработал методику, позволяющую итерировать без увеличения разрядов. В итоге, так и не смог написать на Хаскелле, написал на Питоне. После посмотрел как решают другие — решение на Питоне занимает ровно 4 строки в элементарном цикле, мое же — 3 или 4 функции и около 70 строк кода.

Продолжаю решать задачи.

pavel popov