Epic fail

[thedeemon]

Когда в третьем номере ПФП объявили конкурс, я обрадовался, думал поучаствую, всем покажу. Времени было дано много, можно было не спешить. Я все откладывал, откладывал, а потом внезапно подкрался дедлайн, и я счастливо конкурс пропустил, так и не приступив. Но вдруг окончание конкурса отложили, а в свежем номере журнала упомянули языки присланных решений, и среди них не оказалось Окамла. Тогда в последний момент я все же решил одну задачку сделать; не для победы, так хоть для статистики. Делать взялся экстремистскую задачу про вырезание Московской области из России (условие тут). Интересная часть задачи - определение принадлежности точки произвольной фигуре из ломанных - сделалась очень быстро и проще, чем я ожидал, а вот занудная часть - чтение карты из XML и запись результата - отняла большую часть времени и составила большую часть программы. В итоге для разбора карты был использован ocamlyacc, сгенеренный им парсер превращен в функтор (параметризованный модуль), который дергает callback'и из переданных в качестве параметра модулей обработки. При такой схеме решение все насквозь императивное, при этом во время парсинга выделяется куча мелких строк и списков, списки переворачиваются и многократно обходятся создаваемыми на лету замыканиями, отсюда большая нагрузка на GC, все тормозит и вообще некрасиво.

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

В общем, с моей стороны полный фейл, в другой раз постараюсь не откладывать все на последний момент.
Статистика: всего дней, когда хоть немного занимался решением - 3, чистого времени на разработку - 15,5 часов, исходники - 580 строк Окамла (включая файлы для ocamllex и ocamlyacc, но не включая сгенеренные ими), скорость вырезания московской области из двухгиговой карты РФ на рабочем компе - 2,5 минуты в простом режиме и 4:45 в режиме complete objects.

Comments

[lionet.livejournal.com]

Твоё решение по крайней мере до меня дошло. Не потеряется.

[nealar.livejournal.com]

Гмэйл урод.

[lionet.livejournal.com]

Именно поэтому у меня пункт — свой почтовый домен держать у себя. Позволяет спама больше получать.

[nealar.livejournal.com]

Мне однажды пришлось на машине инсталлятор везти. Сначала локальный антивирь отшил, потом конторский почтовый сервер на что-то вырубился(вроде, не на экзешник) , потом "дальний" почтовый сервер, потом я переименовал файлик (хорошо, что ИнфоДжет свой либмагик ещё не внедрил везде), потом на дальнем сервере что-то отломилось(инет упал?), потом был выходной, потом письмо ещё по какой-то причине отшили. В итоге, взял флэшку и поехал в соседний город. Если без пробок - час-полтора в один конец. Так уж повезло, что заказчики жили рядом, хотя работали за 100 км.

Мне кажется, считать каждый экзешник зловредным - это epic fail. Таким способом утверждение "винда - это постоянные черви, трояны, руткиты, вирусы, змеи и жабы" переносится из фольклора красноглазиков в реальный мир.

[sleepy-drago.livejournal.com]

проф любопытство :) Какую сложность имеет "определение принадлежности точки произвольной фигуре из ломанных" сделанное за "очень быстро"?

[thedeemon.livejournal.com]

Логарифмическую.

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

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

В случае московской области (~1500 отрезков) скорость была около 2 миллионов проверок на принадлежность точки в секунду.

[thedeemon.livejournal.com]

С учетом того, что на карте РФ всего около 10 миллионов точек, их все можно проверить за 5 сек, но вот банально прочитать двухгиговую карту с диска - на порядок дольше.

[sleepy-drago.livejournal.com]

спасибо.
с геом. т.зр. алгоритм (custom sweep line with count) очень хороший выбор. Единственный нюанс как обрабатывались множества запросов на inside/outside. Но на 10млн это не существенно.

зы Да с дисками именно такой баланс для mostly linear операций - ждем флеш стораджа прямо на шине :)

[sleepy-drago.livejournal.com]

ну и на 100+млн понадобилось бы partitioning сверху нацепить