Arduino.ru

"Тёмных лошадок" вроде не наблюдается.

kolyn, я думаю, нужно использовать всю информацию что есть, а если я выложил свои идеи, то сам виноват, что  кто-нибудь ими воспользуется. Может для интереса попробуете п.5 осуществить?

Пишу с телефона:)

Итак, время вышло :)

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

Алгоритм остался прежним, времена по сравнению с вариантом из сообщения #274 уменьшились незначительно, в среднем на 5-15% . Главное достижение - код перестал вылетать на 25 ключах из набора ГОСТ :)

Не знаю, когда будут подведены итоги и каковы будут результаты, но я хочу отметить, что развлекся я классно! это было что-то :) Спасибо всем участвовавшим, сочувствующим и, конечно, организатору.

Да, время вышло, даже по Гринвичу. Ставки сделаны, ставок больше нет. :)

Кстати, в последней идеи доработать код я ошибся, мне показалось, что набор после фильтрации можно ещё прогнать через фильтрацию, отсюда и лишний ключ 8-10 из набора задания.

Перебор сочетаний я взял с этой статьи, как работает не до конца понял, но "прикрутил".

Ознакомился со структурами, раньше не использовал.

Ещё обнаружил несколько полезностей, при разработке первого варианта кода.

Вывод uint64_t в Serial:

void print_uint64_t(uint64_t num) {
  char rev[128]; 
  char *p = rev+1;

  while (num > 0) {
    *p++ = '0' + ( num % 10);
    num/= 10;
  }
  p--;
  while (p > rev) {
    Serial.print(*p--);
  }
  Serial.println();
}

Счет бинарных единиц в uint64_t:

     uint64_t v;
     v = v - ((v >> 1) & 0x5555555555555555);                         
     v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333); 
     uint8_t count = (((v + (v >> 4)) & 0x0F0F0F0F0F0F0F0F) * 0x101010101010101) >> 56;

Так вы решили в новички записаться? ;-)

А это первый конкурс на этом ресурсе? По мне, так сложновато для новичков, тем более для ардуинщиков, мимо основных тем.
Однако, очень интересно посмотреть все результаты и код ЕП.

А почему бы и нет :)  о своем отношении к конкурсу написал в #166.

На призы не претендую, но посоревноваться хочется:)  Не вижу в этом ничего стыдного :)

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

При изрядной доле везения и вовремя произошедшем переполнении millis перебор тоже может показать вполне приличный результат:))

Да и приз не копеечный. :)

Жаль участников мало было. Я слишком поздно сообщил своему коллеге, он тоже заинтересовался, но куда-то свою ардуинку задевал, он заказал новую. И брат у меня по диплому программист, но как диплом написал, больше не кодил. Так что, думаю, в следующем конкурсе будет больше участников.

Мужики, всем сапсибо!

Жизнь так повернулась, что до выходных я врядли этим займусь. Извините за задержку. Но займусь обязательно.

подождем :)

Все правильно: подсчет голосов, судебные иски, пересчет голосов... тут бы к февралю успеть...

Майдан опять же ж :-)

"Эх ты деревня"..."Большого слона едят по куску"...

И что, даже в порядке вне зачёта никто не рискнул съесть большого слона по кусочку?
Предполагаемое время 15-20 миллисекунд на 100 ключей...

У вас уже есть такой код?

Тогда он, для начала, должен решать ГОСТ-овский набор за миллисекунды. А потом должен учитывать, что ключи с размерами {1, 80, 1} тоже по условию задачи могут быть в наборе.

чем меньше ты понимаешь в предмете, тем очевидней и проще кажется задача :)

Напиши такой алгоритм - мы сравним время.

хм... походе ты не понимаешь, что задача деления графа на части не такая простая. Если граф многократно замкнут на себя - как ты его разделишь?

хотя.... может ты и прав.

Седня вечером попробую.

Так эта задача не про граф. Она про множество графов с двумя узлами и одной дугой.

если честно, я в теории графов не силен. В свое время струсил на мехмат поступать :)

Хорошо, пусть это не граф - а множество, вопрос остается прежним - как его правильно поделить на части?

Теоретически - если множество является функцией от чего-либо, то можно. Если оно случайно, как в задаче, - неможно.

Оно не случайно, оно предварительно сортированный список, в этом уверен, так как много работал с барышнями из оного )))

Это Вы часом не о специфичной работе с VIP-клиентами?

С барышнями из предварительно отсортированного списка? Можно с этого места поподробнее :-)

как-нибудь в отвлеченных? ;-)))

пРСТИТЕ...  это блядей по росту в кустах на обочине выстраивал?... Ик... сорри..

Шаббат шалом, кстати! Православные! ;)))

ua6em - попробовал... как-то не очень

Взял этот набор, граф которого представлен выше, волюнтаристки поделил его на два:

посчитал  каждый отдельно  и слил результаты. Как ни странно, минимальный набор совпал с прежними расчетами.

