*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

вторник, 28 декабря 2010 г.

Коллекции электронных книг

Решил собрать в одном месте ссылки на ресурсы с электронными книгами (в одном из недавних постов в коментах была отличная подборка).

Буду признателем за информацию на подобные ресурсы. Обновления буду добавлять в пост.

Opengrok

Исходники – это основной источник информации для программиста, особенно если в компании (или проекте) размер кодовой базы переваливает за 200-300 тысяч строк.

Чтобы найти драгоценное зерно в такой куче, нужна правильная утилита для просмотра, а главное, поиска (типа «дай-ка я гляну, как народ эту функцию вызывает?» или «как там правильно создать экземпляр этого класса?» и т.д.).

Большинство систем контроля версий имеют веб-интерфейс для подобных целей. Также есть независимые системы, и одна из них называется Opengrok.


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

Кстати, можно вживую пощупать Opengrok на исходниках OpenSolaris’а.

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

P.S. Я как-то в целом давно не писал про всякие организационные примочки, облегчающие работу программиста.

Поэтому, небольшой списочек из старенького, но все еще актуального:

понедельник, 27 декабря 2010 г.

Атомарность типа int и указателя

Меня давно занимает вопрос атомарности типа int (да и любого типа, равного по длине шине процессора, например, указателя или float для x86).

Ясно, что в теории, нельзя полагаться на факт такой атомарности. Но давайте конкретизируем: платформа x86, и переменная объявлена как «volatile int a». Тут я не играюсь с «reinterpret_cast»’ом и приведением указателей, то есть можно гарантировать, что компилятор обеспечит правильное выравнивание, соответствующее шине процессора и памяти, тем самым гарантируя, что доступ к этой ячейке произойдет за один такт.

Есть ли хоть какой-то шанс с ненулевой вероятностью, что какое-то вычисление (команда процессора) по отношению к «а» может быть тут неатомарна? Может ли так быть, что операция «a++» или «a += arbitrary_stuff» и т.д. выполниться не целиком?

Так как переменная volatile, значит любые оптимизации будут компилятором запрещены, и не выйдет так, что вместо полноценной 32-х битной команды (обнуления, инкремента, умножения и т.д) компилятор использует, например, каскад двух 8-ми битных команд для операции, которую можно сделать одной 32-х битной.

Ведь где бы значение переменной «а» не обрабатывалось (в регистре, в кэше, в памяти), везде это будет та или иная одиночная команда процесса, которая, очевидно, атомарна.

Ясно, что правилом хорошего тона считается не полагаться на атомарность int’а. Но современная архитектура процессоров (микроконтроллеры пока не берем) практически гарантирует эту атомарность, разве нет?

воскресенье, 19 декабря 2010 г.

В блоге новая система комментирования DISQUS

Подглядел у "One Div Zero" - движок комментирования DISQUS и установил себе.

Что это такое? Это весьма продвинутый движок комментирования (с шахматами и гимназистками) со множеством современных примочек на замену стандартному: сортировка при просмотре, кнопки Не/Нравится, ответ на конкретный комментарий. Ну и разные административные/модераторские возможности.

В целом, ничего особенно, но по сравнению со стандартным движком Блогспота - это небо и земля.

Установка, удивительно, простая. Вообще ничего делать не надо - просто указать имя блога на Blogger'е и разрешить доступ на модификацию шаблона. Далее все происходит автоматически. Вроде даже существующие комментарии проимпортировались.

Вобщем, посмотрим. Будут глюки - пишите.

UPDATE: Оказывается, тут можно редактировать собственные комментарии. Ура!

суббота, 18 декабря 2010 г.

А какая у вас зарплата?

Когда я ходил на свои первые интервью в Англии, меня приводил в недоумение вопрос, который почти всегда задают рекрутеры (независимые агенты или сотрудники отделов кадров конкретной компании) – «А какая у вас сейчас зарплата?». Не имея достаточно опыта подобного общения и толком не понимая причину этого вопроса, я имел глупость говорить эту сумму.

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

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

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

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

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

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

Есть небольшое замечание, что конкретно в Англии, в процессе оформления документов при поступлении на работу (контракт, всякие кодексы, соглашения о неразглашении и т.д.) ты должен предоставить формальные налоговые выписки о твоих доходах с предыдущего места работы (по ним можно понять зарплату), чтобы бухгалтерия правильно рассчитала тебе налоги, но все это происходит уже после, когда контракт уже согласован и подписан, и уже формально взят на работу.

Вот.

Кстати, может кто-нибудь поделиться опытом устройства на работу через кадровые агентства в России и других республиках и государствах нашего региона?

вторник, 7 декабря 2010 г.

Интервью с домашним заданием

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

И вовсе не потому, что я часто люблю менять работу (совсем наоборот). А потому, что в этом процессе есть несколько полезных сторон.

Для начала – это вызов. Задача, которую надо решить (ведь помните, что мы должны быть разносторонними, а не только на С++ программировать). Это как участвовать в ТопКодере. У меня это всегда легкое (а порой и не очень легкое) волнение и ощущение бабочек внизу живота. Предлагаемая задача не решается в лоб академическими знаниями и всегда требует, чтобы ты себя проявил.

Затем идет чисто практическая сторона – опыт, который никаким другим способом не получить. Даже если тебя все устраивает на текущей работе или собственном бизнесе, всякое может случиться, и иметь опыт устройства на работу (как бы формально и прагматично это не звучало) иметь стоит. К тому же усилий для его получения надо не так и много. Чтобы успешно пройти интервью – надо уметь это делать. Хоть многие компании и заявляют, что они целенаправленно набирают специалистов, а не специалистов по устройству на работу – это блеф. Люди всегда оценивают людей. И порой надо догадаться, что за критерии отбора скрыты за вопросами и задачами, предлагаемыми тебе на интервью.

Например, многие думают, что все интервьюеры – это супер/мега/экстра спецы, которые видят тебя насквозь. И причина этому – просто что «он» задает тебе вопросы, а не ты ему. Хотя в большинстве случаев, особенно в больших компаниях, интервьюируют обычные разработчики (а некоторые и без особого желания), и если догадаешься, что ему надо – успех гарантирован.

Лично я понял, увы, не сразу, насколько важно быть не только технически подкованным, но и собрать максимально информации и компании, а по возможности и о предстоящем интервьюере. Благо сейчас у всех есть блоги, ЖЖ, Фейсбук, ЛинкедИн, МайСпейс и т.д.

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

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

Ладно, это лирика.

Хочу поделиться интересным примером.

Интервьюировался я недавно в одной небольшой трейдинговой фирме на позицию обычного разработчика на С++. Сначала было очень короткое пятнадцатиминутное телефонное интервью, которое я легко прошел (но увы, я не вынес из него всей полезной информации – см. ниже). Стандартный набор: С++, multithreading и пару вопросов про сложность. Под занавес товарищ ненавязчиво спросил, какими скриптовыми и функциональными языками я в принципе владею и интересуюсь.

Затем, они мне прислали домашнее задание.

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

Было дано несколько простых тестовых данных. Для задачи большой размерности (поле 7 на 7, 2 короля, 2 ферзя, 2 слона и одна ладья) надо только вывести количество возможных позиций.

И далее было самое главное ограничение: можно писать задачу на любом языке, кроме C, C++, C#, Java, Python, PHP, Pascal.

Срок – неделя.

Я сначала почесал репу (вроде все выглядит как перебор с возвратами, и надо только позаботиться об исключении повторяющихся конфигураций), написал все сначала, конечно, на С++, отладил алгоритм. И стал думать, на чем мне сдавать задачу. Решил на Go. Написал, проверил. Результаты совпадают.

Отправил. Приходит ответ, что все неплохо, но типа мы ищем человека с более оригинальным подходом, чем использование С-подобного языка Go, когда мы явно не рекомендовали использовать императивные языки, тем более из семейства С, и ожидали реализацию на каком-то скриптовом или функциональном языке. Увы, отказ.

Ну, в общем, суть понятна. Задача была не в задаче, а в «показать себя разносторонним программистом», не который если что, так расчехляет С++.

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

Вот.

P.S. Для желающих – исходники мой оригинальной программы на С++. Там же есть версия на Go, но плюсовый вариант содержит самый быстрый алгоритм, который я сумел придумать.

У меня больше нет идей, чтобы еще можно ускорить.

