?

Log in

No account? Create an account

dfyz


Иван Комаров

Colorless green ideas sleep furiously


Про #cryptoclass
dfyz
Мне кажется, курс Crypto I стоит прослушать всем программистам. Вот прям вообще всем. Криптография – это такая математикоёмкая (есть такое слово?) область, типа сжатия данных или формальных языков, с которой каждый программист-практик столкнётся в жизни хотя бы раз. Вот только, в отличие от сжатия данных, цена ошибки из-за плохого понимания предметной области здесь может быть намного, намного выше.

Что можно узнать из курса:
0. (самоочевидное) Если вам вдруг по какой-то причине захочется реализовать какие-нибудь криптографические примитивы для продакшен-системы самостоятельно, немедленно убейте себя об стену, мир станет лучше и добрее. У вас будет замечательный шанс наступить на одни из мириадов граблей, про которые вы даже не подозревали, и протерять все полимеры.
1. При этом если вы используете стандартные криптографические библиотеки, но плохо понимаете, как их надо применять (например, считаете, что шифрование AES'ом со случайным ключом решит все ваши проблемы, или хешируете пароли с помощью SHA-256), то шансов встретиться с граблями и расстаться с полимерами у вас ничуть не меньше.
2. Совершенно непонятно, почему кто-то ещё использует CBC вместо более других режимов шифрования.
3. Padding oracle attacks – забавная и красивая штука, которая как нельзя лучше иллюстрирует пункт 0.
4. RSA кажется очень простым, но его сложно приготовить правильно, есть десятки неочевидных тонкостей (см. пункт 0 про полимеры).
5. В английском языке есть слово "squeamish".
6. В языке программирования Питон из коробки есть возведение в степень по модулю, чего достаточно для реализации MITM-вычисления дискретного логарифма в Z_n.
7. Роль теории чисел в криптографии с открытым ключом сильно преувеличена.
8. И многое другое.

В бой идут одни старики
dfyz
Я понял, что очень скучаю по командным ACM-тренировкам втроём и этому непередаваемому ощущению, когда ты с разбегу зарываешься в стопку задач и выползаешь на поверхность через пять часов непрерывного мозгового штурма, измочаленный, запыхающийся, но довольный. При этом я совсем не скучаю по самим ACM-контестам, которые, на мой дилетантский взгляд, давно уже выродились в странный спорт ради спорта. Поэтому в субботу мы играем IPSC сборной командой из лучших поисковиков мира. :-) Задачи в этом соревновании с первого взгляда похожи на ACM, но на самом деле они в сто раз интереснее и в миллион раз разнообразнее.

И да, если вы собираетесь участвовать в каком-нибудь интернет-соревновании (не ACM, не МММ) командой не больше чем в три человека, зовите меня, пожалуйста. Мне особенно интересно было бы попробовать что-то вроде http://web-ngram.research.microsoft.com/spellerchallenge/, от которого мы c vadimmer в своё время получили немало удовольствия.

Я просто разместил объяву
dfyz
Хотите поучаствовать в DefCON вместе с sharpc и _denplusplus_? Вам сюда: https://www.facebook.com/vadim.kantorov/posts/10201288323555023

Материалы к докладу на DUMP-2013
dfyz
Слайды презентации.

Статьи
Мини-статья с обзором различных подходов к приближённому подсчёту.
Исходная статья 1985 года (алгоритм PCSA, про который я рассказывал).
Развитие темы: алгоритм LogLog 2003 года (рекомендуется сразу читать про его улучшенную версию с гармоническим средним вместо арифметического, которая называется HyperLogLog).

Посты в блогах
http://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/
http://blog.aggregateknowledge.com/2013/04/02/sketch-of-the-day-probabilistic-counting-with-stochastic-averaging-pcsa/
http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/

Некриптографические хеш-функции
http://en.wikipedia.org/wiki/MurmurHash
http://en.wikipedia.org/wiki/CityHash
http://en.wikipedia.org/wiki/Jenkins_hash_function#SpookyHash


Java-библиотека с реализацией этих (и многих других алгоритмов)
https://github.com/clearspring/stream-lib

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

NLP на Coursera
dfyz
От всей души рекомендую курс по Natural Language Processing за авторством Michael Collins. Это лучший курс из тех, что я проходил на Coursera (ладно-ладно, помимо NLP, я прошёл всего один другой курс, но NLP правда выше всяких похвал).

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

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

Помимо теоретических тестов, есть несколько заданий на программирование (нахождение генов в тексте, синтаксический разбор и сопоставление слов для машинного перевода), с которыми, увы, получилось не очень здорово: для получения максимального балла обычно достаточно просто реализовать то, что просят, и стимула улучшать своё решения, пытаясь выбить максимальные полноту/точность, нет. Я, впрочем, компенсировал это тем, что развлекался, экспериментируя с разными ЯП. Первое задание я сделал на Go, второе – на Haskell, третье – на D, а на четвёртом мне как-то надоело (к тому же D оказался на редкость упоротым языком), и я вернулся к старому доброму C++.

Судя по всему, понравилось не мне одному, на форуме курса в тредике с названием "Your experience with the class" больше полусотни отзывов, и практически все – восторженные.

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

Internal Time: Chronotypes, Social Jet Lag, and Why You're So Tired
dfyz
Мимо книжки с таким замечательным названием я, как человек с предельно нетрадиционным режимом дня, обычно ложащийся с первым трамваями и встающий после того, как все нормальные люди уже пообедали, пройти просто не мог. И не пожалел. Книжка коротенькая, состоит всего из 24 глав; каждая глава начинается с небольшой выдуманной истории, после чего на примере этой истории разъясняются некоторые хронобиологические сведения. Поскольку автор – суровый и немного занудный немецкий учони, то, несмотря на то, что книжка ориентирована на читателей-дебилов типа меня, всё серьёзно: по ходу повествования постоянно попадаются сноски со ссылками на реферируемые статьи в научных журналах со сложно произносимыми названиями, именами генов, химических соединений и прочими интересными подробностями. По мастерству создания художественных историй автор, как всякий типичный учони, находится где-то между табуреткой и Дарьей Донцовой, но чтению это, в общем-то, мешает не сильно.

Прочитав книжку, можно узнать:

  • что жаворонки и совы действительно существуют, и это обусловлено вполне объективными причинами;

  • зачем водорослям нужен SIGALRM;

  • как внутренние часы с помощью света и тьмы настраиваются на 24-часовой ритм;

  • на какой месяц в году приходится больше всего самоубийств (скорее всего, не на тот, о котором вы сейчас подумали);

  • что будет, если поместить человека в закрытый бункер, лишив его доступа ко всем признакам, по которым можно догадаться, день сейчас или ночь;

  • как влияет на организм человека переход на летнее/зимнее время;

  • почему страшилки в СМИ в духе "если вы не спите в тёмное время суток, поздравляем, У ВАС РАК" сильно преувеличены;

  • почему, если вы – школьник, то, скорее всего, хреново быть вами (ну, кроме всех очевидных причин);

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


Если вы очень поздняя сова или очень ранний жаворонок, то вам точно понравится, но даже если нет – всё равно рекомендую попробовать.

Главная проблема комментариев в программистских ЖЖ в России
dfyz
Это всё, конечно, очень интересно, но совершенно бесполезно в реальной жизни. В реальности программисту платят совсем не за это. У меня вот пятнадцать лет опыта промышленной разработки, и ни разу не возникало ситуации, где это могло бы пригодиться. Где ты на рынке найдёшь программистов, которые смогут в этом разобраться? У меня на позапрошлой работе тоже был сильно умный коллега, он уволился, а теперь никто не может его код понять. Все эти ваши теоретические построения красиво смотрятся на бумаге, но в реальной жизни программисту достаточно арифметики в объёме начальной школы. Опять какой-то велосипед сделали, могли бы просто взять готовое работающее решение. Это хорошо для тех, у кого очень много свободного времени, а когда у тебя жёсткие сроки и дедлайны, там уже не до этих модных фенечек. Да это же какая-то пионерская поделка. Какая от этого польза обычному программисту? В реальных проектах это всё не нужно. Поубивал бы тех, кто так делает. Эти все понапишут тут потом разбирайся ты кто такой вообще самый умный что ли а ну иди сюда гад я сука тебе сказал не нужно не нужно нужно я тебя ебал гад срать на нас говна.

.hs
dfyz
Товарищи хаскеллисты, я тут решил вспомнить молодость, и что-то не могу понять, почему моё наивное решение для 1330 с Тимуса на максимальном тесте (генератор не привожу, но он пишется тривиально) занимает 2 с лишним секунды, не укладываясь в тайм-лимит, хотя наивные решения на C++ и Go отнимают 60 и 470 миллисекунд соответственно. Я знаю, что вообще для быстрого ввода/вывода принято использовать всякие ByteStrings, но мне интересно понять, где именно затык в наивном решении. Я немножко попрофайлил по методам из Real World Haskell, но пока понял только, что тормозит функция readIntPair, и как её ускорить простыми методами — мне неизвестно. Как вообще кошерно профилировать и разгонять программы на Хаскелле?

Всё время врастопырку
dfyz
Прочитал тут на выходных статейку про время, был сильно впечатлён. Существованием високосных секунд или часовых поясов, отстоящих от UTC на нецелое число получасовых интервалов, меня было не удивить, но вот про отмену пятницы или нескольких минут после полуночи я услышал впервые.

И совсем меня добил тот факт, что количество дней в некоторых прошедших месяцах зависит от текущей локали:
$ LC_ALL='ru_RU.UTF-8' ncal 2 1918
    Февраля 1918
пн    18 25
вт    19 26
ср    20 27
чт 14 21 28
пт 15 22
сб 16 23
вс 17 24
$ LC_ALL='en_US.UTF-8' ncal 2 1918
    February 1918
Mo     4 11 18 25
Tu     5 12 19 26
We     6 13 20 27
Th     7 14 21 28
Fr  1  8 15 22
Sa  2  9 16 23
Su  3 10 17 24