Итог - если мой прежний алгоритм считал его примерно за 12 мсек, то "методом слона" (назовем его так) время снизилось до 5.5 мсек. Казалось бы - успех ...

Но!!

Во-первых, почему всего в 2 раза? что так мало? я ожидал вчетверо... хлтя нет... каждая половинка считается в 4 раза быстрее, но половинок две - получаем в 2 раза, тут все верно.

Но и эти 2 раза - результат излишне оптимистичный, это время не учитывает затраты на разделение графа, поскольку в этом случае я поделил его вручную.

Более того, если взять исходный набор Евгения и посчитать "методом слона" его - выигрыша вообще нет, есть проигрыш.

Но и это все неважно по сравнению с тем, что метод иногда ошибается :) Дело в том. что разделенные графы теряют часть информации друг о друге и минимум в половинке, рассчитанной отдельно - может оказаться не тем, что был в полном наборе. Хотя я и пытался делить набор "умно", оставляя "пограничные" ребра одновременно и в левом и в правом графе - все равно этого оказалось недостаточно.

Так что пока складывается впечатление, что этот подход не позволит особо улучшить результаты. Хотя идейка интересная.

Предложите свое деление

А если к набору добавят 6-27, 15-24, 13-22, 6-18?

А если идти от максимального (в пределах разумного) количества ключей, где есть все размеры от 1 до 255, и все сочетания без повторений ключей с этими размерами и без дублей с высокой ценой, т.е. 32385 ключей. Понимаю, что столько в нанку не влезет, но в теории, как будет выглядеть граф и каково будет его решение?

нет ...в кустах это в Средней Азии СССР было... "а знания другой студентки рядом в кустах подтягивал аж профессор" :-)))
Всё прозаичней ...
PS Ты лучше коллегам подсказал бы, как "Большого слона есть по кусочку", блесни школой, а то с такими подходами как озвучивают ни какой памяти и вычислительных мощностей не хватит...

Для начала, он, видимо, сортировал их методом вставок :-)

Очевидное - если набор можно разделить на подмножества с непересекающимися размерами, например (5*6, 6*7, 7*8, 8*5) и (15*17, 17*19, 19*15). Но это уж ооочень частный случай)) 

мне кажется, в таком случае и делить не надо - набор и так поделен

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

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

к чему этот вопрос? Я все ж призываю рассматривать реальные примеры, которые мы в состоянии проверить.

Возвращаясь к алгоритму деления и его практическим результатам - я взял для примера самый большой набор ua6em. который он предложил в этой ветке - из сообщения #232:

static Spanner spanners[] = {
    {2, 3, 1}, // 2.5 x 3.2
    {3, 4, 2}, // 3.2 x 4
    {3, 5, 3}, // 3.2 x 5.5
    {4, 5, 4}, 
    {5, 6, 5}, // 5 x 5.5
    {5, 7, 6}, // 5.5 x 7
    {6, 7, 7},
    {7, 8, 8},        // за 2 миллисекунды   
      
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 9}, 
    {10, 11, 10},            
    {10, 12, 51455},  // за 77 миллисекунд  
    
    {10, 13, 11}, 
    {11, 12, 12},
    {11, 13, 13},                   
    {12, 13, 56544},
    {12, 14, 57675},  // за 1835 миллисекунд

    {13, 14, 15},        
    {13, 15, 62845},
    {13, 16, 16}, 
    {13, 17, 17},   
    {14, 15, 61714},  // за 29400 миллисекунд

    {14, 17, 70276},
    {16, 17, 76496},
    {16, 18, 81989},
    {17, 19, 82312},    
    {17, 22, 18},     //  за 102724 миллисекунд
    
    {18, 19, 82877},    
    {18, 21, 19},       
    {19, 22, 110826}, //
    {19, 24, 20},
    {21, 22, 21},     //
    {21, 24, 22},        
    {22, 24, 145560},
    {22, 27, 23},       
    {24, 27, 171570},
    {24, 30, 24}, 
    {27, 30, 25}, 
    {27, 32, 26}, 
    {30, 32, 27}, 
    {30, 34, 28},
    {30, 36, 29}, 
    {32, 34, 30},  
    {32, 36, 31},
    {34, 36, 32},
    {36, 41, 33},  
    {41, 46, 34},
    {46, 50, 35},
    {50, 55, 36}, 
    {55, 60, 37},
    {65, 70, 38}, 
    {70, 80, 39},
    {85, 90, 40},
    {95, 100, 41}, 
    {105, 110, 42},
    {115, 120, 43},
    {120, 130, 44}, 
    {135, 145, 45}, 
    {150, 155, 46}  //       
};

алгоритмом, который я использовал в конкурсе - этот набор решается за 718 мс, минимальный набор стоит 623, 71 руб. Методом деления этот же набор решается уже за 75мс - но решение немного хуже - 624.10.

То есть алгоритм дает не самый оптимум, но довольно близкий к нему ответ, в данном случае лишь менее чем на 0.1 % хуже, но в 10 раз быстрее. Не спешите сразу отметать этот результат на основании того, что это не абсолютный минимум... в данном случае это чем-то напоминает методы сжатия данных с потерями - те что используются в МП3 - расжатый звук получается немного не тот, что оригинальный, но зато его удается сжать значительно сильнее, чем LowLess кодеками

"Лучше" бы у меня был хер до колена, крылья за спиной и мульон долларофф! ;))

А по делу - в общем случае нельзя разделить множество на два поменьше. То есть изначально нужно разбить на связанные группы, а вот разделить связанную - это уже совсем не простая задача. Если связь  - однозначный путь без петель, то можно разбить по разным границам ключа и решить 4 половинные задачи - все же сильно меньше перебор. Но нужно время на поиск и локализацию связи. А тут не очевидно что это будет быстрее брутфорса. в группе из 8 ключей - полный брутфорс всего 256 вариантов.

Правильный подход - выбрать стратегию полного перебора неких групп (НО НЕ ЕДИНСТВЕННОГО ДЕЛЕНИЯ НА ДВЕ ЧАСТИ - так неправильно), а в группах - тупо брутфорсить, с ограничениями по количеству ключей. Тоже экспонента, но поменьше.

да, я ужетоже  пришел к тому. что при разбитии на 2 группы надо решать 4 половинных задачи - а это приводит к еще большим потерям времени и выигрыш от метода совсем исчезает

нафиг не надо ничего брутфорсить. В том методе, что использовал в конкурсе - я на самом деле тоже дроблю исходное множество на все меньшие и меньшие части в рекурсии. И это дает неплохие результаты - время решения больших множеств у меня получается в сотни, а то и в тыщи раз лучше брутфорса. Все что нужно моему методу - это место в памяти для рекурсии, места, которого в Уно слишком мало. Но взять, к примеру, Мегу - метод решает все представленные в ветке примеры в пределах 100мс - сравни с десятками и даже тыщами мс на брутфорсе

                              Uno 328                     Mega2560

EP                    2.53                                2.53
EP + 9-27            11.68                              11.72

GOST26               20.68                              20.70
GOST28               30.53                              30.57
GOST30               10.80                              10.79
GOST32                 --                                77.7
GOST35                 --                                81.8

Andre-100              --                                31.8

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

PS небольшим флудом  тему просто "подогревал"
PPS ту автоматику, что сделал приятелю для кораблика (возврат по GPS) оказалось использовать при определённом направлении ветра нельзя, так как все ресурсы тратились на борьбу с волной, возвращает в ручном режиме и галсами

Ахранеть! По такой логике если программа выдает неверный результат но делает это быстрее - она победила?

Вопрос интересен сам по себе. Не будьте так категоричны, метод разделения ( так как я его пока написал ) - не дает абсолютного оптимума, но он ЗАВЕДОМО дает очень близкий к минимуму результат. Я затрудняюсь сказать насколько - тут Дракуле карты в руки - но имхо ошибка не превысит цены пограничного ключа. То есть чем больше исходный набор, тем ближе результат к оптимуму.
И если вопрос стоит практический - получить ли абсолютный минимум брутфорсом за 15 минут или довольствоваться на 0.1% худшим выбором, полученным за 0.1 секунды - все не так однозначно:)

Тут необходимо определиться что чего мы хотим добиться - правильного результата  или минимального времени выполнения. Это как 2 + 2 приблизительно 4.2  - какой смысл искать такое решение?

Ну, аналогия со сжатием с потерями в данном случае не работает: алгоритм либо решает задачу (всегда), либо не решает (во всех или в некоторых случаях не находит оптимума). Очевидно, что "метод деления" задачу НЕ решает.

НО:

в основном алгоритме важным фактором является начальное приближение. Если за 10% времени от работы основного алгоритма можно найти хорошее начальное приближение, то оно сократит время работы основного алгоритма, возможно, на величину более 10%.

Т.е. имеет смысл попытаться применить эти алгоритмы последовательно.

Я всем знакомым связанным с программированием рассказал про конкурс, но слишком поздно, и что он закончиться 30 ноября. А они теперь спрашивают про результат. Памагите. )))

Женя! Продли до НГ. Люди тут переживают сильно!

... ну и не будь как некоторые... расскажи про функциональное программирование. Тут  ведь копья апголову ломают.

это где? не помню таких дискуссий здесь

просто так решать надо. это ж поиск оптимума. Перебор то все равно будет, рекурсией ли, функционалими ли. Вопрос в том, что лучше оптимизирует компилятор.  Есть мнение, что второй вариант компилятору ближе.

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

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

Андрей, ну вот правда, простите, ну припёрло, думал до пятницы расхлебаюсь ... в общем завтра или край - послезавтра приступлю к этой работе.

Форум то тематический. Очень трудно придумать задачи, годные для выполнения на МК и не требующие дополнительных модулей, блоков и т.д. И в то же время и про программную составляющую не забыть, сделав ее достаточной сложности.

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