Желающие могут попробовать. Было бы очень интересно время работы теста #3.

Тесты (можно и добавлять свои) и проверяющая система уже встроены прямо в исходник. Его можно скомпилировать:

cl /O2 /EHsc problem.cpp

У меня печатается:

Case #0 OK (line 235)
Case #1 OK (line 248)
Case #2 OK (line 271)
Case #3 OK (line 318) time 1.495s

Для своей версии вам надо переписать функцию “solve()”. Присваивая переменной «problem_filter» значения, отличные от «-1», можно запускать не все тесты, а по одному.

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

среда, 17 ноября 2010 г.

Активный язык

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

А как насчет вопроса «а на каком языке вы наиболее продуктивны»?

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

Кстати, есть распространенное заблуждение, что спортивное программирование – это обычно куча корявого и запутанного, хоть и работающего кода, который совершенно непригоден для «обычного» программирования. Это не так, и зависит от конкретного человека. Можно, например, посмотреть код двух ТопКодеровских лидеров – ACRush и Petr. Код второго очень чистый, начиная от нормального форматирования и заканчивая общей понятной структурой решения. Код же первого же – обычно по внешнему виду оставляет желать лучшего (хотя это нисколько не умаляет его бесспорного лидерства), и читать его гораздо сложнее.

Так вот, я задал себе вопрос – а на каком языке я бы мог участвовать в контестах, где идет учет времени, и нет возможности копаться в документации по языку или библиотеке? И честно говоря, С++ находится далеко впереди Java и C# (Си не берем из-за бедности стандартной библиотеки). Мой уровень «погружения» в С++ (моменты языка, бесчисленные шаблоны уже виденного кода, знание библиотеки и т.д.) не сравним с той же Java.

А сколько языков у вас «живут в пальцах»?

Неконстантные ссылки

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

Проблема: использовать ли не константные ссылки в аргументах функций?

Мой подход: нет.

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

Лично нарвался недавно на собственную мину (конечно, упрощенный вариант):

T a = 10;
...
f(a);
...
assert(a == 10); // BOOM!!! WTF?! Who changed this?

А причина в «void f(T& a);», а должно быть «void f(const T& a);» или «void f(T* a);». Функция «f()» почему-то изменила значение «а», а писал я ее давно и успел забыть такую ее «особенность». Но из кода «f(a)» сходу не видно – может эта функция изменить «а» или нет.

А как могло произойти, что мне вообще пришло в голову сделать параметр «a» неконстантной ссылкой? Лично у меня это случается, когда переменная изначально была внутри функции, и в какой-то момент я решил сделать ее параметром, а менять в коде везде «a.» на «a->» было просто лень, вот и сделал ссылку, вместо указателя. За что и поплатился, позже.

Кстати, один из аргументов, приводимый людьми, выступающими за неконстантные ссылки –это «писать "a." приятнее и понятнее, чем "a->" или "*a"». Также ссылка более надежна с точки зрения NULL (сделать ссылку, указывающую на NULL конечно можно, но тут уже надо постараться). Тут можно выйти положения так:

void f(T* ptr_a) {
  assert(ptr_a != NULL);
  T& a = *ptr_a;
  ...
  if (a.foo()) ...
}

Небольшой лишний код, но решены обе проблемы: проверка на NULL и необходимость разыменовывать указатель каждый раз. А главное, в вызывающем коде придется писать так: “f(&a)”, что явно укажет на факт возможной модификации аргумента внутри функции.

Например, в C# есть специальной ключевое слово «ref», которое надо ставить перед аргументами в вызывающем коде, если хочется передать что-то по ссылке. По мне,это очень хорошее свойство языка.

Исключения из правила

Я пока выработал для себя одно исключение: сложные, сервисные прокси-объекты, типа потока или базы данных можно передавать по неконстантной ссылке. Но тут надо четко понимать, не вы меняете этот объект внутри функции, а он меняется сам при обращении к нему.

Например:

void print(std::ostream& os, const T& a) {
   os << a;
}

или

void save_to_db(Database& db, ...) {
   db.connect();
   db.save(...)
   ...
}

А когда вы используете неконстантные ссылки?

Ну и чтобы два раза не вставать, пара личных маленьких радостей:

  • Мое интервью проекту "OpenQuality".
  • Уверенно решил две задачи в недавней SRM 487. А достижение в том, что во второй задаче даже применил DP, хоть и тривиальное. В процессе контеста был последним в комнате, так как долго возился с первой задачей, но потом почти все упали на фазе challenge'а и на тестах, и я оказался вторым в комнате. Кстати, настоятельно рекоммендую сайт CodeForces. Наши ребята сделали отличный сайт для контестов и регулярно их там проводят. В отличие от ТопКодера русский язык там в почете, задания предоставляются на обоих языках, и выбор язык программирования гораздо шире. Также можно там спросить совета по задачам и получить квалифицированный ответ от бойцов.

суббота, 13 ноября 2010 г.

Screencast’ы

А вы смотрите скринкасты?

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

Например, посмотрев три видео Coding in Objective-C 2.0 (в принципе, можно скачать бесплатно), я могу написать небольшую программу на этом языке с использованием классов и имею представление, как работает управление памятью в Objective-C (кстати, весьма интересная концепция, я бы ее назвал – ручной сборщик мусора, когда память освобождается вроде как автоматически, но ответственность за правильность подсчета активных ссылок на объект возлагается на программиста).

Сейчас в процессе просмотра Writing Your First iPhone Application и на очереди Erlang in Practice.

Но есть со скринкастами одна засада – они должны быть качественно сделаны, иначе будет только сожаление о потерянном времени. Скринкасты от The pragmatic Bookshelf сделаны, на мой взгляд, очень хорошо.

А какие скринкасты смотрите вы? Какие можете посоветовать?

P.S. Кстати, онлайн-магазин «The pragmatic Bookshelf» нравится мне все больше и больше. Все книги продаются в электронном свободном варианте, причем в нескольких форматах (pdf, mobi, epub).

вторник, 9 ноября 2010 г.

Как называть getter'ы и setter'ы

Для именования функций записи и чтения членов класса (getter/setter) в стандартном C++ есть три часто используемых приема.

1. Чисто плюсовый вариант, основанный на семантике ссылок.

class Foo {
  Value field_;
public:
  Value& field() { return field_; }
  const Value& field() const { return field_; }
};

Использование:

Foo foo;
foo.field() = field_instance;
field_instance = foo.field();

Плюсы: краткость текста, близость к нотации "свойств", и возможность использования присвоения в каскаде (foo1.field() = foo2.field() = 2;).

Минусы: использование синтаксиса вызова функции слева от знака присваивания выглядит непривычно.

2. Способ в стиле Java.

class Foo {
  Value field_;
public:
  void setField(const Value& value) { field_ = value; }
  const Value& getField() const { return field_; }
};

Использование:

Foo foo;
foo.setField(field_instance);
field_instance = foo.getField();

Плюсы: ясность и очевидность синтаксиса.

Минусы: многословность из приставок "get" и "set".

3. Cтиль Objective-C

class Foo {
  Value field_;
public:
  void setField(const Value& value) { field_ = value; }
  const Value& field() const { return field_; }
};

Использование:

Foo foo;
foo.setField(field_instance);
field_instance = foo.field();

Плюсы: краткость текста при чтении (нет почти бессмысленной приставки "get") и очевидность при записи.

Минусы: я пока не нашел таковых.

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

Лично я почти всегда предпочитал способ #1, но после своего последнего поста я перешел на третий.

пятница, 29 октября 2010 г.

Ссылка на временный объект в списке инициализации конструктора

Имеем два исходника:

#include <iostream>

struct A {
  A();
  const int& i;
};

A::A() : i(123) {}

int main() {
  A a;
  std::cout << a.i << std::endl;
}
и

#include <iostream>

struct A {
  A() : i(123) {}
  const int& i;
};

int main() {
  A a;
  std::cout << a.i << std::endl;
}

Будучи скомпилированными компилятором от Sun или GCC, эти два примера печатают разные результаты. И первый - неправильный. Студия же 2010, с настройками по умолчанию, дает предупреждение и генерирует код, работающий правильно (точнее, как ожидает программист) в обоих случаях.

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

Ко мне пример попал как результат анализа реального бага.

вторник, 26 октября 2010 г.

Никому нельзя верить, даже себе

Есть (точнее был) у меня вот такой код:

const std::string& id() const { return id_; }
std::string id() { return id_; }

В нем есть одна досадная опечатка, из которой код:

order.id() = 123;

делал то, что от него не ожидалось, а точнее, ничего не делал. И проблема, как вы наверное уже догадались, в пропущеном значке "&" во второй строке. Должно было быть так:

const std::string& id() const { return id_; }
std::string& id() { return id_; }

Эта опечатка стоила мне часа поиска проблемы через вторичные признаки в виде иногда не обновляемой базы данных.

Причина? А все потому, что я поленился написать тесты изначально, решив, что это уж очень простые методы. Но теперь таки добавил для этого тест:

TEST(Order, GetterSetters) {
  Order order;
  ...
  EXPECT_EQ(0, order.id());   // Must be initialized.
  order.id() = 123;
  EXPECT_EQ(123, order.id());
  ...
}

Решил сэкономить время, а вышло наоборот.

Вывод: тесты, тесты и тесты.

среда, 20 октября 2010 г.

Умножение вручную на бумажке по-китайски

Не берусь утверждать, что этот способ эффективнее традиционного столбика, но все равно впечатляет.

четверг, 7 октября 2010 г.

Книги по обработке строке и производящим функциям

Покупка книг на Амазоне в Европе и Штатах дело крайне простое, удобное и быстрое (особенно для электронных книг). Тут также можно и продавать свои книги. Очень удобно и для владельца, когда надо избавиться от одноразовой книги, и для покупателя, так как можно купить реально дешевле (а потом тоже продать).

Надеюсь, почта России одумается и сделает нормальный сервис доставки.

В Лондоне мой любимый книжный - это Foyles на Charing Cross. Ни в Waterstones, ни в Borders не видел столь огромного отдела технической литературы, которая еще и великолепно отсортирована и разобрана по разделам. Например, отдельный шкаф с книгами чисто по компиляторам, или чисто по языку Хаскель, или по QA тестированию, а вдоль стендов про Java или C++ вообще можно ехать на самокате.

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

Куда я первым делом отправился во время визита в Москву на прошлой неделе? В "Библио-Глобус" на Лубянке. Кто знает в Москве офлайновый магазин с большим выбором и лучшей организацией стендов - поделитесь.

Приятно отменить, что очень много переводных книг, причем весьма свежих.

Но еще более приятно, что наша литература ничем не хуже.

В разделе компьютерном купил:

С. М. Окулов, Алгоритмы обработки строк



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

Просто отличная форма изложения: с картинками, диаграммами, пояснениями и примерами. Одна грамотная иллюстрация бывает лучше тысячи слов. Я видел несколько книг Окулова - могу только обоими руками поддержать этого автора. Писать для школьников о сложных алгоритмах - это трудно. А делать еще и понятным языком - особенно.

Вывод: иметь.

Далее, в соседнем разделе математики купил:

С. К. Ландо, Лекции о производящих функциях



Тут прямо на первых страницах этой методички понятнейшим образом объясняется, что такое производящие функции и их применение для решения комбинаторных задач, причем для понимания даже не обязательно вспоминать Анализ. Разбираются классические задачи про правильные скобочные последовательности, числа Каталана, язык Дика и многие другие. Местами там, конечно, жестковато с точки зрения математики, но вводные даются просто великолепно.

Эта книга есть в свободном варианте.

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

http://www.mccme.ru/free-books/
http://e-maxx.ru/bookz/

P.S. Кто знает еще хорошие ссылки по электронным книгам - делитесь в комментах.

суббота, 25 сентября 2010 г.

Функции, указатели на них и оператор "?"

Был удивлен, когда компилятор С съел вот такой забавный способ условного вызова функций:

#include <stdio.h>
#include <math.h>
int main() {
  int i;
  for (i = 0; i <= 1; ++i) {
    float a = (i ? floor : ceil) (10.5);
    printf("%d: %f\n", i, a);
  }
  return 0;
}

Для С++ надо написать:

#include <stdio.h>
#include <cmath>
int main() {
  int i;
  typedef float (*f)(float);
  for (i = 0; i <= 1; ++i) {
    float a = (i ? (f)std::floor : (f)std::ceil) (10.5);
    printf("%d: %f\n", i, a);
  }
  return 0;
}

или

#include <stdio.h>
#include <cmath>
int main() {
  int i;
  for (i = 0; i <= 1; ++i) {
    float a = (i ? std::floorl : std::ceill) (10.5);
    printf("%d: %f\n", i, a);
  }
  return 0;
}

Все программы выводят:

0: 11.000000
1: 10.000000

воскресенье, 19 сентября 2010 г.

Электронные книги - iPad, Kindle, Amazon и все все все

Недавно я обзавелся iPad'ом. Это лучший гаджет, который был у меня в жизни. Но сейчас я расскажу только про один аспект его использования - чтение книг.

Я давно коллекционирую интересные мне книги в электронном виде (pdf, djvu, mobi, epub и т.д.), но они просто лежали, так как читать с экрана в удовольствие я не могу, поэтому я обычно либо печатал на бумагу, или таки покупал бумажный экземпляр.

И вот все изменилось. Чтение накопленных запасов книг получило новый виток - iPad.

Форм-фактор, свечение экрана, время работы (2-3 дня при чтении 2-3 часа в день плюс серфинг через Wifi или 3G), и главное - программы для чтения просто приковывают к этому устройству.

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

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

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

PDF

Если это нормальный файл-исходник, а не пиксельный скан, то можно спокойно пользоваться стандартным приложением iBook и закачивать туда книги через iTunes. Очень грамотная программа для чтения (i-все-таки). Но если приходится иметь дело с pdf'ками, которые по сути являются постраничными сканами (таких "книг" обычно большинство на просторах торрентов), то тут бесспорный лидер - это Good Reader. Очень быстро работает даже с тяжелыми файлами, умеет сам выкачивать файлы из интернета (HTTP, Dropbox, Google Docs, POP3/IMAP и т.д.), и самое главное - умеет делать конфигурируемую "обрезку" страниц. Это о-о-очень полезно. Часто книги отсканированы через пень-колоду, и например, в порядке вещей наличие гигантских отступов-полей, которые могут отжирать и так ограниченное пространство зоны чтения. А "обрезкой" можно персонально для каждой книги (для четных и нечетных страниц также) задать отображаемую часть листа. Вывод: Good Reader - это номер 1.

DjVu

К сожалению, Good Reader не понимает этот формат, а те программы, которые понимают, кривые. Поэтому я просто печатаю DjVu в PDF через PDFCreator и уже PDF заправляю на айпад.

Где брать книги? Конечно, торренты. Тут не надо ничего объяснять.

Отдельно расскажу по технологию Kindle. Это амазоновская читалка. Но есть еще и приложения Kindle для iPhone/iPad/iPod, Android, Windows Mobile, PC и т.д. В чем тут цимес? Для начала - время покупки электронных Kindle-книг на Амазоне исчисляется минутами: выбрал, оплатил и через пару минут книга сама будет закачена на устройство (можно сначала бесплатно скачать preview в виде десятка первых страниц).

Сами книги сделаны очень добротно, с хорошей и удобной версткой. Можно делать закладки, пометки в тексте, а при клике на слово вызывается оксфордовский толковый словарь (жаль, конечно, что не русский подстрочник). Также можно искать по тексту. А теперь ключевая фича - это синхронизация между различными устройствами. Допустим, у меня зарегистрированы читалки: программа-Kindle на PC, на айпаде и на Nexus'е. Все, что делаю с книгой на любой из читалок (ставлю закладки, пометки, позиция чтения) автоматически синхронизируется на другими устройствами.

Теперь я всегда на Амазоне сначала смотрю наличие электронной книги и покупаю ее, если есть (кстати, при покупке электронной версии не должно более быть проблем с доставкой, например, в Россию). Жалко, что пока ассортимент книг несравнимо мал, по сравнению с полным каталогом.

Есть с амазоновскими книгами одно "но". Файлы книг как таковые как бы пользователю не даются. Они видны во всех зарегистрированных читалках, и их можно скачивать повторно, но вытащить напрямую "официально" не получается.

Я написал письмо в Амазон:

Dear Sirs,

I've purchased a few books in Kindle format via Kindle application on iPad and Nexus. I would like to have those books as files (PDF, mobi, ebook etc). How can I get my purchased items this way?

Thanks,
Alexander


Получил ответ:

