[Задача] Разбить битовый массив [до 16.02.2010]

Различные конкурсы нашего портала

Какое из решений наиболее достойно?

Опрос закончился 19 фев 2010, 00:00

Solution01
0
Голосов нет
Solution02
0
Голосов нет
Solution03
3
50%
Solution04
1
17%
Solution05
2
33%
 
Всего голосов: 6

AndreyDmitriev

Activity Professionalism Tutorials Gold Black
VIP
VIP
Сообщения: 1327
Зарегистрирован: 03 фев 2010, 00:42
Награды: 6
Версия LabVIEW: 6.1 - 2024
Откуда: Германия
Благодарил (а): 1 раз
Поблагодарили: 38 раз
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение AndreyDmitriev »

Jakob писал(а):Ну, почти как выборы президента на Украине,
Да ну что Вы, коллега,

Это всего лишь маленький конкурс. На самом деле его ценность и не в победе вовсе. Я вот каждое утро начинаю с разминки на десять - пятнадцать минут за чашкой кофе. Маленький программистский этюд. Форумы — прекрасный источник для таких задачек. Например как прибить другое приложение из Лабвью, либо определить установленный язык в системе, либо вот такой вот конкурс с битами и байтами. Это прекрасная возможность не дать мозгам заржаветь и прекрасно начать рабочий день. Ну и очень интересно посмотреть на проблемку глазами другого человека.

Что же касается судейства - так надо просто убрать голосовалку вовсе и судить секундомером, вот и всё.

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

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение mzu2006 »

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

Таким образом, мы имеем 2 претендента в финале.
Решение 3 и Решение 5.

Открылся второй тур голосования: http://www.labviewportal.org/viewtopic.php?f=179&t=1852

Пожалуйста, выражайте свои мнения.
Аватара пользователя
Forward

Activity Tutorials Black
professional
professional
Сообщения: 337
Зарегистрирован: 03 мар 2008, 12:41
Награды: 3
Версия LabVIEW: 2010
Откуда: Кишинев
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение Forward »

Ну на самом деле можно было сделать продолжительность голоосвания чуть больше суток :). Я вот только щас добрался до анализа решений и проголосовать не успел.
ИМХО, все очевидно, решение №3 вне конкуренции. Но раз довели дело до второго тура, то проголосую за решение №5 :D - шутка
Jakob писал(а):Ну, почти как выборы президента на Украине
Да-да. Очень смахивает :D . Даешь тоталитарную диктатуру :))

По делу:
Решения 1, 2, 5 - алгоритм одинаковый (детали реализации не учитываю). Самый простой и логичный с т.з. :labview: , но не самый оптимальный. Много лишних операций + памяти больше кушает.
Решения 3, 4 - алгоритм одинаковый (детали реализации не учитываю). Самый логичный с т.з. производительности, но реализация чуть сложнее (хотя и с этим можно поспорить взглянув на код mzu).
В решении #3 присутствует одно серьезное отличие: автор использовал 2 параллельных цикла. Результаты говорят сами за себя. Голосую за №3.
Аватара пользователя
Pavel Krivozubov

Activity Bronze
professor
professor
Сообщения: 4421
Зарегистрирован: 07 фев 2008, 16:39
Награды: 3
Версия LabVIEW: 7.0 - 2013
Откуда: г. Электросталь
Благодарил (а): 24 раза
Поблагодарили: 9 раз
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение Pavel Krivozubov »

AndreyDmitriev, спасибо большое за коррективы, обязательно их учтем при проведении следующего конкурса. Однако на данном этапе, повторюсь - правила менять уже поздно, т.к. номинанты при создании своих работ руководствовались в том числе тем, как проводилось судейство в предыдущих конкурсах. Так будет справедливо по крайней мере.
Jakob, Forward, Ну я бы не сравнивал это с выборами президента в Украине, скорее ближе другое событие - олимпиада в Ванкувере :D
А второй тур можете считать фотофинишем :D
По поводу же учета затраченного времени на создание работы - я думаю можно этот параметр добавить, спасибо. Однако тут участникам надо быть очень осторожными - т.к. быстрое решение как правило не всегда самое верное.
mzu2006, спасибо за организацию второго тура! Я думаю голосование целесообразно сделать до ближайшей пятницы, т.к. в России сейчас начались праздники и посещаемость упала, а первый рабочий день у нас - среда.
Аватара пользователя
mzu2006

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение 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 раз.
Аватара пользователя
mzu2006

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение mzu2006 »

Пару комментариев по ведению:

1. Я изначально имел в виду оценку секундомером.
Выигрывает программа переработавшая один и тот же массив из 1000000 элементов за меньшее время на наборе N=1..31. В случае статистической неразличимости результатов разных участников, оценивается стиль написания блок-диаграммы (компактность) голосованием.
Почему-то я посчитал, что эти слова расположенные после ссылки на "Виртуальный Задачник" отменяют соответствующие пункты оценки "Виртуального Задачника". Видимо, в следующий раз надо будет это оговаривать явно.

2. Да, голосование идёт до следующей пятницы - это логично.

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

4. Конечно ценность не в победе, а в разминке мозгов. :drink:
Аватара пользователя
Pavel Krivozubov

Activity Bronze
professor
professor
Сообщения: 4421
Зарегистрирован: 07 фев 2008, 16:39
Награды: 3
Версия LabVIEW: 7.0 - 2013
Откуда: г. Электросталь
Благодарил (а): 24 раза
Поблагодарили: 9 раз
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение Pavel Krivozubov »

mzu2006 писал(а): Почему-то я посчитал, что эти слова расположенные после ссылки на "Виртуальный Задачник" отменяют соответствующие пункты оценки "Виртуального Задачника". Видимо, в следующий раз надо будет это оговаривать явно.
Конечно надо оговаривать. У меня например и мысли такой не возникло, что они что-то отменяют. Вернее у меня возникла мысль, что этот параметр просто развернутый пункт общих правил оценки "Скорость выполнения кода". То что он отменяет остальные пункты - сказано не было.
Аватара пользователя
Pavel Krivozubov

Activity Bronze
professor
professor
Сообщения: 4421
Зарегистрирован: 07 фев 2008, 16:39
Награды: 3
Версия LabVIEW: 7.0 - 2013
Откуда: г. Электросталь
Благодарил (а): 24 раза
Поблагодарили: 9 раз
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение Pavel Krivozubov »

крупье ставит музыкальную паузу :D
<object width="425" height="344"><param name="movie" value=" name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="425" height="344"></embed></object>
Аватара пользователя
mzu2006

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение mzu2006 »

Победителем стал ....
Аватара пользователя
mzu2006

Professionalism Tutorials Black
doctor
doctor
Сообщения: 2456
Зарегистрирован: 16 авг 2008, 02:12
Награды: 3
Версия LabVIEW: 7.1 10 11 12
Откуда: St-Petersburg (RU), Phila, Boston, Washington DC
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение mzu2006 »

AndreyDmitriev c решением Solution03. Поздравляю, Андрей!!! Андрей получает медаль за победу в конкурсе.

На втором месте по результатам второго тура Jackob с решением Solution05.

Большое спасибо всем участвовашим:

solution0 1 - eg
solution02 - FireFly
solution03 - AndreyDmitriev
solution04 - Forward
solution05 - Jackob

Доставило большое удовольствие покопаться в ваших решениях.

Как обещано, Forward и AndreyDmitriev + к карме.

Indey, Награди медалью, plz

Пароль к Dumb.vi - "dsfjhby@#$jn*((32412!@$54777745@!". Она больше всего похожа на решение 02 и 05
Последний раз редактировалось mzu2006 26 фев 2010, 16:20, всего редактировалось 1 раз.
Аватара пользователя
FireFly

Activity Black
expert
expert
Сообщения: 1321
Зарегистрирован: 25 апр 2009, 08:58
Награды: 2
Версия LabVIEW: 2014
Откуда: Санкт-Петербург
Поблагодарили: 1 раз

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение FireFly »

:clap:
Иногда лучше молчать и слыть идиотом, чем заговорить и развеять все сомнения.
Аватара пользователя
Pavel Krivozubov

Activity Bronze
professor
professor
Сообщения: 4421
Зарегистрирован: 07 фев 2008, 16:39
Награды: 3
Версия LabVIEW: 7.0 - 2013
Откуда: г. Электросталь
Благодарил (а): 24 раза
Поблагодарили: 9 раз
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение Pavel Krivozubov »

Поздравляю Андрей! Неплохая разминка для мозга получилась.) Ты награждаешься медалью за победу в конкурсе "Виртуальный задачник". Когда Женя появится, он тебе её вмонтирует в профайл! :D Надеюсь на такое же активное участие в последующих конкурсах из этой серии :super:
Так же поздравляю Jacob! Пусть твое решение оказалось не самым быстрым, но зато там самый минималистичный код, а это тоже очень существенный параметр по моему мнению, по крайней мере в части касающейся правки кода через несколько лет. Своим примером ты показал к чему надо стремиться в написании программ!
Спасибо большое Михаил за отличное и интересное проведение конкурса причем на всех этапах от идеи разработки задания до финала! Ждем еще таких же блестящих и интересных идей!
Остальным претендентам - спасибо больше за участие в конкурсе!
AndreyDmitriev, Jakob, mzu2006, - от меня +5 :super:
Аватара пользователя
Forward

Activity Tutorials Black
professional
professional
Сообщения: 337
Зарегистрирован: 03 мар 2008, 12:41
Награды: 3
Версия LabVIEW: 2010
Откуда: Кишинев
Контактная информация:

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение Forward »

Всем спасибо за участие :thank: , интересно и полезно было вглянуть на другие варианты после относительной "зашоренности" на своем.
mzu2006 - отличная организация :super: .
Pavel

Activity
developer
developer
Сообщения: 271
Зарегистрирован: 31 июл 2009, 08:07
Награды: 1
Версия LabVIEW: 8.5

Re: [Задача] Разбить битовый массив [до 16.02.2010]

Сообщение Pavel »

Forward писал(а):Всем спасибо за участие :thank: , интересно и полезно было вглянуть на другие варианты после относительной "зашоренности" на своем .
Я твое решение проголосовал. Мне кажется если его оптимизировать оно будет быстрее!
Ответить
  • Похожие темы
    Ответы
    Просмотры
    Последнее сообщение

Вернуться в «Конкурсы»