Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
В одной компьютерной игре игрок выставляет в линию шарики разных цветов. Когда образуется непрерывная цепочка из трех и более шариков одного цвета, она удаляется из линии. Все шарики при этом сдвигаются друг к другу, и ситуация может повториться. Напишите программу, которая по данной ситуации определяет, сколько шариков будет сейчас "уничтожено". Естественно, непрерывных цепочек из трех и более одноцветных шаров в начальный момент может быть не более одной. Входные данные Сначала вводится количество шариков в цепочке (не более 1000) и цвета шариков (от 0 до 9, каждому цвету соответствует свое целое число). Выходные данные Требуется вывести количество шариков, которое будет "уничтожено". Пример: Вход: 5 1 3 3 3 2 Выход: 3 Решение данной задачи реализованнное на С++,заходит только на 70%.Остальные или неправильные, или тайм лимит(знаю что далеко от идеала,но все же): Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. З.Ы:Знаю что решений этой задачи в интернете много,но все же интересно допилить свой код до ума.Прошу строго не судить ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 18:45 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
если что картинка - это мое условие,текст нашел в интернете (на случай если картинка не загрузиться) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 18:46 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
ванмомас намбаванвсе же интересно допилить свой код до ума Интересно - допиливай. Хотя его, как обычно, лучше будет выкинуть целиком и написать новый. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 18:55 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakovванмомас намбаванвсе же интересно допилить свой код до ума Интересно - допиливай. Хотя его, как обычно, лучше будет выкинуть целиком и написать новый. Его уже надо выкидывать. Там используется массив со всеми вытекающими. Хотя из природы самой постановки требуется что-то вроде связного би-направленного списка. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 19:11 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
mayton, а что такое би-направленный список? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 19:14 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Список ты должен был проходить. Это первый курс кодинга. 2-я или 3 лаба. Дву-направленный (bi-directional (doubly-linked)) это тоже самое но в дополнение к списку каждый элемент смотрит на обоих соседей. Справа и слева. Это позволяет двигать итератор в обратку. В STL возможно это его имплементация (я уж точно не помню): http://www.cprogramming.com/tutorial/stl/stllist.html ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 19:22 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
mayton,обычный список юзал не раз,про этот слышу впервые,надо разобраться ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 19:26 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
maytonиз природы самой постановки требуется что-то вроде связного би-направленного списка. Не требуется ни массива, ни списка. Это задача решается поточно. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 20:20 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakov, разве что рекурсивно. Список называется не бисексуальным, а двусвязным, если что, майтон ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 20:47 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Siemarglразве что рекурсивно. Назачем? В условии не сказано, что шарики схлопываются каскадно. Наоборот, сказано, что цепочка может быть только одна. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 21:07 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
ванмомас намбаванmayton, а что такое би-направленный список? Двусвязный список. Список, где каждая нода связана как со следующей, так и с предыдущей нодой. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 21:14 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
SiemarglСписок называется не бисексуальным, а двусвязным, если что, майтон ) Спасибо бро. Это ценная инфа. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 21:26 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Не надо тут рекурсий, списков и прочей бисексуальности. Один проход. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2016, 21:36 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima TНе надо тут рекурсий, списков и прочей бисексуальности. Один проход.Опиши алгоритм словами. Я сходу не вижу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 11:00 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
SiemarglDima TНе надо тут рекурсий, списков и прочей бисексуальности. Один проход.Опиши алгоритм словами. Я сходу не вижу. Сверяешь текущую с предыдущей, совпало - счетчик++ ... дальше писать или догадался? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 11:34 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima TSiemarglпропущено... Опиши алгоритм словами. Я сходу не вижу. Сверяешь текущую с предыдущей, совпало - счетчик++ ... дальше писать или догадался? Дима, понимаю твою идею но мне кажется что после удаления учёта трех единичек 111 их (по условию) надо удалить чтобы детектировать следующую цепочку 222. Пример входных данных: Код: plaintext 1. Их можно и не удалять но тебе по любому нужно где-то хранить и обновлять информацию о связности соседних шариков и сделать это через FSM КМК очень сложно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 11:41 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
mayton(по условию) Да, точно, я как-то упустил из виду "ситуация может повториться". Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 11:50 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
maytonДима, понимаю твою идею но мне кажется что после удаления учёта трех единичек 111 их (по условию) надо удалить чтобы детектировать следующую цепочку 222. 222 окружает найденную 111, т.е. уже известно где ее искать. Удалять не обязательно, задача только посчитать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 11:57 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Да, точно, я как-то упустил из виду "ситуация может повториться". а я что-то пока не упустил. Взять два указателя на строчку, и от них проверку делать в две стороны. Один проход. о_о ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:00 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima T222 окружает найденную 111, т.е. уже известно где ее искать. Удалять не обязательно, задача только посчитать. Тогда или рекурсия (и/или цикл + какая нибудь коллекция) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:02 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
CEMbВзять два указателя на строчку, и от них проверку делать в две стороны. Один проход. о_о Это как? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:03 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
По сути тут две части: 1. Найти цепочку 2. Проверить окрестности на новую цепочку. Если найдено, то п.2 повторить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:03 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima T, согласен, но это явно смахивает "на рекурсию". Или нечто очень на нее похожее. И в любом случае, это НЕ "один проход" p.s. понятно, что любой рекурсивный алгоритма можно заменить на не рекурсивный + коллекция ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:05 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Если дотошно всматриваться, то не один проход, а максимум дважды по каждой ячейке пройтись придется. Но рекурсий и списков не надо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:06 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsevp.s. понятно, что любой рекурсивный алгоритма можно заменить на не рекурсивный + коллекция Ну зачем тут рекурсия? Надо просто пойти от найденного центра в обе стороны. Циклов достаточно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:08 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima Tа максимум дважды по каждой ячейке пройтись придется откуда взялось утверждение "максимум дважды" а если: 3011102222201113 схлопнули 11 и 222 после этого можем схлопнуть 000 потом можем схлопнуть 333 Как это сделать "максимум дважды" - мне не понять. Без рекурсии и списков - как два пальца обосновать. Но за один или "максимум дважды", мне не представить ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:10 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsevа если: 3011102222201113 Недопустимое значение. Похоже ты ТЗ невнимательно прочитал ванмомас намбаванЕстественно, непрерывных цепочек из трех и более одноцветных шаров в начальный момент может быть не более одной . А у тебя их три. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:22 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Мне почему-то эта задача напомнила клеточные автоматы. Там невозможно никак спрогнозировать состояние вселенной на шаге N+2 до тех пор пока ты до конца не воспроизведешь шаг N+1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:26 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Тогда да. Беру свои слова обратно. Два прохода. Один найти цепочку, второй от цепочки в две стороны. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:26 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Leonid KudryavtsevЭто как? вырезаешь из цепочки первую тройку, 1. ставишь 2 указателя на границах по очереди ходишь от них влево-вправо, до тех пор, пока есть одинаковые. как только насчитал 3 одинаковые штуки - вырезал, перешёл к шагу 1 в конце сложил 2 строчки ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:27 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
CEMbLeonid KudryavtsevЭто как? вырезаешь из цепочки первую тройку, 1. ставишь 2 указателя на границах по очереди ходишь от них влево-вправо, до тех пор, пока есть одинаковые. как только насчитал 3 одинаковые штуки - вырезал, перешёл к шагу 1 в конце сложил 2 строчки Мне кажется в конце надо еще раз искать "первую тройку". Доказать не могу но кажется что можем случайно пропустить еще одну эпоху схлопываний. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:34 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Тред не читал @ сразу отвечал ИМХО ничего не нужно схлопывать в памяти (реаллоцтровать). 1. Выделяем массив под шарики. 2. Ищем место "схлопа" (3 шарика подряд одинакового цвета). 3. Запускаем "волны" в обе стороны со счётчиками (как от камня, брошенного в воду). Единственная заминка может быть именно этими "волнами", которые должны быть как-то синхронизированы и двигаться параллельно. Если одна "волна" "заглохла" (упёрлась в границу), то другой уже продолжать двигаться не имеет смысла, потому что на её пути никогда не встретится 3 одинаковых шарика подряд (из условий задачи по игре, не может быть в один момент времени сразу 2 и более набора шариков для схлопывания). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:38 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Краевой случай. Для 1000 элементов и количества троек ( 1000/(3+1) = 250) разделённых одним шариком нам нужно контролировать 500 волн (по две волны на тройку). Где эту информацию хранить? В отдельных структурах или в самом списке? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 12:53 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Мне до сих пор не даёт покоя, что это компьютерная игра. "В одной компьютерной игре игрок выставляет в линию шарики разных цветов. Когда образуется непрерывная цепочка из трех и более шариков одного цвета, она удаляется из линии." Вы тащите шарик в линию мышкой. То есть, как только появляется последовательность из 3-х шариков, она тут же схлопывается и тянет за собой остальные по цепочке. Не может получиться так что в один момент времени будет сразу две и более последовательности в это линии. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 13:01 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Lines, Coloris, Zuma. Тысячи их. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 13:35 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
maytonКраевой случай. Для 1000 элементов и количества троек ( 1000/(3+1) = 250) разделённых одним шариком нам нужно контролировать 500 волн (по две волны на тройку). Где эту информацию хранить? В отдельных структурах или в самом списке? Не надо хранить 500, смотри по другому: 1. находим цепочку, назначаем ее краями дырки 2. проверяем края дырки на расширяемость, если расширяется - расширяем и снова п.2. 3. возвращаем размер дырки. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 13:50 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Пора делать макет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 13:53 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima TmaytonКраевой случай. Для 1000 элементов и количества троек ( 1000/(3+1) = 250) разделённых одним шариком нам нужно контролировать 500 волн (по две волны на тройку). Где эту информацию хранить? В отдельных структурах или в самом списке? Не надо хранить 500, смотри по другому: 1. находим цепочку, назначаем ее краями дырки 2. проверяем края дырки на расширяемость, если расширяется - расширяем и снова п.2. 3. возвращаем размер дырки. Рекурсией это делается красиво. Но доказано, что любой рекурсивный алгоритм можно заменить на нерекурсивный. К тому же рекурсия в данном случае тоже линейный алгоритм. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 14:04 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
maytonПора делать макет. Тут кода 20-30 строк. Пусть ТС делает. Алгоритм подробно выше расписан. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 14:07 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima TmaytonПора делать макет. Тут кода 20-30 строк. Пусть ТС делает. Алгоритм подробно выше расписан. Ему не под силу. Он школьников по росту сортировал и неосилил тесты. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2016, 14:20 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
нафига волны? простой перебор цепочки с проверкой и подсчетом при схлопывании достаточно два шага назад. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 01:13 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Малыхин Сергей, "волна" и "перебор цепочки" это очень красивые поэтические метафоры брат. Они достойны литературного форума. Но может мы спустимся на землю хотя-бы до алгоритмического языка (АЯ) или псевдокода в лучших традициях википедии? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 01:31 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Малыхин Сергейпростой перебор цепочки с проверкой и подсчетом при схлопывании достаточно два шага назад. Согласен с этим алгоритмом. Никаких рекурсий, двух и более проходов и прочих волн. Один проход + состояние в массиве. maytonНо может мы спустимся на землю хотя-бы до алгоритмического языка (АЯ) или псевдокода в лучших традициях википедии? Скукота. Пусть ТС пишет )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 02:58 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
maytonПора делать макет.Да, пойду заведу проект в Стиме. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 06:07 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
maytonDima Tпропущено... Тут кода 20-30 строк. Пусть ТС делает. Алгоритм подробно выше расписан. Ему не под силу. Он школьников по росту сортировал и неосилил тесты. Задача про школьников работала нормально,проблема была в размере массива ,я просто недочитал условие ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 07:27 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Про волну алгоритм зачётный ,наду будет закодить ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 07:28 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
mayton, Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 10:01 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Siemargl, яж не славянофил. Мог-бы и латиницей писать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 10:35 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Пока чай заваривается набросал алгоритм, сорри что не по-русски )) Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 14:20 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Anatoly Moskovsky, давай тыщу шариков. Посмотрим как летает твой "Запорожец". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 16:50 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Anatoly Moskovsky, И эти люди не советуют рекурсию ))))) Я даже не поверил сначала, что это работает. Работает. Но эффективность неочь ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:04 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
maytonAnatoly Moskovsky, давай тыщу шариков. Посмотрим как летает твой "Запорожец". Разрешаю )) Сложность - O(n) в 0.2 сек уложится, не бойтесь )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:05 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
SiemarglAnatoly Moskovsky, И эти люди не советуют рекурсию ))))) Я даже не поверил сначала, что это работает. Работает. Но эффективность неочь Во-первых, это алгоритм, а не оптимизированная программа. Цель была показать что там происходит. Во-вторых, не верю что неочь, давайте пруфы в сравнении с другими реализациями ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:10 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Нормально все, где вы тормоза увидели? Разве что state.push_back(v), несколько раз перевыделение памяти сделает, но это не большой тормоз на 500 элементах, и можно полечить выделив место заранее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:11 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Коллеги а вы тестили вариант с двумя локальными минимумами? (У меня к сож нет компиллятора под рукой щас) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:16 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima T, Сложность O(n), но на каждый элемент 2 вызова функции. И отдельно возня с динамическим массивом (хотя его тут можно заменить обычным фиксированным стеком). Для сравнения в рекурсии - один вызов функции. Причем хотя я написал для каждого элемента - можно вызывать ее только один раз для пары если два соседних шарика отличаются. Т.е работы примерно вчетверо меньше. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:19 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
maytonКоллеги а вы тестили вариант с двумя локальными минимумами? (У меня к сож нет компиллятора под рукой щас) По идее для кода выше без разницы сколько минимумов. Может чуть допилить надо (сходу не могу сказать), а сложность так и останется: два прохода. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:21 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
У меня по перформансу нет вопросов. Просто я (теоретически) там ожидал увидеть рекурсию но не увидел. И один проход.... Вобщем возникло подорзрение что какой-то кейс недотестирован. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:22 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Siemargl, Ну вот пусть ТС и оптимизирует, там есть куда и все прямо в глаза бросается. Я еле удержался когда писал )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:24 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
maytonУ меня по перформансу нет вопросов. Просто я (теоретически) там ожидал увидеть рекурсию но не увидел. И один проход.... Вобщем возникло подорзрение что какой-то кейс недотестирован. Тут неявная рекурсия. state - это стек ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:24 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Anatoly MoskovskyТут неявная рекурсия Но при этом это один из тех немногих случаев, когда алгоритм проще реализовать именно с неявной рекурсией. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:26 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Anatoly MoskovskymaytonУ меня по перформансу нет вопросов. Просто я (теоретически) там ожидал увидеть рекурсию но не увидел. И один проход.... Вобщем возникло подорзрение что какой-то кейс недотестирован. Тут неявная рекурсия. state - это стек Я понял. А если использовать std::stack ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:27 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
maytonЯ понял. А если использовать std::stack ? А оно внутри все равно так же устроено )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:29 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
А ну ОК. Остался пустяк. Растолковать автору. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:31 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
SiemarglТ.е работы примерно вчетверо меньше. Не согласен. Рекурсия - однозначно вызов функции (что не быстро), а тут все функции оптимизатор заинлайнит. vector это по сути обычный массив, который довыделяет память при необходимости, причем не по одному элементу, а сразу кратно текущему размеру (в 1,5 раза где-то читал). В принципе тут это решаемо на берегу: Код: plaintext 1. 2. и перевыделения памяти вообще не будет во время работы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:31 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Почему "вызов функции" == "не быстро" ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:43 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Leonid KudryavtsevПочему "вызов функции" == "не быстро" ? Все регистры в стэк, код функции, восстановление обратно. Или современные компиляторы как-то по другому вызов делают? Под "не быстро" имел ввиду по сравнению с инлайном, где не надо регистры сохранять/восстанавливать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 17:50 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima TВсе регистры в стэк... Нет такого AFAIK ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 18:04 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima T, есть такой трюк. Называется хвостовая рекурсия. Механию ее работы я до конца не понимаю. Но гуры от Функциональщины говорят-де она с помощью этого "хвоста" способна сворачивать рекурсии в обычные циклы. Haskell, Scala теоретически ее поддерживают. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 18:13 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
maytonНазывается хвостовая рекурсия. Механию ее работы я до конца не понимаю. Думаю к этой теме это не имеет отношения. А механика проста. При хвостовой рекурсии, после рекурсивного вызова локальные переменные вызывающей функции уже не используются, поэтому сам вызов можно не проводить, а сымитировать прямо в текущем фрейме, путем установки новых значений аргументов и перехода в начало функции. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 18:22 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Leonid KudryavtsevDima TВсе регистры в стэк... Нет такого AFAIK Не силен в асме, кодом доказывать не буду. Пример рефакторинга собственного кода. Схематично. Было Код: plaintext 1. 2. 3. 4. 5. 6. 7. переписал в класс Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Именно так, без каких-либо доп оптимизаций. Просто скопипастил куски кода. Ну и в клиентском коде создание объекта добавил. Стало работать на 15-20% быстрее, т.к. компилятор смог инлайнить f() ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 18:27 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
поторопился, такой класс Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 18:29 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Опять поторопился :) Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. Вобщем не знаю точно за счет чего, но как написал стало работать быстрее на 15-20%. Я считаю из-за инлайна. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 18:39 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Вообще-то в данном случае под виндовсом главный тормоз будет в Код: plaintext 1. Недавно тестили. 18908145 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 18:50 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
SiemarglDima T, Сложность O(n), но на каждый элемент 2 вызова функции. И отдельно возня с динамическим массивом (хотя его тут можно заменить обычным фиксированным стеком). Для сравнения в рекурсии - один вызов функции. Причем хотя я написал для каждого элемента - можно вызывать ее только один раз для пары если два соседних шарика отличаются. Т.е работы примерно вчетверо меньше. Приврал. Проверил. Вдвое. На данных 10 3 3 2 2 1 1 1 2 2 3 3 у АМ 13 вызовов функций (не включая работу с вектором) у меня - 6 Чуть позже выложу ассемблер ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 19:28 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
SiemarglПриврал. Проверил. Вдвое. На данных 10 3 3 2 2 1 1 1 2 2 3 3 у АМ 13 вызовов функций (не включая работу с вектором) у меня - 6 у АМ 0 (ноль) вызовов функций. Вызовы компилятор уберет. Если не веришь компиляторам - у него можно просто скопипастить весь код в main(), функции там только для для читаемости кода, с рекурсией это невозможно, так что 6:0, а не 6:13. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 19:37 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Вы действительно хотите это видеть?? AM Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219. 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. 253. 254. 255. Sie Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 19:48 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
mingw 4.7.1 mingw32-g++.exe -Wall -fexceptions -fomit-frame-pointer -O2 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.03.2016, 20:02 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
SiemarglЧуть позже выложу ассемблер Для начала неплохо было бы исходник хотя бы выложить ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.03.2016, 01:30 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Anatoly MoskovskySiemarglЧуть позже выложу ассемблер Для начала неплохо было бы исходник хотя бы выложить ))) Да хотелось подавану дать время самому подумать. Думаешь уже хватит? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.03.2016, 10:21 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Anatoly MoskovskySiemarglЧуть позже выложу ассемблер Для начала неплохо было бы исходник хотя бы выложить ))) Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. Dima TSiemarglПриврал. Проверил. Вдвое. На данных 10 3 3 2 2 1 1 1 2 2 3 3 у АМ 13 вызовов функций (не включая работу с вектором) у меня - 6 у АМ 0 (ноль) вызовов функций. Вызовы компилятор уберет. Если не веришь компиляторам - у него можно просто скопипастить весь код в main(), функции там только для для читаемости кода, с рекурсией это невозможно, так что 6:0, а не 6:13. Я не верю =) ИМХО, у них от шаблонного объектного кода крыша съезжает. В простых случаях - нормально инлайнит и оптимизирует, но с сегодняшней модой на простые пятимерные шаблоны смотри сам, какой код генерится. Это типовой образец причем. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.03.2016, 22:14 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
SiemarglDima Tпропущено... у АМ 0 (ноль) вызовов функций. Вызовы компилятор уберет. Если не веришь компиляторам - у него можно просто скопипастить весь код в main(), функции там только для для читаемости кода, с рекурсией это невозможно, так что 6:0, а не 6:13. Я не верю =) ИМХО, у них от шаблонного объектного кода крыша съезжает. В простых случаях - нормально инлайнит и оптимизирует, но с сегодняшней модой на простые пятимерные шаблоны смотри сам, какой код генерится. Это типовой образец причем. ИМХУ не туда смотришь. При чем тут шаблоны? Замени vector<> на массив + немного кода и не будет шаблонов. vector<> тормознее обычного массива, не спорю. Но при необходимости его можно заменить на обычный массив. У меня так скомпилировалось MS VC 2015 Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. Как видишь match_back() и erase_back() заинлайнились. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2016, 08:58 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Вот так твой код скомпилировался Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. deflate() не инлайнится, т.к. рекурсия. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2016, 09:06 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima T, Рекурсия, какая рекурсия? Где ты видишь рекурсивный вызов в ассемблере? =) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2016, 11:30 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
тут Код: plaintext 1. 2. 3. 4. 5. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2016, 11:36 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Господа, вам не стыдно сравнивать скорость кода который читает из потока и кода который работает с уже считанным массивом? ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2016, 14:27 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Anatoly MoskovskyГоспода, вам не стыдно сравнивать скорость кода который читает из потока и кода который работает с уже считанным массивом? ))) Это не принципиально. Оба кода в итоге прочитают массив целиком. Хотя можно было бы и не дочитывать. Мы же не секундомером мерим, а количество операций обсуждаем. PS Еще код Siemargl 18954238 неправильно считает. В принципе это тоже не важно :) Код: plaintext 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2016, 14:54 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima TЭто не принципиально. Оба кода в итоге прочитают массив целиком. Хотя можно было бы и не дочитывать. Это принципиально. Потому что чтение например 1000 чисел займет несколько миллисекунд, а сам алгоритм их обработки - несколько микросекунд (что один что второй). Поэтому считать такты на вызовы функций, когда I/O на порядки медленнее - бессмысленная работа )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2016, 15:18 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Dima T, Срочный сервис пак =) Код: plaintext 1. 2. С точки зрения практической выгоды, конечно дисковое чтение гораздо дольше. Но это пример, когда рекурсивный алгоритм короче и эффективнее. Причем оба компилятора оптимизировали хвостовую рекурсию. Чтение из потока дает небольшую добавку в инструкциях (хотя хз, почему MSVC дважды сгенерил этот кусок) Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2016, 16:47 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Хотя нет, GCC рекурсию оставил. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2016, 17:04 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Написал для сравнения с учетом вышеизложенных замечаний. (без функций, шаблонов и потокового чтения) Исходник Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. в асме Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2016, 17:32 |
|
||
|
Шарики(задача по программированию)
|
|||
|---|---|---|---|
|
#18+
Немного потестил. Тоже срочный сервиспак надо :) Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. получилась тоже что и у тебя с рекурсией, только цикл вместо рекурсии. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2016, 18:48 |
|
||
|
|

start [/forum/topic.php?all=1&fid=57&tid=2018575]: |
0ms |
get settings: |
9ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
49ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
145ms |
get tp. blocked users: |
1ms |
| others: | 14ms |
| total: | 251ms |

| 0 / 0 |