Hello Alexander,

Content you purchase from the Kindle Store (such as books, newspapers, magazines and blogs) can be read on most Kindle devices or devices running a Kindle application registered to your Amazon.co.uk account. Information about devices that can read Kindle content can be found in our Help pages here:

http://www.amazon.co.uk/kindlesupport

Kindle Store content is not currently viewable on any other electronic reading devices. We don't offer Kindle content in any other formats so you would have to see if they are available elsewhere in different formats to read outside Kindle applications.

I hope this helps.


Значит типа "хрен тебе".

Ясное дело, проще всего покопаться с программой на PC. Файлы с книгами я нашел быстро. Это обычный mobi-формат, но, конечно, зашифрованный. Но если книга читается, когда интернет отключен, значит ключ где-то на самом компьютере, а значит - его можно найти. На просторах интернета нашлась волшебная программа skindle, которая в момент из зашифрованной DRM-ленной книги делает просто mobi-книгу.

И дело не в том, что я мог бы выложить книги в сеть. Я этого делать не буду, так как я за них денег платил, но сам факт ограничения доступа к файлу - это глупость. Хотя надо отметить, некоторые издательства, например "The pragmatic bookshelf" уже продают книги в электронных форматах. При это тебя не ограничивают во владении файлом, делай с ним что угодно. Просто каждая страница в колонтитуле мелким шрифтом содержит твое имя, взятое из данных платежа. То есть файл типа персонализирован. Понятно, это все можно тоже вырезать, но пусть этим занимаются те, кому охота.

Конечно, айпад - это весьма дорогая читалка книг, есть альтернативы, но сам подход электронных книг - это какой-то нереальный скачок вперед.

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

UPDATE: Совсем забыл. Для чтения книг в CHM-формате тоже есть хорошее приложение для айпада.

воскресенье, 12 сентября 2010 г.

Проба на Эрланге

Решал я тут одну красивую задачу. Решение - рекурсивная функция, динамическое программирование.

Для эксперимента написал свою первую программу на Эрланге как решение этой задачи.

Вот оригинал на C++ (рекурсия с кешированием):

bignum f(int n, int k, int t, int& K, vector<vector<vector<bignum> > >& dp) {
  if (n == 0 && k == 0 && t == 0) return 1;
  if (n == 0 || k < 0) return 0;

  if (!(dp[t][n][k] == -1)) return dp[t][n][k];

  bignum ans = 0;

  if (k < K) {
    ans = ans + f(n - 1, k - 1, t, K, dp);
    if (t == 1 || (t == 0 && k < K - 1))
      ans = ans + f(n - 1, k + 1, t, K, dp);
  }

  if (t == 1 && k == K) {
    ans = ans + f(n - 1, k - 1, 0, K, dp);
    ans = ans + f(n - 1, k - 1, 1, K, dp);
  }

  dp[t][n][k] = ans;
  return ans;
}

А теперь Эрланг:

main(_) ->
  N = 50, K = 25,
  io:format("~w\n", [rbs(2*N, 0, 1, K)]).

rbs(0, 0, 0, _) -> 1;
rbs(0, _, _, _) -> 0;
rbs(_, K, _, _) when K < 0 -> 0;

rbs(N, K, 0, MAX_K) ->
  if 
    K < MAX_K-1 -> rbs(N-1, K-1, 0, MAX_K) + rbs(N-1, K+1, 0, MAX_K);
    K < MAX_K   -> rbs(N-1, K-1, 0, MAX_K);
    K =:= MAX_K -> 0
  end;

rbs(N, K, 1, MAX_K) ->
  if
    K < MAX_K   -> rbs(N-1, K-1, 1, MAX_K) + rbs(N-1, K+1, 1, MAX_K);
    K =:= MAX_K -> rbs(N-1, K-1, 0, MAX_K) + rbs(N-1, K-1, 1, MAX_K)
  end.

Красиво, а?

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

#!/usr/bin/env escript

main(_) ->
  N = 50, K = 25,
  io:format("~w\n", [rbs(2*N, 0, 1, K)]).

rbs(0, 0, 0, _) -> 1;
rbs(0, _, _, _) -> 0;
rbs(_, K, _, _) when K < 0 -> 0;

rbs(N, K, 0, MAX_K) ->
  if 
    K < MAX_K-1 -> rbs_memo(N-1, K-1, 0, MAX_K) + rbs_memo(N-1, K+1, 0, MAX_K);
    K < MAX_K   -> rbs_memo(N-1, K-1, 0, MAX_K);
    K =:= MAX_K -> 0
  end;

rbs(N, K, 1, MAX_K) ->
  if
    K < MAX_K   -> rbs_memo(N-1, K-1, 1, MAX_K) + rbs_memo(N-1, K+1, 1, MAX_K);
    K =:= MAX_K -> rbs_memo(N-1, K-1, 0, MAX_K) + rbs_memo(N-1, K-1, 1, MAX_K)
  end.

rbs_memo(N, K, T, MAX_K) ->
  Name = rbs,
  case ets:info(Name) of
    undefined ->
      ets:new(Name, [public, named_table]);
    _ -> true
  end,
  Key = {N, K, T, MAX_K},
  case ets:lookup(Name, Key) of
    [] ->
      Val = rbs(N, K, T, MAX_K),
      ets:insert(Name, {Key, Val}),
      Val;
    [{_, Val}] -> Val;
    Else -> Else
  end.

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

По времени выполнения эрланговый вариант не уступает C++. При это надо учесть, что Эгланге по умочанию арифметика "длинная", а в С++ мне пришлось использовать доморощенный класс bignum.

вторник, 31 августа 2010 г.

Chaos Construction

Закончился в Питере очередной Chaos Construction. Жаль, не удалось побывать самому.

Один из конкурсов, от которого меня реально вставляет – это Realtime Chip Hack.

Вкратце суть: вам дается тестер, пара проводков и светодиодов. С помощью данного нехитрого набора требуется в некоторой реальной работающей схеме определить тип микросхемы, маркировка которой спилена. Еще как вариант – дается устройство-индикатор обратного отсчета (типа бомба). И надо с таким же набором юного сапера ее обезвредить (перерезать дорожку, или наоборот добавить проводок). Но, например, неверное действие может ускорить «бомбу» или просто сразу ее взорвать.

Я однозначно нахожу это крайне близкой темой к reverse-engineer’ингу, где надо просто взять и разобраться, как программа, например, проверяет ключ, и написать ключелку или битхак.

И прелесть тут в том, что все, что отделяет тебя от победы – это не мегабайты кода, а всего 1-2 байтика (или проводочка), которые найти и исправить.

четверг, 26 августа 2010 г.

Снова головоломки или сайт hackquest.com

Любое общение с собратьями по разуму традиционно приносит новые и новые интересные штучки.

На этот раз это сайт hackquest.com. Не знаю, сколько он уже существует, но я только сейчас о нем узнал.

Итак, это сборник разнообразных головоломок на около компьютерные тематики: логика, JavaScript, Java, reverse engineering, криптография, интернет, взломы, Flash, программирование и т.д.

Я вчера посидел пару часов и порешал задачки из своей любимой темы reverse engineering'а. Получил удовольствие.

Рекомендую.

четверг, 19 августа 2010 г.

Роб Пайк критикует С++ и Java

Из этого небольшого видео, где автор и идеолог языка GO Роб Пайк делится своим недовольством языками С++ и Java, я вынес для себя классную мысль: в С++ и Java очень "важно" знать и использовать паттерны (какой уважающий себя программист на этих языках не знает хотя бы одного паттерна?), но наличие паттернов (а особенно их обилие) - это отрицательное свойство! То есть знание языка как такового - это еще полдела, так как затем надо еще и знать "правильные" паттерны.

Вобщем, я становлюсь фанатом этого дядьки.

Update: А комментарий с семью различными типами умных указателей в Бусте - это вообще шедевр.

вторник, 10 августа 2010 г.

Решение кубика Рубика максимум на 20 шагов

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

http://www.cube20.org/

Update: У нас тут есть свои блумберговские кубики, на грани которых кроме цвета нанесена корпоративная атрибутика. Подобное "улучшение" сильно осложняет сборку, так как необходимо правильно сориентировать остов до начала сборки слоев. Причем данная ориентация может съехать при неосторожной попытке сборки начального слоя.

воскресенье, 8 августа 2010 г.

