Nomen est omen

Представим себе гипотетическую ситуацию: некий юноша-с-косичкой подрядился писать программу. Ну хотя бы учет посетителей в библиотеке. (Ещё ни одной приличной не видел) И вот доходят у него руки до учета пользователей и он радостно создает в базе табличку visitors {firstName, lastName, middleName}. А что, у всех буквально есть фамилия, имя и отчество. Вот у его знакомых в родном Крыжополе точно у всех. Да и девочка-библиотекарь, которая заместо аналитика, говорит что так правильно. И вот поступает такая система в эксплуатацию. А там кого только нет: и Александров-Погорельский, Ли Син Цин, и Хосе Луис Мария Педро Фернандос. И вот мучаются библиотекари, стараясь всунуть чуждые имена в прокрустово ложе программы, сыплются проклятья и летят в сторону незадачливого юноши лучики поноса.

Произошло это потому, что незадачливый программист не разобрался в сути моделируемых явлений. На больших объемах данных такой подход очень редко сходит с рук — всегда найдутся выпадающие данные, даже если на первый взгляд их быть не должно. Хороший пример: тройные фамилии вроде бы как запрещены законодательно, по крайней мере просто так её взять не получится. Возникает соблазн добавить проверку, и соблазн довольно опасный. Вероятность того, что системе попадется человек с тройной фамилией довольно велика на большой выборке. Аллах знает, как у них это получается, но сменить человеку фамилию можно только через суд.

Ещё одна распространенная ошибка — трактовать отчество как middle-name. Мне попадался даже один декан, который подписывался Boris A. Gladkih, видимо, не подозревая, что читается это как Борис Афанасий Гладких, что суть нонсенс. Второе имя это именно самостоятельное имя, которое можно использовать отдельно, пусть даже оно и дается в честь отца или деда. Отчество же без имени употребляется исключительно в качестве прозвища и только отдельно от фамилии: «Кузмич — за пивом пойдет». На эти грабли качественно наступили создатели формата fb2.

В наш век всеобщей глобализации правильнее не задумываться над традициями присвоения имен, а признать, что человек может сам выбрать как ему называться. Технологически, ничего сложного в этом нет, если только вы не хотите поддерживать все возможные традиции именования. Зато, если завтра к вам придет посетитель, у которого в паспорте написано «БОЧ рВФ 260602 Вячеславович Воронин-Фролов» вы будете к этому готовы.

ICFP '08 Contest

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

Preambula

Про ICFP contest я узнал начитавшись отчетов и сразуже захотел попробовать. Этот контест выгодно отличается от ненавистных мне «академических» олимпиад и их идиотскими заданиями, не имеющими ни малейшего отношения к реальности. Поскольку по одним субъективными отчетам трудно достоверно оценить явление было решено потрогать воду лапкой прежде чем готовиться к участвовать всерьез. Что и было проделано с величайшим удовольствием. Однако, некоторую подготовку я все же провел: настроил NetBeans с Ruby, создал необходимую структуру папок для проекта, поднял на всякий случай Linux под виртуальной машиной, скачал и запустил LiveCD

Day 0. Landing

За час до начала вылезаю на канал #icfp-contest и наблюдаю там больше 200 человек. С трудом дожидаюсь публикации задания. Большого смысла в этом нет, но хочется уже прочесть его, составить план штурма и отправится спать. Время из-за разницы во времени довольно позднее. В час «X» вся эта толпа, коей набралось уже за 300 человек радостно тянется качать задание и на несколько минут роняет сервер. Наконец я добираюсь до нужного документа и погружаюсь в чтение. Итак, задача этого года, в моем кратком изложении

Есть квадратное поле заданных размеров, представляющее поверхность Марса. На поверхности имеются:

1. кратеры, в которые можно упасть, насмерть, много;
2. валуны, о которые можно стукнуться, больно, тоже много;
3. марсиане, которые норовят сожрать, самоходные, много;
4. база, дружественная, одна;
5. марсоход, свой, один.

На поверхность в произвольной точке высаживают марсоход (с довольно реалистичной физической моделью) для которого нужно написать программу управления (общающуюся с сервером по TCP/IP), приводящую его к базе в обход кратеров, валунов и марсиан. Соревноваться в итоге будут программы между собой, у кого лучше, тот и победитель. В деталях, оригинал на 12 страницах.

Прочитав задание, понимаю, что Ruby тут не при делах. Марсоход — железка глупая, не станет ждать пока досчитается, укатится к черту на рога. Решаю применить запасной вариант и использовать Java. Пока разворачивается IDE, лезу качать симулятор, но его ещё не выложили. Основных проблем в задании видится три: 1) Сетевой протокол; 2) Алгоритм управления; 3) Визуализатор для отладки. За пару часов реализую сетевой протокол, описываю необходимые структуры данных и с чистой совестью отправляюсь спать

Day 1. Doctrine: Mobility

Пока я спал, организаторы выложили симулятор, а участники в чате и рассылке развели невообразимый флейм. Быстро скачав симулятор, проверяю свой код. Сетевой протокол работает без отладки. В симуляторе оказывается встроенный визуализатор, так что от одной задачи я на некоторое время избавлен. Несколько часов уходит на то, чтобы научить марсоход ехать в заданную точку. Дело продвигается медленно, потому как тригонометрию я напрочь забыл, уж слишком давно не делал ничего подобного. Когда первая карта проходит отправляюсь кататься на велосипеде, а вечером принимаюсь за объезд препятствий. Лобовое решение, отворачивать от препятствия расположенного в опасном угле по курсу работает плохо. Объехав первый кратер, марсоход сослепу ухает во второй. Мне подкидывают идею, предсказывать положение марсохода на несколько ходов. Решаю заняться этим завтра и отправляюсь спать.

