?

Log in

No account? Create an account
The limits of my language mean the limits of my world
 
[Most Recent Entries] [Calendar View] [Friends]

Below are 20 journal entries, after skipping by the 20 most recent ones recorded in Eugene Kirpichov's LiveJournal:

[ << Previous 20 -- Next 20 >> ]
Thursday, January 2nd, 2014
9:39 pm
Settling debts
Сегодня с утра подумал было, что, наверное, settle debts - хорошая задачка на интервью.

Формулировка задачи: есть список транзакций "кто кому сколько одолжил". Надо сделать так, чтобы никто был никому не должен, за минимальное количество транзакций.
Например, если я должен Маше 1 рубль, а Маша должна Пете 1 рубль, то я могу отдать 1 рубль Пете.

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

Казалось бы, простая задача; должно быть если не тривиальное или хотя бы жадное решение, то уж, в худшем случае, решение через какой-нибудь min-cost max-flow.

Однако не тут-то было: задача NP-трудна (слайд 15) - тривиально сводится к KNAPSACK.
Sunday, December 29th, 2013
3:27 pm
2013
2013й был крайне спокоен и небогат на события.
Я пилил MapReduce; сделал одну большую и клёвую фичу и несколько вещей поменьше, вот это всё.
Несколько месяцев играли с _navi_ и еще одним гуглером гитарные трио по понедельникам, потом перестали.
Заняли 19е место на ICFPC (10 в lightning).
Повидали национальные парки Юты и Аризоны; Гранд Каньон даже два раза.
Юля с октября начала работать в LinkedIn.
Собственно, и всё. Как-то год пролетел очень быстро и совершенно незаметно. Я думаю, это скорее плохо, чем хорошо - эдак вся жисть пролетит.

Надеюсь, 2014й будет поинтереснее. Надо, что ли, найти какие-нибудь митапы, повыступать там, или найти какое-нибудь место, куда меня пустят попреподавать.
10:28 am
Два подхода к random testing, или QuickCheck сбоку
Положим, вы написали какую-нибудь хитрую структуру данных - скажем, interval heap, ну или просто heap.

Положим, вы бы хотели протестировать свою реализацию как можно более полно - т.е., не доверяете своей способности написать достаточное количество юнит-тестов.

Есть два принципиально разных подхода в духе "нагенерировать тесткейсов":
1) Генерировать случайные последовательности операций: Начать с пустой структуры и много раз применять к ней последовательность случайно сгенерированных операций, проверяя на каждом шаге, что семантика операции соблюдается (например, параллельно применяя те же операции к вспомогательной простой и неэффективной структуре с той же семантикой, или как-нибудь ещё).
Альтернатива 1.1) Генерировать не много независимых последовательностей операций, а их дерево - это возможно, если структура чисто функциональная (тогда можно к одному и тому же экземпляру применить несколько операций, не делая полную копию).
2) Генерировать случайные валидные состояния и применять к ним одну случайную операцию. В случае двоичной кучи, например - сгенерировать все возможные массивы длины N с числами от 1 до N с повторами, отфильтровать те, что являются кучами (или сгенерировать сразу только кучи - это не очень сложно), и про каждую такую кучу проверить, что применение к ней insert соблюдает семантику insert, а применение removeMax - семантику removeMax.

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

Понятно, что сама реализация подхода 2 может содержать баги, но если присыпать её assert'ами, и если она всё же намного проще тестируемого кода, то это может быть не так страшно.

Пример реализации подхода 2: https://github.com/jkff/gkutil_java/commit/fcbecdb44a3ebb448e88713d919d65084e2e5994 [я это написал just for lulz, когда искал для stream-lib реализацию interval heap, нашёл gkutil_java и нашел в коде глазами багу, которая почему-то не ловилась имевшимися тестами - автор подтвердил наличие баги]

Пытливый читатель разглядит, что подход 2 близок к QuickCheck или SmallCheck, правда, я редко видел сильно нетривиальные генераторы входов для QuickCheck/SmallCheck.
Tuesday, November 26th, 2013
9:01 am
Задачка
Пусть хочется хранить в памяти большое количество строк среднего размера (например, несколько миллионов строк по 10-20кб). Известно:
0) Хочется сэкономить память и хранить каждую строку как можно более сжатой.
1) Набор всё время меняются: добавляются новые строки, удаляются старые
2) Каждая строка сама по себе сжимается, но не очень
3) Многие строки очень похожи друг на друга (но есть несколько "классов эквивалентности"); при сжатии нескольких строк сразу, сжатие получилось бы в несколько раз лучше.

Иными словами, хочется реализовать какой-то вот такой интерфейс:
interface CompressedSet {
  Handle Add(String s);
  String Get(Handle h);
  void Release(Handle h); // Get(h) will not happen again
}


Как быть?

Приходит в голову следующее:
1) Хранить небольшими коллективно сжатыми группами по примерно K: Add находит неполную группу и пересжимает ее с добавлением этой строки; Get разжимает всю группу и достает из нее нужное; Release пересжимает группу без этой строки.
2) Завести какой-нибудь shared dictionary-based компрессор, у которого dictionary с подсчётом ссылок. Есть такие?

