Jakob писал(а):Ну, почти как выборы президента на Украине,
Да ну что Вы, коллега,
Это всего лишь маленький конкурс. На самом деле его ценность и не в победе вовсе. Я вот каждое утро начинаю с разминки на десять - пятнадцать минут за чашкой кофе. Маленький программистский этюд. Форумы — прекрасный источник для таких задачек. Например как прибить другое приложение из Лабвью, либо определить установленный язык в системе, либо вот такой вот конкурс с битами и байтами. Это прекрасная возможность не дать мозгам заржаветь и прекрасно начать рабочий день. Ну и очень интересно посмотреть на проблемку глазами другого человека.
Что же касается судейства - так надо просто убрать голосовалку вовсе и судить секундомером, вот и всё.
Кроме того не вижу препятствий тому, чтобы автор задачки сам участвовал. Я бы вот проголосовал за решение автора, если уж на то пошло. Единственное преимущество, которое есть у автора - это время. Ну так и конкурс вполне можно растянуть на месяц.
Ну на самом деле можно было сделать продолжительность голоосвания чуть больше суток :). Я вот только щас добрался до анализа решений и проголосовать не успел.
ИМХО, все очевидно, решение №3 вне конкуренции. Но раз довели дело до второго тура, то проголосую за решение №5 - шутка
Jakob писал(а):Ну, почти как выборы президента на Украине
Да-да. Очень смахивает . Даешь тоталитарную диктатуру :))
По делу:
Решения 1, 2, 5 - алгоритм одинаковый (детали реализации не учитываю). Самый простой и логичный с т.з. , но не самый оптимальный. Много лишних операций + памяти больше кушает.
Решения 3, 4 - алгоритм одинаковый (детали реализации не учитываю). Самый логичный с т.з. производительности, но реализация чуть сложнее (хотя и с этим можно поспорить взглянув на код mzu).
В решении #3 присутствует одно серьезное отличие: автор использовал 2 параллельных цикла. Результаты говорят сами за себя. Голосую за №3.
AndreyDmitriev, спасибо большое за коррективы, обязательно их учтем при проведении следующего конкурса. Однако на данном этапе, повторюсь - правила менять уже поздно, т.к. номинанты при создании своих работ руководствовались в том числе тем, как проводилось судейство в предыдущих конкурсах. Так будет справедливо по крайней мере. Jakob, Forward, Ну я бы не сравнивал это с выборами президента в Украине, скорее ближе другое событие - олимпиада в Ванкувере
А второй тур можете считать фотофинишем
По поводу же учета затраченного времени на создание работы - я думаю можно этот параметр добавить, спасибо. Однако тут участникам надо быть очень осторожными - т.к. быстрое решение как правило не всегда самое верное. mzu2006, спасибо за организацию второго тура! Я думаю голосование целесообразно сделать до ближайшей пятницы, т.к. в России сейчас начались праздники и посещаемость упала, а первый рабочий день у нас - среда.
Обещанный краткий технический комментарий.
Решения разбились на 3 типа в зависимости от поведения зависимости времени вполнения то количества битов.
1 тип - решения, где скорость выполнения почти не зависит от количества битов (Solution02, Solution05, SolutionIncluded). Все они выполнены по одной схеме, где входной массив превращается в массив boolean целиком, потом массив boolean разбивается на кусочки нужной длины и всё это собиратеся в выходной массив. Видимо, основное время уходит на разбиение массива на биты и последующее нарезание на куски. Когда N мало, то начинает проявляться зависимость от N (маленький хвостик в самом начале графика). Из всех решений этой группы Solution05 обладает самой красивой диаграммой. Преимущество, достигнутое распараллеливанием в Solution02 - невелико.
2 тип - скорость выполения убывает с ростом N. (Solution03, Solution04, SolutionMZ, SolutionDLL). Во всех этих решениях использованы битовые операции над целыми числами (сдвиги и послдующая маскировка ненужных битов). Во всех в них главный счётный цикл считатет до количества элементов в выходном массиве, которое ~1/N, отсюда и характерная зависимость. По-видимому, как заметил AndreyDmitriev, основное время отнимает операция индексирования, сдвиги и or/and происходят достаточно быстро. За счёт этого решения Solution04 и Solution05 вырываются вперёд. Solution03 оптимизирвано под 2 ядра + Solution03 содежит всего лишь 1 case структуру внутри себя, что обеспечивает лидерство по быстродействию. (дажев версии Soluton03a - на одном ядре). Решение Solution04 отличается грамотными комментариями к блок диаграмме. Solution03 - рассмотрением частных случаев 1,2,4,8,16, 32 бита (Это видно на графике, в точках 8 и 16. NB! Масшаб логарифмический).
3 тип - Solution01, где с массивом обращаются как с потоком. Решение очень инуитивное и доходчивое. Немного тормозит, видимо, из-за Delete From Array, которая вынуждена отвести дополнительный буфер (он не отводится в решениях 1-го типа) и из-за разборки входного массива на элементы по одному элементу, а не все сразу. почему зависимость такая "скачущая" сказать не берусь.
Последний раз редактировалось mzu2006 23 фев 2010, 05:00, всего редактировалось 1 раз.
Выигрывает программа переработавшая один и тот же массив из 1000000 элементов за меньшее время на наборе N=1..31. В случае статистической неразличимости результатов разных участников, оценивается стиль написания блок-диаграммы (компактность) голосованием.
Почему-то я посчитал, что эти слова расположенные после ссылки на "Виртуальный Задачник" отменяют соответствующие пункты оценки "Виртуального Задачника". Видимо, в следующий раз надо будет это оговаривать явно.
2. Да, голосование идёт до следующей пятницы - это логично.
3. Я за участие автора в конкурсе. Просто, ведущим должен быть кто-то другой.
4. Конечно ценность не в победе, а в разминке мозгов.
mzu2006 писал(а): Почему-то я посчитал, что эти слова расположенные после ссылки на "Виртуальный Задачник" отменяют соответствующие пункты оценки "Виртуального Задачника". Видимо, в следующий раз надо будет это оговаривать явно.
Конечно надо оговаривать. У меня например и мысли такой не возникло, что они что-то отменяют. Вернее у меня возникла мысль, что этот параметр просто развернутый пункт общих правил оценки "Скорость выполнения кода". То что он отменяет остальные пункты - сказано не было.
Поздравляю Андрей! Неплохая разминка для мозга получилась.) Ты награждаешься медалью за победу в конкурсе "Виртуальный задачник". Когда Женя появится, он тебе её вмонтирует в профайл! Надеюсь на такое же активное участие в последующих конкурсах из этой серии
Так же поздравляю Jacob! Пусть твое решение оказалось не самым быстрым, но зато там самый минималистичный код, а это тоже очень существенный параметр по моему мнению, по крайней мере в части касающейся правки кода через несколько лет. Своим примером ты показал к чему надо стремиться в написании программ!
Спасибо большое Михаил за отличное и интересное проведение конкурса причем на всех этапах от идеи разработки задания до финала! Ждем еще таких же блестящих и интересных идей!
Остальным претендентам - спасибо больше за участие в конкурсе! AndreyDmitriev, Jakob, mzu2006, - от меня +5
Всем спасибо за участие , интересно и полезно было вглянуть на другие варианты после относительной "зашоренности" на своем. mzu2006 - отличная организация .