Day 2. Doctrine: Flexibility

Со вчерашнего дня обнаружилась ещё одна проблема: перерегуляция, приводящая к том, что марсоход пролетает мимо базы. Решил сперва побороть её и ввел эвристики, запрещающие крутые повороты вдали от базы для наведения на цель. С предсказанием все плохо, марсоход едет довольно паршиво, часто падает в кратеры и стукается о валуны. Приседания с параметрами дают немного. Это продолжается до тех пор, пока я не начинаю проверять точность предсказаний в реальном времени. Сперва обнаруживается, что я забыл учесть трение и предсказания скорости не слишком точны. Добавив систему оценки трения и ускорения, получаю точность предсказания скорости до четвертого знака. Выглядит хорошо, но точность предсказания расстояния не изменилась. Проверяю расчеты калькулятором и обнаруживаю, что java.lang.Math принимает аргументы синусов и косинусов в радианах, а я считаю углы в градусах. Правлю и точность hgtlcrfpfybq достигает требуемой. Поскольку нет необходимости в играх с параметрами, устанавливаю предсказания на 5 секунд вперед. Все три тестовые карты проходятся, так что я начинаю искать, на чем бы ещё протестировать. Поскольку возможности достать и померяться прямо в процессе организаторы не предусмотрели народ во всю обсуждает результаты и выкладывает собственные карты. Пытаюсь протестировать на чужих картах и обнаруживаю два факта: а) на рандомных картах сходных с тесовыми все работает идеально; б) стенки, «рюмки», «бутылки», лабиринты и прочие непрерывности вводят марсоход в ступор. На этой прекрасной ноте отправляюсь спать.

Day 3. Doctrine: Initiative

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

Conclusions

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

Date, Time, Interval, and Duration

С представлением времени в большинстве систем творится полный бардак. Ладно, RDF с OWL’ем, там и без этого все плохо, но даже в стандартных библиотеках самых что ни на есть мейнстримных языков полный бардак. Ну что нужно курить чтобы в стандартный класс Date добавить преобразование к Юлианскому календарю? Ни разу не встречал человека, которому бы это потребовалось. Зато вычислять интервал между двумя событиями приходится вручную. Давайте попробуем спроектировать библиотеку для работы со временем правильно. Может хоть кому-нибудь живой пример вправит мозги.

Итак, что такое время для программиста? Это одна координатная прямая, на которой определена выделенная точка «сейчас», делящая прямую на «прошлое» и «будущее». Примитивные племена на этом и останавливаются, оперируя тремя понятиями: «было», «есть» и «будет». Современному человеку требуется больше: время должно быть измеримо. Это позволит производить вычисления (до сеанса осталось полчаса) и учитывать порядок событий ([сначала]он мне в глаз, а [затем] я ему в ухо) от которого и до причинно-следственной связи недалеко. Для того чтобы сделать время измеримым на прямую произвольным образом добавляют фиксированную выделенную точку «0». Исторически сложилось так, что в разных культурах эту точку добавляли по-своему. Это мог быть день коронования императора, начало определенного года, произвольно выбранный момент времени и даже время «сотворения мира». В мире UNIX, например, это полночь 1 января 1970 года.

С другой стороны люди привыкли к довольно неудобной для вычислений системе предстваления времени, связанной с циклами вращения Земли. Опять же, в разных культурах к этой проблеме подходили по разному. В результате год начинается в разное время и по разному делится на месяцы в зависимости от культуры. Более того, в разных культурах привычные способы записи времени сильно отличаются, даже если системы счисления времени совпадают. Та же американская ММ/ДД/ГГ и русская ДД.ММ.ГГ.

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

Поскольку продолжительность суток растет, каждые несколько лет к UTC добавляют секунду, чтобы компенсировать замедление. Это тоже усложняет точные расчеты, однако, пока не вызывает проблем, поскольку единой системы точного времени затрагивающую все — от GPS приемников до кофеварок не создано.

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

Первое, что нам требуется, это момент времени (Timestamp) заданный с максимальной возможной точностью в некоторой системе отсчета, хоть UNIX time. Этот класс является платформозависимым, поскольку умеет работать с системным таймером. Никаких преобразований или вычислений этот класс делать не должен. Очень часто требуется работать с моментами времени с точностью до минуты, дня или года, в этом случае максимальное разрешение тут только мешает. Для некоторой частых случаев можно определить классы Date и DateTime и точностью, соответственно, до дня и до секунды. Timestamp должен корректно поддерживать сравнение отметок времени с максимальной и ограниченной точностью.

Второе — интервал между двумя моментами времени (Interval) Интервал можно представить двумя моментами времени: начало интервала и конец интервала. Интервал должен уметь вычислять свою продолжительность. Кроме того, нужна возможность зная начало или конец интервала и продолжительность, получить интервал.

Третье — продолжительносить (Duration) Внутри продолжительность хранится в максимально возможной системной точностью.

Для каждой из трех сущностей потребуется два интерфейса: *Parser и *Formatter имплементации которых служат для преобразования сущностей из строки и к строке (или прочим типам). Кроме форматирования, их зона ответственности — преобразование к другим системам представления времени, например к тому же юлианскому календарю.

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

duration = Duration.measure do
...
end