Intel® Software Network

В дополнение к "общему вопросу", вызвавшему (и вызывающему) здесь такой ажиотаж, хочу задать один частный, частично продублировав вопросы с американского форума, поскольку здесь нередко высказываются особые мнения, не всегда совпадающие с американскими ;) А вопрос, применительно к только что закончившемуся заданию про грациозные графы, очень интересный: что важнее - быстрота или правильность? Сегодня, просматривая сообщения американского форума, я набрал не маленькое множество сообщений о проблемах с тестированием и отладкой данного задания, даже в судейской программе выявились ошибки! Я отослал стабильно работающую программу, реализующую алгоритм с трудоемкостью порядка ~ O(E!), и отлаживал более эффективную ~ O( E!/(E-N+1)! ),  сегодня я исправил последний (?) баг на 14 мин. позже окончания срока приема заданий, поэтому послать ее не смог. Интересно, что ни в специальной литературе по теории графов, ни в Инете я не нашел алгоритма, эффективно решающего поставленную задачу. Похоже, судей ожидает масса оригинальных алгоритмов, предложеных в наших решениях,  при отсутствии строгих доказательств этих алгоритмов. Все-таки 20 дней - карикатурно малый срок на создание нетривиального алгоритма, его реализацию в многопоточной программе, тестирование и отладку. Точно также 20 дней безумно мало для судей, чтобы со всем этим разобраться и протестировать, тем более что в отличие от предыдущих задач тут нужно гораздо больше тестов (в идеале бесконечно много :) и идут они не в пример дольше... Если будет достаточно много тестов и достаточное внимание будет уделено корректности работы программы и обоснованности алгорима, то первое мое решение имеет  неплохие шансы, в противном случае не надо было копаться с  отладкой 2го решения - пресловутый "последний баг" проявлялся очень редко, далеко не на каждом графе, и выявился в результате долго и муторного теоретического анализа исходного текста программы... 

-- Михаил (mt2)

Хм, вопрос очень интересный. Я по-диагонали просматривал американский форум и тоже для себя его отметил. Есть ответ формальный "точность решения должна соответствовать поставленной задаче", иными словами, если в задании сказано, что точности (допустим) 90% достаточно, то и не следует гнаться за 100%.

С другой стороны, постановка задания и точность измерения (судейства) может содержать погрешности сама по себе. Следовательно, лишняя точность не помешает. Ее-то и оценивают с помощью "дополнительных" баллов. Очевидно, что "дополнительные" баллы - штука очень субъективная, т.е. целиком и полностью зависит от судей. Я не вхожу в жюри конкурса Threading Challenge, но я судил некоторые другие конкурсы и могу сказать, что присуждать "дополнительные баллы" очень непросто.

Теперь по существу. Как вы наверное уже знаете, доктор Клэй - единственный на данный момент судья конкурса. Но я тоже не сидел сложа руки! :)))) Используя свои старые личные связи, я поговорил с менеджером команды TBB, а он, в свою очередь, кинул клич своим инженерам. Насколько я знаю, несколько человек откликнулось, и, быть может, именно с этого задания судей будет больше, а следовательно - судейство будет более объективным (ничего против Клэя, отнюдь! Чистая математика :)).

Что еще приятнее, - скорее всего новые судьи будут русскоговорящими!

Теперь пару слов о графах. В институте у нас был специальный курс по таким алгоритмам, была и настольная книга - "Алгоритмы и структуры данных" Н.Вирта. Кстати, лирическое отступление - почти 20 лет спустя мне удалось лично повидаться с Виртом, но это уже другая история.

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

Так вот, этот мой друг за три дня написал и отладил рекурсивный обход направленного графа (или что-то в этом роде, точно не помню), и что характерно - этот его доморощенный алгоритм был на 30% быстрее чем алгоритм из книжки Вирта.

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

Удачи!

---

Дмитрий Оганезов
Intel® Software Network

MAD\doganezo:

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

Я этого ожидал:

алгоритм работает быстреее потому, что он работает неправильно:

"In this case absolute correctness did not seem as important as speed.  When I submitted my solution I knew that my assumptions were most likely incorrect but they appeared to work most of the time and since I have few points I concluded that it was worth the risk.  Based on what I had seen about there being only 4 test graphs and that heuristics were acceptable despite not being proven I felt that there was a good chance that my solution would compute correct answers for the test cases and that there would not be an issue with the shortcuts I took."  http://softwarecommunity.intel.com/isn/Community/en-US/forums/permalink/30251772/30251850/ShowThread.aspx#30251850

-- Михаил (mt2).

 

Только что прочел: "когда кого-то чем-то награждают, это значит что его работа - пример остальным." Дмитрий Оганезов, Intel® Software Network, http://softwarecommunity-rus.intel.com/isn/Community/ru-RU/forums/permalink/30221136/30221148/ShowThread.aspx#30221148

Дмитрий, совершенно согласен с Вами и поэтому еще больше недоумеваю - какой "пример" мне нужно использовать для дальнейшего участия в конкурсе, если я, конечно, буду и дальше в нем участвовать - некоторые лидеры уже прекратили :(

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

-- Михаил (mt2)

ЗЫ Здесь я еще раз поздравляю победителя - хотя он по-русски, кажется, не читает. Так схохмить на таком представительном конкурсе (=на конкурсе такой известной компании) - это надо суметь!

ЗЗЫ Новый анекдот: сколько будет 2*2? - Если вы пристегнете к решению tbb, то может быть и 5 :)))))))))))))) -- план по смайликам выполнен :)