Странные скобки в С++

Недавно более часа потратил на поиск проблемы в куске кода, упрощенный вариант которого привожу ниже:

#include <iostream>
int x;
struct A {
  A(int a) {
    x = a;
  }
};
struct B {
  B(A a) {
    A local_a = a;
  }
};
int main() {
  x = 0;
  std::cout << "Case #0: " << x << std::endl;
  B b1(A(1));
  std::cout << "Case #1: " << x << std::endl;
  int t;
  t = 2;
  B b2(A(t));
  std::cout << "Case #2: " << x << std::endl;
  t = 3;
  B b3((A(t)));
  std::cout << "Case #3: " << x << std::endl;
  return 0;
}

Как вы думаете, что должна вывести эта программа? Числа 0, 1, 2 и 3 последовательно для каждого случая?

А она печатает:

Case #0: 0
Case #1: 1
Case #2: 1
Case #3: 3

Почему для случая #2 не произошло присваивание? Куда делась двойка?

Ответ на этот вопрос кроется в наличии рудиментов языка С в грамматике С++.

вторник, 3 августа 2010 г.

Поиск подстроки в строке: алгоритм Кнута-Морриса-Пратта

Мне понравилась идея недели борьбы с велосипедизмом, посему внесу свою лепту.

Один из частых вопросов, которые задают у нас в Блумберге на интервью в плане так называемого coding exercise (это когда надо на бумаге или на доске написать почти реальный кусок кода) - это поиск строки в подстроке. Это абсолютно жизненная задача.

Подавляющее число людей пишут первое, что приходит в голову - это два вложенных цикла, когда искомая строка последовательно "прикладывается" с каждой позиции исходной строки. Такой подход дает сложность O(M*N), и, очевидно, что в жизни он нереален, если строки более менее длинные. Хотя все при этом знают, что любой hex-вьювер спокойно ищет в огромных файлах за явно линейное время.

Итак, для эффективного поиска строки в подстроке есть алгоритм Кнута-Морриса-Пратта, который решает проблему не за O(N*M), а за O(N+M).

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

P.S. Сразу скажу, у нас никто не просит по памяти писать КМП. И если человек после написания простого O(N^2) решения также скажет, что есть метод быстрее, и сможет описать его идею - этого вполне достаточно.

воскресенье, 1 августа 2010 г.

volatile - это очень сильный модификатор в С++

Как-то по многим блогам эта тема недавно пробегала, но надо отдать должное, вопрос почему эта программа, будучи откомпилированной в Студии, печатает "1" вместо "0", озадачивает даже опытных программистов на С++ (или по крайней мере они дают неправильное объяснение причины происходящего).

#include <iostream>
volatile const char* p = "0";
int main() {
  std::cout << p << std::endl;
  return 0;
}

Для получение схожего эффекта в GCC надо заменить "0" на "false".

четверг, 29 июля 2010 г.

Блог о Великобритании глазами программиста

Завел отдельный блог для моих субъективных заметок о Великобритании.

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

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

Все будет рассматриваться, естественно, через призму оцифрованного мозга программиста, поэтому часть постов будет определенно про профессию программиста в Великобритании.

понедельник, 19 июля 2010 г.

О том, как я «ломал» RSA

Решал я как-то очередную задачу:

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго – шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.

Дано число n (1 ≤ n ≤ 10^5). Найдите такой его делитель (само число n и единица считаются делителями числа n), который лучше любого другого делителя числа n.


Простая задача: ищем все делители n, у каждого делителя считаем сумму цифр, и среди найденного выделяем все делители с минимальной суммой, и уже среди них находим минимальное по значению. Просто надо аккуратно запрограммировать.

Я все сделал, и решение прошло.

Далее была вторая задача:

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго — шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.

Дано число n (1 ≤ n ≤ 10^5000). Найдите такой его делитель d (само число n и единица считаются делителями числа n), что любой другой делитель c числа n лучше, чем d.


По сути, такая же задача, что и предыдущая – просто нужно в паре мест поменять «больше» на «меньше» и наоборот. Я поменял, и на небольших тестах решение прошло.

Но тут я замечаю, что в это задаче верхнее ограничение на n какое-то очень большое. Я заменяют тип «int» на класс «длинной» арифметики (5000 тысяч знаков – пустяк, было и более) и пробую: на малых тестах работает, значит, алгоритм верный.

Посылаю решение, и конечно, получаю ответ «Time limit exceeded». После небольшого раздумья становится ясно, что слишком много надо считать, и подход в целом неправильный.

Пишу письмо Leonid’у с просьбой прояснить ситуацию.

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

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

Нулевые ссылки в С++

Началось с того, что мне предложили взглянуть некий на "интересный" код. Там было что-то вроде:

...
class A { virtual void f() {} };
class B {};

int main() {
  A a;
  try {
    B& b = dynamic_cast<B&>(a);
    if (&b == 0) {
      // ...
    }
  } catch (...) {
    std::cout << "Got it!" << std::endl;
  }
  return 0;
}

Я слегка выпал в осадок от уведенного, а в частности, от строки "if (&b == 0) {". До сего времени я пребывал в осознании факта, что ссылка в С++ либо существует и указывает на реальный объект, либо ее нет вообще. И если тут приведение типа к "B&" не срабатывает, то будет исключение, и управление все равно улетит в другое место, и проверять как-либо "b" бессмысленно.

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

Ну да ладно. Оставим это на откуп странным компиляторам на AIX и SUN, и людям, использующим исключения, но почему-то компилирующие с принудительным их выключением в компиляторе.

Меня заинтересовал другой вопрос: как вообще ссылка может существовать отдельно от объекта. Оказывается, может:

int& a = *(int*)0;
int main() { a = 123; }

Данный код прекрасно компилируется Студией (2010) и компилятором SUN (этот хоть предупреждение выдает), и также прекрасно падается при запуске по понятой причине.

Вы получили ссылку в качестве параметра и думаете, что она лучше чем указатель, так как ее не надо проверять на null? Зря!

пятница, 9 июля 2010 г.

Лекции из MIT

На сайте MITа лежит множество лекций из различных разделов науки. Например, раздел Computer science.

В частности, курс Introduction to Algorithms.

Все сделано максимально удобно: в добавок к видео (некоторые идут сразу с субтитрами) еще есть и транскрипт каждой лекции.

Я еще рекомендую заценить примеры экзаменационных задач.

Честно говоря, берет зависть, насколько там все удобно сделано для учебы.

четверг, 1 июля 2010 г.

Неконстантные ссылки в аргументах функций

У меня есть определенная позиция на использование неконстантных ссылок в С++ в аргументах функций – я стараюсь не использовать неконстантные ссылки для передачи аргументов, которые будут изменены внутри вызываемого блока.

Например, вместо:

void f(T& t) {
  // change ‘t’
}
...
T a;
f(a);

я предпочту передачу по указателю:

void f(T* t) {
  // change ‘*t’
}
...
T a;
f(&a);

Мой основной мотив – наглядность в вызывающем коде. Когда я вижу «&» перед аргументом, я точно знаю, что это возвращаемый параметр, и он может измениться после вызова. И мне не надо постоянно помнить, какие именно агрументы у этой функции ссылки, а какие нет.

Конечно тут есть и минусы: корявость текста в вызываемом коде, так как надо таскать за собой «*» или «->». Также неплохо бы проверять указатель на ноль.

А у вас есть предпочтения в этом вопросе?

суббота, 26 июня 2010 г.

Bloomberg: Вакансии

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

Например, можно зайти в наш раздел вакансий, указать в «Job Function» категорию «Research and Development» (R&D) и получить список открытых позиций для программистов во всех наших офисах.

Я работаю в Лондонском офисе, и поэтому многое из этого поста относится к лондонскому R&D, но в целом, все верно и для остальных офисов.

Например, конкретные вакансии в подразделение «Trading Systems», где работаю я: раз, два и три.

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

Подавляющее количество позиций – это С++ и UNIX, но, например, в мобильную команду (iPhone/iPad/Android/Blackberry) также приглашают специалистов по Objective-C и Java.

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

Как подать резюме? Нет ничего проще – просто послать его через сайт. Многие думают, что такие заявки никто не читает – это неверно. Я сам устроился точно таким же образом. Все читают. Другое дело, часть отсеивается на стадии начального анализа присланных резюме, хотя, я думаю, что на этой стадии отсеивают только полностью неадекватные заявки, когда люди даже не пытаются прочитать требования и хоть как-то отразить это в своем резюме.