P.S. Задачка скорее праздная; некоторые из предположений в реальности нарушаются. Но интересно же!
Saturday, November 23rd, 2013
7:55 pm
Что нового в мире наук
Я в этом своём гугле, при всех его достоинствах, кажется, немного отстал от жизни: стал мало общаться с функциональным сообществом, меньше читать книжек и разных блогов, и т.п.
Т.е. /r/programming-то, ЖЖ и прежние RSS рассылки я всё равно читаю, но не ими едиными.

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

Интересуют темы: ФП, распределённые системы, high-performance computing, алгоритмы, может даже java, вот это всё. Какие интересные, по-вашему, проекты или перспективные идеи появились.

Я, в свою очередь, ознакомился в последнее время с темой succinct data structures, а также предлагаю вам горячо заценить гугловую технологию fibers, про которую говорит в видео несметно крутой техлид гугловой production linux kernel team Paul Turner - это нативные зелёные нитки, с типичным для таковых перформансом (~200нс на создание или переключение нитки) и вообще ничем в плохую сторону не отличающиеся от "обычных" нативных ниток, в т.ч. работающие прозрачно для дебаггеров, thread-locals, блокирующих операций и т.п. Их смысл в том, чтобы навсегда забыть про асинхронные колбеки и спокойно плодить по нитке не только на пользовательский запрос, но даже и на каждый RPC, выполняемый в рамках этого запроса.
Wednesday, September 11th, 2013
8:45 am
Algorithm of the day
Почитал немного just for fun про то, как вычислять в больших графах достижимость; некоторые идеи очень понравились.

Постановка задачи: Есть очень большой граф (миллионы-миллиарды вершин и рёбер); надо научиться быстро отвечать на вопросы
1) достижима ли вершина А из Б?
2) какие вершины достижимы из А?

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

Начнём с задачи 2.

Самый простой способ - просто при запросе сделать BFS. Недостаток - нужно некоторое количество памяти на маркировку вершин; требует заметного количества IO, когда граф лежит не в памяти, а где-то.

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

Есть разные способы сжатия транзитивного замыкания (transitive closure compression). Мне больше всего понравился такой (называется Interval Labeling):
* Построим остовное дерево графа - например, дерево поиска в ширину.
* Разметим каждую вершину дерева индексом входа и выхода в порядке in-order обхода, и положим на диск табличку для доставания вершины по индексу.
* Теперь для любой вершины исходного графа её транзитивное замыкание можно закодировать не просто как список достижимых вершин, а как список достижимых поддеревьев дерева обхода (если достижим корень, то достижимо и всё поддерево). Поддеревьев намного меньше, особенно если в графе много "узких мест".
* Пометим каждую вершину списком достижимых поддеревьев: каждое поддерево будем кодировать как пару (iIn, iOut) для его корня (почему не просто id корня - см. далее).
* Вопрос 1 "есть ли путь A..B" решается так: лежит ли интервал (iIn_B, iOut_B) в одном из интервалов, которым помечена вершина А?
* Вопрос 2 "кто достижим из А" решается так: перечисляем все индексы во всех интервалах, которыми помечена А; всё.

Единственный вопрос остаётся - как выполнить шаг 3 эффективно. Ответ простой: после того, как дерево построено, обойдём исходный DAG снизу вверх в порядке топологической сортировки, и построим метки по индукции: intervals(A) = union {intervals(B) | B <- out(A)} (union берётся с удалением избыточных интервалов).

Очень полезная фишка interval labeling в том, что полученные структуры данных тривиально хранятся и запрашиваются в SQL БД.
Кроме того, если граф уж очень большой, то всё описанное неплохо ложится на MapReduce, Pregel, вот это всё.

Для решения сугубо вопроса 1 есть ещё один интересный класс алгоритмов - "2-hop labeling".
Смысл в следующем: для каждой вершины каким-то образом найдём "остовные (backbone) исходящие" и "остовные входящие" вершины - bOut(A), bIn(A). Они необязательно должны быть прямыми соседями А - имеется в виду достижимость.
Их свойство должно быть таким: "есть путь A .. B" равносильно "bOut(A) пересекает bIn(B)".
В вырожденном случае можно взять за них соответственно прямое и обратное транзитивное замыкание, но цель - уменьшить размер этих меток bIn, bOut.

Минимизировать размер меток - NP-полная задача; и за 10 лет с придумывания подхода пока ещё так и не придумали очень красивых, очень простых или очень быстрых алгоритмов поиска таких меток, но алгоритмов, неплохо работающих на сотнях тысяч или даже миллионах вершин - полно.

Исходная статья про interval labeling
Исходная статья про 2-hop labeling
SCARAB: мета-подход к ускорению алгоритмов reachability
Одна из современных статей на тему ускорения 2-hop
Чумовые слайды про похожий на 2-hop алгоритм поиска кратчайших путей на дорожных сетях из MSR
Tuesday, September 3rd, 2013
9:51 am
Поездка по национальным паркам
Мы давеча съездили с товарищами на каникулы по национальным паркам - Гранд-Каньон, кольцо парков в Юте (Arches, Canyonlands, Capitol Reef, Bryce Canyon, Zion) и Sequoia National Park.

Общие впечатления
Везде очень красиво, но самые красивые - пожалуй, Arches и Zion.
Из минусов - нужно было водить в день суммарно часов 6-8, и некогда/нечем было нормально поесть в какое-либо дня, кроме утра: на обед батончики, на ужин обычно ничего, т.к. очень поздно приезжали (около полуночи). Правда, завтракали обычно очень плотно - в каком-нибудь кафе, в американском стиле: бекон, яйца, вот это всё.
Спали (почти) везде в палатках, но в цивилизованных кемпингах - с туалетами, водой, а иногда даже и душами. Похоже, в Америке это популярный способ жить - приезжать на трейлере (RV - Recreational Vehicle) и торчать там. Очень дёшево; от 10 баксов за ночь на место, куда может влезть 2-3 палатки.
Забавно осознавать, что то, что вокруг тебя - это и есть тот самый "дикий запад", который показывают в кино; с пустыней, горами, кактусами и перекати-полем.
Наш отпуск пришёлся как раз на время, которое, по идее, должно быть самым жарким в году, но кроме того и на сезон муссонов. Однако же с погодой на удивление повезло, и мы нигде не зажарились, и промокли всего пару раз.

Лас-Вегас
Фотки
В Лас-Вегасе почти ничего не посмотрели - только приехали, поели, да прошлись по Стрипу. Мне не понравилось: город-апогей стереотипного консьюмеризма - всё очень дорогое, пошлое, кричащее. Улицы утыканы раздатчиками рекламы секс-услуг. Только было собрались выдвигаться к Гранд-Каньону, как лопнула шина - минус 350 баксов (меняли всю ось) и 2.5 часа времени. За это время сходили пешком в башню Stratosphere, и стало понятно, почему нужно брать с собой очень много воды: в +40 литр в час пьётся очень легко, и весь выводится путём испарения.

Grand Canyon
Фотки
Гранд-Каньон самый сложный - я теперь понимаю, почему оттуда приходится спасать в год 200-300 не рассчитавших свои силы людей: обычно идёшь, пока силы есть, вверх, а когда сил нет - вниз; а тут наоборот: только уж было подустал, как пора вверх.
Мы прошли по трейлу до Plateau Point (суммарно 9 миль ~ 15 км, и 1 км вертикально), встретив по дороге рейнджершу, пытавшуюся нас отговорить (мол, слишком тяжело будет, и гроза надвигается - мы заранее также начитались про опасности от молний, стремались от всякого звука грома и чуть ли не гуськом шли по открытому пространству). Получилось примерно 2 часа вниз и примерно 4.5 часа вверх. Очень повезло с погодой - было лишь около 30 градусов вместо обычных в это время 40, да и под грозу на этот раз не попали. Очень помогает наличие станций с водой каждые полторы мили.
Довольно красиво, но я, признаться, ожидал большего. Огромные скалы, кактусы, разная другая зелень; белки, бурундуки. Colorado River внизу (до неё не дошли, и слава богу).
По дороге дальше по-настоящему поняли, что такое "wildlife crossing" - машин на дороге было мало, но часто образовывались пробки, т.к. дорогу переходил олень или лось (или несколько сразу).

Потом поехали в Юту, в Arches. Долгой дорогой ночью казалось, что в Юте вообще ничего нет.

Arches
Фотки
Я слышал, что этот парк вдохновлял образ планеты Татуин в "Звёздных Войнах", но выяснилось, что нет: Татуин таки снимался в Долине Смерти, а в Arches - всего-навсего один из Индиан Джонсов.
Парк находится рядом с городом Moab, UT (название этого города я знал по соответствующему софтверному продукту). Состоит в основном из жёлтого песчаника, и главная достопримечательность - обилие разных причудливых формаций из песчаника, в частности - более двух тысяч арок.
Через парк проходит дорога, от которой отходят пешие тропы. Мы прошли к Delicate Arch и к Devil's Garden.

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

Затем поехали к Devils Garden - более равнинная тропа с причудливыми скалами по бокам, тонкими плоскими вертикальными скалами, и пр. По дороге оттуда уже полило и загромыхало очень конкретно: правила lightning safety диктуют стрематься, если от молнии до грома проходит менее 30 секунд; тут же молнии несколько раз били рядом с нами; согласно моим представлениям о скорости звука, метрах в 30. Промокли, конечно, до нитки. Мы делали всё как положено: бежали, периодически теряя разные вещицы из рюкзака и периодически садясь на корточки.
Как выяснилось впоследствии, не так уж и зря: мой коллега рассказал, что когда они были в одном из этих парков, то молния ударила в землю прямо рядом с их группой и они все потеряли сознание и полежали некоторое время под дождиком, пока не очухались.

Canyonlands
Фотки
К вечеру поехали в Canyonlands. Уже начинался закат, вдалеке клубились тучи и сверкали молнии. В парке почти никого не было, что создавало довольно мистическую обстановку. Мы решили просто доехать до главной точки созерцания заката, Grand View Point, и посозерцать. Grand View не разочаровал: это обрыв, с которого, во-первых, видно вокруг миль на 150, и видно в основном лежащие в километре-другом внизу плато и очень странной формы каньоны; а во-вторых, закат на нём проявляется в ярком зареве с одной стороны неба и тонкой алой полоске цвета лазерной указки - с другой. Никогда такого раньше не видел.

Capitol Reef
Фотки
Я возлагал на этот парк большие надежды, т.к. насмотрелся в интернете на "slot canyons" (узкие вертикальные каньоны между почти примыкающими друг к другу скалами) и на какие-то особо красивые водопады на Fremont River, однако ни того, ни другого мы не нашли, и просто забрались на небольшую гору, а затем поели яблок и груш в саду, и фруктовых пирогов на местной ферме.

Bryce Canyon
Фотки
Этот парк тоже состоит из песчаника и знаменит своими "иголками" (needles) - группы тонких вертикальных скал, выглядящие, как какой-то сказочный замок. Вживую выглядят значительно краше, чем на фотографиях. Тропа проходит по этим скалам вниз каньона, затем по лесу и обратно вверх - впрочем, мы (но не наши друзья) испугались начавшегося дождя и на полпути повернули обратно и, вернувшись, прошли немного по этой тропе в обратную сторону. С обратной стороны - узкий каньон, как воронка, по одной из сторон которого спускается крутая, узкая, вихляющая дорога; всё в целом выглядит как лестница для гиганта. Заканчивается он то ли пещерой, то ли slot canyon'ом.
Посмотрели закат и поехали дальше.

Нас поджидало несколько неприятностей.

Во-первых, я простудился и слегка занемог.
Во-вторых, у нас всех разряжались телефоны (на случай, когда вообще есть сотовая связь), а у машины внезапно сломались все порты зарядки. Так что доставание телефона с навигатором было крайней мерой, на случай, когда совсем непонятно, куда ехать.
В-третьих, часть хайвея, видимо, размыло, и по дороге пришлось сделать огромный крюк в объезд по дороге in the middle of nowhere, прибавивший, кажется, часа 2 или 3. За всю дорогу встретили всего пару машин. Впрочем, эта дорога была в чём-то оживлённой - то и дело скакали зайцы, кролики, олени; а ближе к Zion в свет фар попали два маленьких скунса. Они страшно перепугались и почесали от нас вперёд, не понимая, куда же им деваться, т.к. слева была скала, а справа - высокий поребрик. К счастью, через минуту они всё-таки сумели запрыгнуть на поребрик и убежать. Ситуация была в чём-то экстремальная, учитывая, что, как сказала oleyka, после встречи их собаки со скунсом им пришлось выбросить даже находившийся в кармане кошелёк - выбрасывать машину не хотелось.
В-четвёртых, как и предполагалось, в ночь с субботы на воскресенье все кемпинги в Zion были забиты. В ближайшем городе, Hurricane, и по дороге к нему также никаких свободных кемпингов не оказалось. В итоге к двум часам ночи приехали в мотель в St.-George.

Zion
Позавтракали в Bear Paw Cafe, примечательном вкусной едой и картинами, изображающими почему-то игру в гольф в разных встречающихся на диком западе экстремальных ситуациях.
У меня разрядился телефон, так что фотографировать было нечем - все фотки в альбоме Юлины.

Фотки - день 1
В первый день пошли на тропу West Rim / Angel's Landing. Поначалу это обычная тропа в гору, а затем она доходит до гряды узких и достаточно голых скал, для прохода по которым следует держаться за вбитые в скалу цепи. Периодически кто-нибудь падает и умирает; кажется, человек 5 за последние 10 лет - в общем, не очень много. Ну и не очень страшно, учитывая, что в политеховском "южном лагере" мы ходили по такому же, только без цепей.

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

Фотки - день 2
На второй день пошли в East Rim / Hidden Canyon / Observation Point. Hidden Canyon - довольно узкий каньон, находящийся довольно высоко в горах. Он был частично запружен наводнением накануне; дно было усыпано песком, камнями и ломаным лесом - тем интереснее. Полазали по стенкам каньона; видели совсем близко настоящую сову; пошли обратно, когда дошли до места, где лезть было опасно.
До Observation Point до конца не дошли, т.к. было уже поздно - пора было выдвигаться в сторону дома через Sequoia National Bark; остановились в городе Bakersfield.

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

Sequoia National Park
Фотки
Из примечательного: узкая и очень вихлючая горная дорога; переходящий нам дорогу медведь; множество - surprise! - гигантских секвой. Fun fact: секвойи размножаются лесными пожарами - их семена раскрываются только при высокой температуре.
Также это был единственный день, когда нам довелось-таки развести костёр: в предыдущие дни либо разводить было негде, либо было слишком поздно и хотелось спать.
Пожарили сосиски и marshmallow. Оказывается, если бросить marshmallow в костёр, то вначале она покрывается корочкой, затем содержимое этой корочки вскипает, прорывает в ней дырку и лезет оттуда; то, что вылезло, тоже покрывается корочкой, а затем вскипает, и т.д.

Вот, в сущности, и всё. Рекомендую.

Хотелось бы съездить ещё раз как следует в Canyonlands и Bryce Canyon, посмотренные уж очень мельком, и съездить "по-настоящему", с ночёвкой в диком месте, а не в кемпинге. Видимо, для этого лучше выбрать другое время года - не жаркое и не холодное; весну, например.
Wednesday, August 14th, 2013
8:42 pm
Fair Guessing of Bit Vectors, или как я участвовал в ICFPC 2013.
Давно ничего в ЖЖ не писал, и сейчас леновато. Но однако же поделюсь восхитительным отчётом _adept_ о том, как мы на этих выходных участвовали в ICFPC.

Мы на 10 месте в lightning round и где-то между 25 и 11 в основном зачёте (думаю, около 20).

Оригинал взят у _adept_ в Fair Guessing of Bit Vectors, или как я участвовал в ICFPC 2013.

Эпиграф



Нас было 7 человек. У нас было 20 модулей на хаскеле, приватный репозиторий на гитхабе, 6 веток в этом репозитории, ImplicitParams, MagicHash и UndecidableInstances в коде и одна highmem нода на амазоне, а также hangouts для общения, юнит-тесты, просто тесты, google docs для заметок и куча статей про SMT-солверы. Не то что бы мы это все использовали, но на ICFPC ты ищешь в инете всякую дурь и бывает трудно остановиться. Единственное что вызывало у меня опасение - это SMT-солверы. Нет ничего более беспомощного, безответственного и испорченного, чем человек, читающий статьи в ходе контеста. Но я знал, что рано или поздно мы подсядем и на эту дрянь.

Краткое содержание для тех, кому лень читать все



Наша команда называлась "(unmatched", и состояла она из меня, Жени jkff, Ромы ro-che.info, Вани _navi_, Саши sorhed, Макса (которого нет в ЖЖ) и еще одного Саши wizzard0.

Мы набрали 1301 из 1820 возможных, из них 457 в lightning round, т.е. в первые 24 часа (UPD: и, похоже, заняли там 10 место! Аааааа!). Мы заняли место между 11-м и 25-м, но еще не знаем, какое конкретно.

Мы писали на Haskell и вот наш репозиторий.

Спасибо моим соратникам - вы все молодцы и умницы! Традиционное спасибо моей жене yulanta за моральную и прочую поддержку :)

А теперь - длинная история про то, как дело было.Collapse )
Sunday, April 14th, 2013
1:49 pm
О поверхностных реакциях
На тему недавних законов - то о блокировке сайтов за материалы, содержащие описание способа самоубийства; то о защите чувств верующих; то о запрете мата в СМИ, то еще чего.

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

Законодатели подают пример рефлекторной, без тени мысли и анализа, не говоря уже о привлечении экспертов, реакции на сложные проблемы - и сами себя нахваливают за эти примитивные, популистские, быдловатые "достижения", таким образом закрепляя мысль, что это ок; ведь сама госдума и даже сам Путин так делают.

Самоубийства? Запретим о них говорить - мы же не хотим, чтобы наши дети начитались про самоубийства и самоубились!
Общее впечатление бескультурья? Запретим публиковать матерные слова в СМИ - мы же не хотим, чтобы все разговаривали матом!
Общее впечатление отсутствия нравственных ориентиров? Дадим паре-тройке основных религий иммунитет от критики - мы же не хотим, чтобы люди смеялись над "не убий"!
Низкая рождаемость? Маргинализуем ЛГБТ!
Люди боятся за безопасность своих детей? Защитим наших детей хоть от кого-то - например, от злых иностранцев-усыновителей!
Люди всерьёз сомневаются в превосходстве российских технологий и образования над иностранными? Объявим, что другие страны безнравственны и дестабилизируют обстановку - мы же не хотим, чтобы люди уважали опыт других стран - так недолго и до перенятия их либеральных ценностей!
Люди выходят на митинги из-за фальшивых выборов? Запретим митинги - мы же не хотим, чтобы случилась революция!

Не знаю, насколько большую роль на самом деле играет имидж государства в формировании культуры и системы ценностей граждан, но думаю, что большую - мне представляется картина, как, искренне восхитившись такой заботой власти о населении, иные люди начинают брать пример со "старших" и "сильных" и использовать такие же методы для заботы о своих близких, без какого-либо чувства вины за недостаточность и неадекватность принимаемых мер; даже с гордостью за то, что какие-то меры принимаются:

Ребёнок курит? Побьём его, и пообещаем побить ещё, если снова найдём у него сигарету!
Ребёнок разговаривает исключительно матом? Вымоем ему рот с мылом!
Ребёнок худой и слабый? Впихнём в него силой вдвое больше еды!
Ребёнок перестал уважать родителей? Перестанем платить за его за образование, пускай работать идёт или в армию!
Ребёнок запирается в своей комнате, обвешанной постерами готических музыкантов? Выбросим постеры!
Жена не хочет секса? Запретим ей общаться с другими мужчинами, а то и силой возьмём!
Собака ссыт по всему дому? Будем её бить за каждый раз - поделом!

Мы заботливы и не гнушаемся жёстких мер, если Так Надо - мы берём пример с нашего сильного Государства!

Я в курсе, что популизм и создание иллюзии политической деятельности характерны не только для России. My point stands.

P.S. Отвечать на комменты буду мало и редко.
Thursday, March 21st, 2013
7:53 am
О гендерном неравенстве
si14 написал пост о гендерном неравенстве, с которым я на 100% согласен.

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

Оригинал взят у si14 в О гендерном неравенстве
К сожалению, эта тема достаточно мало обсуждается в современном российском обществе, но от этого она не становится менее значимой: быть женщиной сегодня сложно. Сложнее, чем мужчиной. Особенно в России. Не нужно быть семи пядей во лбу, достаточно просто посмотреть по сторонам и пообщаться.
С течением времени всё больше карьера (научная, в индустрии, где угодно) становится для «среднего класса» не столько путём зарабатывания денег (на пропитание вполне можно заработать и низкоквалифицированным трудом в маке), сколько средством самореализации. Тем, за что можно самого себя уважать. Тем, о чём ты думаешь вечером и что заставляет тебя жить. Одновременно с этим растёт средняя продолжительность жизни. Всё это приводит к тому, что убогая «традиционная» модель «мужчина зарабатывает деньги, женщина сидит дома и Kinder-Küche-Kirche» вырождается в одну из двух:

  • «советская»: все работают, все равны, но женщина ещё и следит за домом (и за собой, но об этом ниже); при этом, как ни странно, разнообразные домохозяйки, полуфабрикаты и няни считаются чем-то позорным — есть же жена!

  • «российская»: заканчиваем школу-заканчиваем университет-выходим замуж-рожаем детей-растим детей-дети вырастают и уходят. И тут внезапно оказывается, что нашей бывшей студентке уже около 40-50, она с каким-то неинтересным, некрасивым и унылым мужиком, ничего не умеет и профессионалом ни в чём, кроме варки борщей, не является. Впереди 30-40 лет жизни без смысла — ведь в России как-то не принято поступать в 40-50 в университеты, учиться чему-то новому или зажигать с мужиками. Примерно так выглядит ад, я думаю — и примерно так рождаются все эти бессмысленые тётки с химической завивкой, дикой помадой, ожирением, мерзким характером и скандальным голосом.

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

  • ты должна выйти замуж и родить до 30, а лучше до 25 — ведь в этом смысл твоей жизни!

  • ты должна обязательно найти мужика, мужик это всё, женщина без мужика говно и не нужна!

  • вари борщи! борщи вари!

  • вся эта наука (программирование/инженерия) это очень сложно и не для женщин — посмотри, у тебя же ничего не получилось с первого раза, ты просто тупая и должна варить борщи!

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

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

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

Вы всё ещё сомневаетесь в приведённом в самом начале тезисе о гендерном неравенстве? Тогда у меня для вас плохие новости.

В конце концов, можно бы обратить внимание и на нас самих. Подавляющее большинство читателей этого блога — мучжины, я думаю. Вот прямо сейчас посмотрите на себя в зеркало, оголившись выше пояса; что вы увидите? Зарождающийся (или уже зародившийся) живот, покрытый бледной кожей с торчащей порослью, или что-то более близкое к этому, например (да, я понимаю, что эти люди — профессиональные модели, но как ориентир сойдут)? Прыщавую, грязную рожу? Как давно вы готовили что-нибудь (я знаю, что многие готовят, но большинство — нет), кроме полуфабрикатов? Насколько чисто у вас в жилище? Почему-то считается нормальным ожидать (даже требовать!) нормального эстетичного внешнего вида, вкусной еды и прибранного уютного жилья от женщин и не делать ничего из этого самим. Это глупо, нечестно и мерзко.

Какова мораль этого поста? Достаточно проста. Если вы мужчина — помогайте женщинам расти профессионально (даже если отбросить соображения о мировой справедливости — помогать симпатичным людям просто приятно же!), разберитесь с проблемами и сексизмом в своей голове, начните беспокоиться о собственном внешнем виде, запахе и бытовых умениях. Если вы женщина — просто помните, что делать что-то интересное, развиваться и получать за это деньги — действительно круто, детьми же вы успеете обзавестись всегда (да и это не то чтобы достижение, у всех ваших матерей вглубь веков получалось, я уверяю), и крутите патриархальное общество на виртуальном болту. Viva la Resistance!

Sunday, February 24th, 2013
7:04 pm
Про Google
Возможно, читатели заметили, что с тех пор как я пришёл в Гугл, я ничего не писал в ЖЖ. Это по двум причинам:
1) Я писал всякую мелочь в плюсике
2) Некогда и не хочется. Об этом далее.

Но всё-таки напишу.

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

"Пропагандистская машина" работает очень здорово. Первое, что происходит по приходе в Гугл - Noogler Orientation, длящаяся две недели; башню сносит напрочь где-то через два часа после начала. Еженедельно происходят т.н. TGIF ("thanks god it's friday"), на которых рассказывают о state of the art гугла в какой-либо теме и готовящихся проектах (напр. поиск, карты, перевод, ...) и отвечают на любые вопросы, в т.ч. острые. Также периодически бывают митинги, где рассказывают о новых инфраструктурных компонентах и т.п. - это обычно тоже сносит башню.

Про то, чем я занимаюсь. Напомню, я в команде MapReduce - не совсем так, но точнее сказать не могу. Сейчас занимаюсь, грубо говоря, некоторыми высокоуровневыми аспектами его производительности.

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

Про коллег. Я еще не очень втянулся в командную разработку, и пока сделал всего один коммит (больше занимался анализом данных - кстати, с помощью R и ggplot2), но их характерные особенности таковы: 1) они все приятные в общении, дружелюбные, скромные (ни грамма понтов), адекватные, весёлые люди 2) они все очень и очень крутые. Не знаю как это сформулировать; не то чтобы они ежесекундно извергали гениальные идеи - просто всё, что они говорят и делают, преисполнено продуманности, взвешенности и профессионализма :) На мои высказываемые "гениальные" идеи говорили "да, хорошая идея - уже реализовано / планируется, см. обсуждение там-то".
Почти все с семьями, многие с детьми.

Уточнённый состав моей команды - те, с кем я в основном пересекаюсь и хожу обедать - выглядит так (погуглите про них самостоятельно, если интересно): Eric Roshan-Eisner, Fangwei Li, Jelena Pješivac-Grbović, Jeremy Hurwitz, Jerry Zhao, Ma Chi, Marian Dvorsky, Shan Lei, Sunghwan Ihm, Swapnil Patil, Tudor Marian, Xiaozhou Li. Конкретно над своей областью проекта работаю падаваном Елены.

Про код. В моей команде пишут на C++, но с имеющимся качеством кода, инструментами разработки и библиотеками это вроде бы не проблема, во всяком случае не затмевающая domain complexity.

Про нагрузку. Никакого овертайма я вокруг себя не заметил - все в основном приходят около 10, а уходят около 6. Просто всё это время заняты делом. Устал - можно отойти съесть какой-нибудь фрукт или покататься на велике по кампусу (около нашего здания холм, с которого открывается классный вид).
Не знаю, насколько это вас впечатлит, но для меня ключевой показатель собственной продуктивности такой: я не залогинен на рабочем компе ни в одну социальную сеть :) а в туалете интернет почти не ловит
К вечеру голова не гудит, но заниматься умственной деятельностью не очень хочет - а тем более, скажем, волноваться и участвовать в кипучих дискуссиях в ЖЖ, так что я ничего не писал, мало читал и мало комментил.

Пока всё.
Friday, January 11th, 2013
10:16 am
Górecki Symphony no.3 - II. Tranquillissimo
https://www.youtube.com/watch?v=R90vDLHGs1Q
У меня нет слов.

Вики-статья про эту симфонию: http://en.wikipedia.org/wiki/Symphony_No._3_(G%C3%B3recki)

Часть 2:

...Later that year Górecki learned of an inscription scrawled on the wall of a cell of a Gestapo prison in the town of Zakopane, which lies at the foot of the Tatra mountains in southern Poland. The words were those of 18-year-old Helena Wanda Błażusiakówna, a highland woman incarcerated on 25 September 1944. It read O Mamo nie płacz nie—Niebios Przeczysta Królowo Ty zawsze wspieraj mnie (Oh Mamma do not cry—Immaculate Queen of Heaven support me always). The composer recalled, "I have to admit that I have always been irritated by grand words, by calls for revenge. Perhaps in the face of death I would shout out in this way. But the sentence I found is different, almost an apology or explanation for having got herself into such trouble; she is seeking comfort and support in simple, short but meaningful words".[8] He later explained, "In prison, the whole wall was covered with inscriptions screaming out loud: 'I'm innocent', 'Murderers', 'Executioners', 'Free me', 'You have to save me'—it was all so loud, so banal. Adults were writing this, while here it is an eighteen-year-old girl, almost a child. And she is so different. She does not despair, does not cry, does not scream for revenge. She does not think about herself; whether she deserves her fate or not. Instead, she only thinks about her mother: because it is her mother who will experience true despair. This inscription was something extraordinary. And it really fascinated me."[9]...
Saturday, January 5th, 2013
10:18 am
Remote coffee debugging
leksea научила меня делать настоящий кофе, по случаю чего я приобрёл кофемолку, турку и кофе, но я слегка подзабыл урок, и решил последовать рецепту отсюда и у меня получилась какая-то хрень - а именно, пенка толком поднялась всего один раз, процесса внезапного кипения у кофе не наблюдалось, вообще времени до кипения прошло в несколько раз больше чем надо, ну и результат какой-то плоский и безвкусный. Единственное очевидное отличие использованного "оборудования" - у моей турки гораздо шире горлышко (достаточно узкой на амазоне не нашёл).
Доктор, что я, вероятно, сделал не так?
Thursday, January 3rd, 2013
9:35 pm
Сложные моральные вопросы
Порою - почти исключительно в зарубежном интернете - натыкаюсь на статьи, поднимающие действительно сложные этические вопросы и обсуждающие их на уровне на несколько голов выше и смелее, чем обычно (с избитыми и всем известными аргументами). Не в том смысле смелее, что выражается какая-то особенно радикальная точка зрения, а в том смысле, что автор делает усилие и заговаривает о вопросе, о котором, считается, и говорить-то нельзя. Мне обычно после таких статей становится неудобно за тот уровень, на котором дискуссии об этике веду я, и хочется чему-нибудь научиться у авторов.

Вот несколько таких статей, которые мне удалось сейчас вспомнить.

http://growingupgoddy.com/blog/eaton/world-without-consent про изнасилования и добровольность в сексе

http://www.pulitzer.org/works/2010-Feature-Writing про случай Димы Яковлева и преступную небрежность

http://www.forbes.com/sites/harrybinswanger/2013/01/01/with-gun-control-cost-benefit-analysis-is-amoral/ про владение оружием (thx sorhed)

http://wikileaks.org/wiki/An_insight_into_child_porn про детскую порнографию и её легальность

Если знаете, где взять ещё - подкиньте.
Sunday, December 30th, 2012
9:43 am
Итоги года
События и достижения:
* Купили суперкрутого кота.
* Поженился с grrrl.
* Начал заниматься в Мирантисе OpenStack'ом; поначалу понравилось, что узнал очень дохрена про сети, девопс и вообще; потом разонравилось, что ни computer science, ни серьёзного software engineering там не оказалось, реально сплошной девопс; загрустил и начал искать работу.
* Выступил на #addconf про кластеры и на #spbfprog про timeplotters.
* Поучаствовал в выборах президента и ещё одних местных выборах. Потерял последние иллюзии.
* Переехал в силиконовую долину.
* Сходил на интервью во много компаний. Интервью везде были очень простые - интервью в гугле, например, абсолютно не соответствовало сложности того, чем надо будет заниматься.
* Приехал "на 4 недели" в Россию, а застрял на 7. Зато военный билет получил.
* Получил и принял оффер от гугла в команду MapReduce.
* Опубликовал перевод статьи про инкрементальные регекспы - похоже, статья таки удалась.
* Сделал мануал по timeplotters и опубликовал его.
* Два дня назад начал по утрам хоть как-то бегать :)
* Вчера купил гитару.

Скиллы:
* Как уже сказал - знатно прокачал девопсные скиллы.
* В плане скиллов software engineering, математики и т.п. год был крайне непродуктивным; возможно, даже имел отрицательную продуктивность. Ну разве что из литературы побольше узнал об устройстве всяких масштабируемых систем.
* Прокачал английский, хотя можно было и посильнее.
* Очень сильно прокачал social skills, кажется - в двух смыслах: 1) умение вести культурную и аргументированную дискуссию и вообще выражать свои мысли 2) умение договариваться, преподносить неприятные вещи и т.п. Ну и, возможно, 3) умение видеть в несогласном собеседнике человека
* Прочитал книжек 10 по типографике, но почти никуда пока не применил.
* За время в России взялся за гитару и вспомнил её.

Ощущения и прочее:
* Год был очень стрессовый - постоянно приходилось что-нибудь организовывать, оформлять какие-нибудь документы, звонить куда-то и что-то выяснять или договариваться, и т.п. Очень часто в связи с этим хотелось издать львиный рык и громко расхуячить что-нибудь хрупкое.
* В этом году я был непродуктивен и ленив, и вообще уже не торт. Мне бы хотелось связывать это с разонравившейся работой и постоянными упомянутыми стрессами; вероятно, следующий год будет в этом смысле лучше и проще.
* В значительном количестве срачей на различные темы (от прав ЛГБТ до производительности языков программирования) в полной мере осознал масштаб проблемы "защиты своей уверенности в правоте любой ценой". Думаю, не ошибусь, если скажу, что видел комментарий вида "ок, убедил" всего несколько раз на несколько тысяч дискуссий. Заинтересовался, как с этим бороться, но пока понятно лишь, что необходимый компонент - относиться к собеседнику как к живому человеку и не заставлять его обороняться. Это очень сложно и этим скиллом я пока не овладел в нужной мере.

Всех с наступающим.
Saturday, December 29th, 2012
9:33 am
Thursday, December 27th, 2012
9:04 pm
Google
Как я уже сказал в паре соц.сетей (можно не поздравлять, а то мне уже неудобно :)), с середины января я буду работать в Google, по сути, в команде MapReduce, но над другим, пока секретным проектом. (из Mirantis ухожу потому, что оказалось, что работа над OpenStack, которая стала основным направлением всей компании, это почти исключительно systems integration, что мне не по душе; в остальном великолепная компания)

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

Сегодня обедали с будущей командой. Они охрененные. Вот несколько человек, чьи имена я запомнил: Grzegorz Czajkowski, Ken Goldman, Jerry Zhao, Jelena Pjesivac-Grbovic, Matt Austern и Jim Denhert, работавшие с А.Степановым в SGI (а Matt вообще основной автор SGI STL). Еще пару человек не запомнил и пары не было. У половины команды докторские степени. Короче, зазнаться точно не получится :)

Сказали, что по расчётам втянусь я где-то через полгодика.
Wednesday, December 26th, 2012
7:16 pm
8:41 am
Снова про найм.
У thesz хаскельная вакансия.

Оригинал взят у thesz в Снова про найм.
Поскольку Володя Шабанов отказался от работы (он работает над bq Reader), я продолжаю поиск.

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

"Мало не покажется", прозвучавшее в предыдущем посте, означало как фронт и сложность работ, так и оплату труда. Оно остаётся полностью в силе.

Присылайте резюме и сопроводительные письма на jobs@parsci.com или на serguey.zefirov@parsci.com.

В скайпе я serguey.zefirov, в гмейле sergueyz - стучитесь, я всё расскажу.

PS
Если вы знаете суперзвезду, расскажите ей (или ему), пожалуйста.

Wednesday, December 19th, 2012
7:00 pm
Перевёл статью про инкрементальные регулярные выражения
http://jkff.info/articles/ire/

Кажется, получилось лучше, чем оригинал - некоторые секции переработаны, кое-что дописано.

Даже сам Russ Cox расшарил :) (правда, это потому, что я ему письмо прислал - однако, сам себя не похвалишь - никто не похвалит :) )
UPD. И Дэн Пипони тоже.
[ << Previous 20 -- Next 20 >> ]
Guitar Delicacies   About LiveJournal.com