Какие шансы пройти? Ничего гарантировать нельзя, но если у вас 4.0 и более баллов на Brainbench на тесте по С++ (не забудьте дать ссылку на профайл в резюме) и более чем пятилетний постоянный опыт больших проектов на С++ , то шанс добраться до телефонного интервью весьма велик. А если вдобавок у вас есть рейтинг на TopCoder’e, CodeForces или что-то в этом роде (также не забудьте дать ссылку), то шансы и на личном интервью очень даже неплохие.

Теперь самая интересная часть марлезонского балета – а как это все работает для граждан России и бывших соцреспублик, у которых нет европаспорта? Могу сказать, что Блумберг может предоставить визовое спонсорство для понравившегося кандидата.

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

Зарплаты? Блумберг всегда адекватен к текущему уровне зарплат на рынке. Насколько я знаю, сейчас зарплаты программистов в Лондоне могут колебаться от 35K до 75K фунтов в год (50K-100K USD) минус 20% налогов Великобритании. Вообще, для ориентации по заплатам и вакансиям можно посетить jobserve.co.uk или monster.co.uk.

А как вообще работается в Блумберге? Интересно (объемы внутренних технологий объять невозможно), динамично (недельные релизы прямиком в онлайновый продакш), разнообразно (тренинги, возможность не уходить в менеджмент, если не хочется), престижно.

Ну и под занавес, как говорится, чтобы два раза не вставать – у нас в Лондонском офисе 22-го июля будет Bloomberg Technology Open Evening – день открытых дверей для разработчиков. Однозначно понимаю, что не все россияне могут так чисто взять и на денек ради этого сюда приехать, на всякий случай – вдруг кому будет-таки полезно, и кто захочет прийти – могу сделать инвайт (пишите на alexander@demin.ws).

Макросы для определения компилятора, библиотеки, операционной системы или архитектуры

Очень полезный проект - http://predef.sourceforge.net/.

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

понедельник, 21 июня 2010 г.

Отладчик в Visual Studio 2010

В отладчике Visual Studio 2010 появилась просто фантастическая штука - отображение трассируемой переменной не где-то в особом окне, а прямо на тексте программы. Это позволяет обращать внимание на переменную, только когда доходишь до ее места в программе.

Лондонское метро - live map

Не уверен, что это будет кому-либо полезно за пределами Лондона, но тут меня поразил сам факт существования подобного сервиса.

Живая карта Лондонского метро - http://traintimes.org.uk/map/tube/

Тут видно движение отдельных поездов.

И опять-таки, идея нереволюционная. Но! Самое важное, что такой сервис есть благодаря public API, официально поддерживаемый Лондонским Метро, которая является полугосударственной структурой. Теперь ясно, откуда такое изобилие приложений для айфона и андроида, предоставляющих разнообразную on-line информацию о метро. Я то думал, они просто парсят страницы официального сайт, а тут, оказывает, все дается на тарелочке.

воскресенье, 20 июня 2010 г.

Блог на английском для носителя русского языка?

Вы пробовали вести блог на английском?

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

Кстати, а вы знаете интересные блоги на английском (хотя бы технические), которые пишут носители русского? (конечно, если человек вырос в английской среде с 5-6 лет, то это не в счет).

fill_n vs memset

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

А вот к чему. Если разобраться, что я могу писать код вообще без С-шных штучек типа массивов, malloc/free, старого способа приведения типов, строчек с нулем на конце и т.д. Получается, что мой диалект С++ можно урезать на тему всего, что я перечислил. Просто убрать, и все.

И от этого будет только польза. Сколько ошибок потенциально я НЕ сделаю в арифметике указателей (ее просто не будет)? Вместо того, чтобы мотивировать человека "разумно использовать наследия С в С++", их надо просто выключить. Конечно, сразу сузится и круг решаемых задач, но мой, кстати, не самый узкий круг, можно покрыть таким вот урезанным в сторону "правильного" С++ диалектом С++.

Например, как мне кажется, функция memset() в мире С++ в целом годится разве что для обнуления. Использование какой-либо иной константы-заполнителя принципиально приближает нас к проблемам с памятью. Хотите, например, "эффективно" заполнить строку пробелами, и зарядите для этого memset(), а потом вам неожиданно придется работать с многобайтовыми кодировками, и этот пробел, записанный через memset(), может стать источником проблем.

Так что используйте алгоритм "fill_n()" вместо "memset()". Может быть неэффективен? Может, а может и нет. Зато уж точно безопасен с точки зрения типизации.

пятница, 18 июня 2010 г.

Google I/O: all videos

Тут собраны все видео с Google I/O 2010, по категориям.

http://code.google.com/events/io/2010/sessions.html

Мне, например, очень понравилась презентация про новую Java машину с JIT в Android 2.2:



И про язык программирования Go:

Сумма цифр числа в Excel'е

Разбираясь с задачей из последней SRM'ки, решил я посмотреть, как будет выглядеть график у функции Y=D(X), где X - натуральное число, а D(X) - сумма цифр его десятичной записи. Оказывается, вот такой хитрой формулой:

=SUMPRODUCT(--MID(A1,ROW(INDIRECT("1:" & LEN(A1))),1))

можно в Экселе посчитать этот самый D(X). Ума не приложу, что это формула значит, но точно работает.

А вот и сам график, кому интересно:

TopCoder SRM 473. Уроки

Сегодня ночью была очередная SRM’ка. Как водится, я узнал сам про себя много нового. Например, я изобрел совершенно уникальный и доселе невиданный метод решения линейной системы из двух уравнений.

Итак, по порядку. Дивизион 2, 75 минут, 3 задачи + 10 минут после на взлом (challenge) чужих решений.

Задача номер 1.

Есть набор куриц и коров. У каждой курицы две ноги и одна голова. У коровы четыре ноги и одна голова. Даны два числа: количество ног и количество голов (каждое число от 1 до 10^6). Надо ответить на вопрос: возможно ли существования некоторого количества куриц и коров при заданном количестве ног и голов.

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

Все просто. Но! В два часа ночи я родил иной подход: перебор! (для системы-то из двух линейных уравнений). Я даже помню ход свох мыслей: так как количество только 10^6, значит можно перебрать все возможные значение количество куриц. Для каждого значения вычислить количество коров, исходя их количество ног и из количество голов. Полученные значения сравнить, и если совпадают, значит найдено возможное решение.

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

Кстати, решение в итоге не прошло системных тестов. И к лучшему.

Задача номер 2.

Дано неограниченное поле, в некоторой точке которого стоит робот. Дана программа для робота – строка, каждый символ которой – команда: «S» - шаг вперед на какую-то константную величину, «L» - поворот налево, «R» - поворот направо. Требуется сказать, будет ли траектория робота, двигающего по этой программе, ограничена конечной окружностью, или робот будет постоянно удалятся от исходной точки. Длина программы для робота до 250 символов.

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

Решение есть. Теперь его надо запрограммировать. Надо было сделать имитацию выполнения программы, то есть команды робота «вперед», «влево» и «вправо».

Приведу фрагмент программы, которую родил мой воспаленный мозг ночью:

...
      if (cmd == 'S') { 
        x += dx; 
        y += dy; 
      } else { 
        if (cmd == 'L' && dx ==  0 && dy ==  1) dx = -1, dy =  0; 
        else if (cmd == 'R' && dx ==  0 && dy ==  1) dx = +1, dy =  0; 
        else if (cmd == 'L' && dx ==  1 && dy ==  0) dx =  0, dy =  1; 
        else if (cmd == 'R' && dx ==  1 && dy ==  0) dx =  0, dy = -1; 
        else if (cmd == 'L' && dx ==  0 && dy == -1) dx =  1, dy =  0; 
        else if (cmd == 'R' && dx ==  0 && dy == -1) dx = -1, dy =  0; 
        else if (cmd == 'L' && dx == -1 && dy ==  0) dx =  0, dy = -1; 
        else if (cmd == 'R' && dx == -1 && dy ==  0) dx =  0, dy =  1; 
...

Даже сейчас я не могу смотреть на это без содрогания. Надо то было всего:

...
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int d = 0;
...
if (cmd == ‘S’) {
  x += dx[d];
  y += dy[d];
} if (cmd == ‘L’)
  d = (d + 4 - 1) % 4;
else if (cmd == ‘R’)
  d = (d + 1) % 4;
...

И все!

Но увы. Когда время ограничено, на ум приходят странные решения.

Хотя мое решение прошло системные тесты, от его вида как-то грустно.

Задача 3.

Дано определение числа Y: Y = X/D(X). X – натуральное число, D(X) – сумма цифр в десятичной записи числа Х. Если Y получается целым, то читается, то Y есть «предок» числа X. Дан интевал чисел от «а» до «b» (каждое от 0 до 10^9), но «a-b» всегда не более 10000.

Спрашивается, сколько есть на данном интервале есть числе Y, у которых нет предка (то есть нет такого Х, чтобы Y был целым).

Итак, для решение перебираем все значения Y от «а» до «b» (их не более 10000). Для каждого Y числа надо проверить, если ли у него «предок». Ясно, что заменатель D(X) принимает только значения от 1 до 81 (число с максимальной суммой цифр – это 999999999, а их сумма 81). Итак, делаем внутренний цикл от 1 до 81, и вычисляем X как X=Y*i (i от 1 до 81). Далее по факту равенста i и D(X) (надо вычислить сумму цифр, составляющих текущее X) можно понять, если ли у текущего Y предок или нет.

Всего итераций будет максимум 10^4 * 81 * 9 ~= 10^6 = 1000000, что вполне реально.

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

Итак, выводы.

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

Заснуть под утро я так уже не смог. Все думал.

воскресенье, 13 июня 2010 г.

Перебор всех разбиений множества на два подмножества

Допустим, есть массив (вектор) v, и надо перебрать все возможные варианты разделения его компонент на два непересекающихся подмножества.

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

vector<int> v(20); // Исходное множество

// Всего вариантов будет: 2^(v.size())-1.
for (int i = 1; i < (1 << v.size()); ++i) {
  vector<int> left, right;
  for (int j = 0; j < v.size(); ++j) {
    if ((i >> j) & 1)
      left.push_back(v[j]);
    else
      right.push_back(v[j]);
  }

  // Текущий вариант множеств left и right готов для обработки.
  ...
}

суббота, 12 июня 2010 г.

return со значением для void-функции

Я как-то думал, что для void-функций оператор return не может иметь ничего, кроме пробелов, перед завершающей его точкой с запятой. Оказывается, что нет. Visual Studio съела без каких-либо жалоб вот такой код:

void v() {}
void f(){ 
  return v();
}

int main() {
  f();
}

Разностная машина из Лего, или динамическое программирование в жизни

Динамическое программирование - это очень интересный и очень эффективный прием. Недаром, огромный пласт олимпиадных задач по программированию посвящен этой теме.

А что в жизни? В жизни-то оно применимо? Конечно!

Итак, разностная машина, построенная из Лего!



Как сказано в описании: "Computing the next entry in a table can be significantly easier than computing an arbitrary entry of the table." - классика динамического программирования.

Вот оно - настоящее Железо!

Ссылки по теме:

пятница, 11 июня 2010 г.

Анализатор последовательностей

Многие задачи в спортивном программировании из раздела динамического программирования сводятся к задаче отыскания формулы какой-либо последовательности.

Формула может быть в замкнутом виде, когда ты просто подставляешь аргументы и разом получаешь результат за время O(1), или в динамической, рекуррентной форме, когда для вычисления i-го члена надо вычислить предыдующие.

Классический пример замкнутой формы - это сумма ряда n положительных чисел:

S(n)=n*(n-1)/2.

А для динамической, или рекуррентной формы - это, например, формула для i-го члена последовательности чисел Фибонначи:

F(i)=F(i-1)+F(i-2).

Например, вот такая задача (для школьников!).

Есть N чисел от 1 до N. Требуется разместить эти числа в ряд слева направо. Первым числом всегда идет 1. Каждое последующее может отличаться от предыдущего не больше, чем на 2. Например:

1 2 3 4 5 ...
1 3 2 4 5 ...
1 3 5 4 2 ...

и т.д. (эта задача есть на Тимусе).

Требудется найти количество возможных размещений по этому правилу для N чисел. N от 1 до 55.

Просто перебором в лоб не получится, так как вариантов будет 55! ~ 10^73, а времени дается всего одна секунда.

Судя по ограничению по времени в 1 секунду, тут просто должна быть формула.

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

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

В итоге, магия произошла. Когда я ввел вычисленные первые элементы последовательности в этот анализатор, мне просто сказали, что формула для i-го члена этой последовательсти: a(n)=a(n-1)+a(n-3)+1. И все! И по данной формуле задача решается пулей одним циклом за O(N).

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

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

среда, 9 июня 2010 г.

Проблемы с delete[]

Имеем следующий код:

#define T 2

class A {
  public:
    virtual ~A() { 
      p = 0;
    }
    int p;
};

class B: public A {
  int a;
};

int main() {
  A* a = new B[T];
  delete[] a;
  return 0;
}

У меня эта программа однозначно падает с "Segmentation fault" на строке "delete[] a". Проверено на Sun C++ на Солярисе, GCC на Линуксе и на FreeBSD. Вот, например, что происходит на BSD:

Program received signal SIGSEGV, Segmentation fault.
0x08048743 in main () at new_array.cpp:17
17        delete[] a;

Забавно, что под Windows в VS2008 ничего особенного не происходит.

Как я понимаю, что в этой программе принципиально важно, чтобы она падала: деструктор класса "A" должен быть виртуальным, дочерний класс "B" должен быть больше по размеру (тут есть член "a"), константа "Т" должна быть 2 или более (то есть мы должны создавать несколько экземпляров класса "B"), и деструктор класса "A" должен что-нибудь писать в свои члены (тут есть "p = 0;").

Что же тут происходит?

new[] создает массив экземплятор класса "B". Оператор же delete[] получает на вход указатель типа "A*" и начинает вызывать деструкторы элементов. Так как деструктор класса "А" виртуальный, то в ход пускается таблица виртуальных функций. Итак, отработал деструктор для первого элемента a[0]. Далее delete[] хочет получить адрес следующего элемента массиве "a". И для этого (внимание!) адрес следующего он вычисляется так: "a + sizeof(A)" (ему же на вход дали указатель типа "A*"). Но проблема в том, что sizeof(A) < sizeof(B) (это дает член класса B::a), и "a + sizeof(A)" будет указывать не на второй элемент в массиве "a", а куда-то между первым и вторым элементом, так как реальный адрес второго элемента - "a + sizeof(B)". И все бы ничего, но деструктор класс "A" пишет в член "p", тем самым меняя содержимое памяти, а так как для второго элемента адрес вычислен неправильно (его this указывает непонятно куда), то куда реально попадет 0 в присваивании "p = 0;" уже никто не знает, но явно не туда, куда надо. Вот и "Segmentation fault".

Другого объяснения у меня нет.

Если кто знает лучше, поправьте.

P.S. Забавно, что под виндами ничего страшного не происходит.

Update: В комментариях дали точное объяснение из стандарта: C++ 2003 5.3.5:
...In the second alternative (delete array), the value of the operand of delete shall be the pointer value which resulted from a previous array new-expression. If not, the behavior is undefined. [Note: this means that the syntax of the delete-expression must match the type of the object allocated by new, not the syntax of the new-expression.]

Update 2: Объяснение, почему не глючит в Visual Studio.

воскресенье, 6 июня 2010 г.

Опрос: как мы называем свою профессию

Создал небольшой опрос: "Как вы говорите про себя, когда вас спрашивают о профессии?".

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

Немного об алгоритмах

Небольшой перерыв в активности блога вызван чудным мегасобытием - рождением второго ребенка. К дочке прибавился сын!

Scheduling для двоих детей, особенно с небольшой разницей в возрасте, конкретно отличается от одного, и является гораздо более сложной оптимизационной задачей, ибо количество переменных увеличивается на порядок. Но в целом - переходный процесс уже начал стабилизироваться, и снова появляется время позависать на всяких сайтах с алгоритмическими задачками (успел даже поучавствовать в двух SRM'ах на TopCoder'е).

Например, сайт Красноярского Дворца пионеров и школьников. Он позиционируется как место для самоподготовки школьников, интересующихся программированием, для олимпиад. Но хвала тем школьникам, которые могут сходу решать задачи сложности 50% и выше с этого сайта. Не всякий, как пишут в резюме, "профессиональный программист с многолетним стажем" сможет "взять" некоторые из них.

Обнаружил просто мега-сайт - e-maxx.ru/algo. Справочник по алгоритмам и их реализациями на С++. Все на русском языке. Как мне тут сказали, что, в принципе, освоив большинство из них, можно показывать неплохие результаты на программистских соревнованиях.

В разделе книг там также отличная подборка.

Из категории, опять-таки, олимпиадного программирования, могу посоветовать:



и



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

Кстати, заметил интересный факт. Лично я не люблю язык Паскаль. Мое субъективное мнение. Многословный и эстетически некрасивый синтаксис. Но Российская школа программирования уважает Паскаль и Дельфи (спасибо вечному Турбо Паскалю 7.0), и поэтому программы в этих книгах написаны на Паскале, а не на С++. И заставляя себя вчитываться в паскалевские куски кода, еще и изуродованные форматированием для печати в книге, получаешь более полное понимание алгоритма. Как говорят: умение читать код может быть даже важнее для программиста, чем писать его.

Далее. Нашел интересную страничну какого-то профессора из MIT, на которой лежат его мини видео лекции с разборами некоторых классических задач динамического программирования. Манера подачи материала очень интересна - видео представляет собой постепенную запись объяснения задачи от руки, сопровожаемую голосом. Например, задача о сдаче, или оба вида задачи о ранце - с повторами и без (0-1).

Алгоритмы - это очень интересно.

Посты по теме:

понедельник, 24 мая 2010 г.

Dropbox

Как-то осознал, что реально подсел на Dropbox.

Как это реально выглядит: просто у меня есть папка, которая автоматически синхронизируется через интернет на любом компьютере, где я залогинен в Dropbox. Не надо ничего вручную копировать и синхронизировать. Ты просто работаешь с локальными файлами, а все в фоне уходит на сервер и оттуда раздается на другие компьютеры.

Все файлы имеют историю ревизий, и их можно делать выборочно публичными. Почти как Google Docs, только есть автоматическое синхронизирование с локальными файлами.

Недавно вышел официальный клиент Dropbox для Android, так что теперь файлы еще и доступны прямо с телефона. Захотел в метро исходничек глянуть или pdf-ку - пожалуйста.

Конечно, класть в эту папку более менее конфиденциальные данные было бы глупо, хотя Dropbox гарантирует их сохранность, но для рабочих документов и исходников - это самое оно. Они и так у меня почти все лежат на Google Code.

Совершенные числа

Решал я тут одну задачу из раздела теории чисел про нахождение совершенных чисел.

В принципе, тривиальная задача. Элементарное разложение на множители.

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

bool is_perfect(long long n) {
  if (n == 1) return false;
  long long s = 1;
  long long q = sqrt((double)n);
  for (long long i = 2; i <= q; ++i) {
    if ((n % i) == 0) {
      s += i;
      if (n/i != i) s += n/i;
    }
  }
  return s == n;
}

...
  bool found = false;
  while (m <= n) {
    if (is_perfect(m)) {
      os << m << endl;
      found = true;
    }
    m += 1;
  }
  if (!found) os << "Absent" << endl;
...

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

И только тут я смотрю на органичения задачи. А именно, что верхняя граница для N - это 5*10^18, то есть если при этом дать M=1, то мой цикл должен будет пробежать ~10^18 значений, что в отведенные на это 2 секунды явно не укладывается.

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

Первый же поиск раскрыл мне суть проблемы - а сколько вообще есть таких совершенных чисел? Оказывается, что на интервале от 0 до 5*10^18 их всего-то восемь, и они уже давно вычислены!

6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128

Поэтому вместо самостоятельного вычисления этих чисел надо просто найти, какие их этих восьми попадают в данный интервал [M, N]. Как говорится "Easy peasy lemon squeezy!".

Естественно, после этого решение успешно засабмитилось.

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

Мораль 2. Есть случаи, когда надо просто знать, как решать тот или иной тип задач. А знать это можно только хотя был раз их прорешав. Можно, конечно, и самому изобрести новый QuickSort с нуля, но это будет уже другая история.

P.S. Сейчас идет Google Gode Jam 2010.

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

Еще интересный момент. В подраунде Round 1B участвовал известный своим юным возрастом "спортивный" программист Геннадий Короткевич (третья позиция сверху таблице результатов). Я всегда очень люблю смотреть решения других людей. Поглядев на его решения, а был реально поражен тем, что они написаны на Дельфи! (а фактически на Паскале) (на Code Jam'е по статистике есть решения и на более "экзотических" языках типа BrainFuck'а или PostScript'а, но такие программы скорее всего сгенерированы из "традиционного" языка, и это уже иная тема). И эти решения кратки и понятны, и не используют различные шаблонные заготовки, которые в целом в ходу в спортивном программировании. Это еще одно подтверждение, что даже для алгоритмических задач "неудобный" язык не является проблемой в написании быстрой и понятной программы.

P.P.S. Один мой друг учавствовал в раунде 1, сидя с ноутом на полу в аэропорту через Wifi. Это не помешало ему получить 127-е место и проход в следующий раунд.

понедельник, 17 мая 2010 г.

Судоку для программистов или олимпиадные задачи

Последнее время радикально подсел на алгоритмические задачки по программированию.

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

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

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

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

И все это – абсолютное знание. Твой единственный судья – это программа проверки результата и тестовые наборы данных, которые одинаковы для всех. Говорят, что на том же ТопКодере есть пути нечестного поднятия рейтинга, но очень несильно. Если посмотреть на топ-листы независимых онлайновых контестов, то можно увидеть там одни и те же имена. Неужели все эти люди знают как «читить» на всех сайтах? Конечно нет.

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

Сайтов для онлайнового решения задач много. Я пока остановился на Школа программиста, Timus Online Judge, UVa Online Judge (классика жанра), Codeforces и, конечно, TopCoder (пока только в practice room’ах).

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

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

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

Если вместо сотни красивых слов в резюме про где и как человек учился и над чем замечательным работал, будет просто указана ссылка на профайл того же ТопКодера, то это будет в сотни раз полезнее. Там тебе и примеры кода, и тематика решенных задач, время из решения (после этого можно не спрашивать, как «человек работает под стрессом»), и, что очень важно с моей точки зрения – страсть к программированию, увлеченность (а как иначе можно объяснить многолетнее постоянное участие в «пустой трате времени», как спортивное программирование).

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

Например, другой товарищ рассказывал, когда его стандартно попросили у нас на интервью нарисовать функцию для вычисления чисел Фибоначчи разными способами – рекурсивно, рекурсивно с хвостовой рекурсией, а затем просто циклом, он написал матричный вариант через производящую функцию, который работает за логарифмическое время, вместо линейного. У товарища, кстати, неплохой рейтинг на ТопКодере.

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

В общем, решайте задачи, тренируйтесь, держите себя в форме.

среда, 12 мая 2010 г.

Плавающая точка уплыла

Решал одну задачу на UVa Online Judge. Долго не мог найти проблему и проверял алгоритм.

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

#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, char* argv[]) {
  double f = 1.15;
  int a = f * 100.0 + 0.1E-9;
  int b = f * 100.0;
  cout << "a = " << a << endl;
  cout << "b = " << b << endl;
  return 0;
}

Я ожидал два числа 115.

Нет, у меня на VS2008 она печатает:

a = 115
b = 114

Вот такие дела.

Update:
Кстати, если попробовать так:

#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, char* argv[]) {
  double f = 1.15;
  int a = f * 100.0 + 0.1E-9;
  int b = f * 100.0;
  cout << "a = " << a << endl;
  cout << "b = " << b << endl;
  double f1 = 0.15;
  int a1 = f1 * 100.0 + 0.1E-9;
  int b1 = f1 * 100.0;
  cout << "a1 = " << a1 << endl;
  cout << "b1 = " << b1 << endl;
  return 0;
}
то результат будет:
a = 115
b = 114
a1 = 15
b1 = 15
Как я думаю, это из-за того, что числа, у которых целая часть нулевая имеют немного особое внутреннее представление в IEEE.

На ТопКодере есть отличная статья на эту тему (часть 1 и часть 2). Все кратко и по делу.

пятница, 30 апреля 2010 г.

Две лекции создателя STL Александра Степанова в Яндексе

Преобразования и их орбиты



Наибольшая общая мера последние 2500 лет



Посты по теме: