powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Шарики(задача по программированию)
93 сообщений из 93, показаны все 4 страниц
Шарики(задача по программированию)
    #39193715
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В одной компьютерной игре игрок выставляет в линию шарики разных цветов. Когда образуется непрерывная цепочка из трех и более шариков одного цвета, она удаляется из линии. Все шарики при этом сдвигаются друг к другу, и ситуация может повториться.

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

Входные данные
Сначала вводится количество шариков в цепочке (не более 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.
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;


int main(){
       freopen("input.txt","r",stdin);
	   freopen("output.txt","w",stdout);
    
    int n=0,count=0,k=0;
    int a[1000]={0};
    cin>>n;
	   for(int i=0;i<n;i++){
           
           cin>>a[i];
       }
	   int rembFirst=0;
	   bool enterance=false;
       bool remember=true;
	   do{
           enterance=false;
           for(int i=1;i<n;i++){
               
               
               if(a[i]==a[i-1]){
                   
                   if(remember) {
                    rembFirst=i-1;
                    remember=false;
                   }
                   enterance=true;
                   count++;
                   
               }
               if(a[i]!=a[i-1] || i==(n-1)){
                   
                   if(count>=3){
                       for(int  z=rembFirst;z<n;++z){
                           a[z]=a[z+count];
                       }
                       k+=count;
                       n-=count;
                       count=1;
                       remember=true;
                       rembFirst=0;
                       break;
                   }
                   remember=true;
                   rembFirst=0;
                   count=1;
               }
               
               
           }
           
       }while(enterance);
    
    
    cout<<k;
    
    return 0;
}


З.Ы:Знаю что решений этой задачи в интернете много,но все же интересно допилить свой код до ума.Прошу строго не судить
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193717
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
если что картинка - это мое условие,текст нашел в интернете (на случай если картинка не загрузиться)
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193726
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ванмомас намбаванвсе же интересно допилить свой код до ума
Интересно - допиливай. Хотя его, как обычно, лучше будет выкинуть целиком и написать новый.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193748
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakovванмомас намбаванвсе же интересно допилить свой код до ума
Интересно - допиливай. Хотя его, как обычно, лучше будет выкинуть целиком и написать новый.

Его уже надо выкидывать. Там используется массив со всеми вытекающими.
Хотя из природы самой постановки требуется что-то вроде связного би-направленного
списка.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193753
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
а что такое би-направленный список?
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193756
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Список ты должен был проходить. Это первый курс кодинга. 2-я или 3 лаба.

Дву-направленный (bi-directional (doubly-linked)) это тоже самое но в дополнение
к списку каждый элемент смотрит на обоих соседей. Справа и слева.
Это позволяет двигать итератор в обратку.

В STL возможно это его имплементация (я уж точно не помню):

http://www.cprogramming.com/tutorial/stl/stllist.html
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193760
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,обычный список юзал не раз,про этот слышу впервые,надо разобраться
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193792
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonиз природы самой постановки требуется что-то вроде связного би-направленного
списка.
Не требуется ни массива, ни списка. Это задача решается поточно.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193805
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

разве что рекурсивно.

Список называется не бисексуальным, а двусвязным, если что, майтон )
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193827
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemarglразве что рекурсивно.
Назачем? В условии не сказано, что шарики схлопываются каскадно. Наоборот, сказано, что
цепочка может быть только одна.

Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193831
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ванмомас намбаванmayton,
а что такое би-направленный список?

Двусвязный список. Список, где каждая нода связана как со следующей, так и с предыдущей нодой.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193838
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SiemarglСписок называется не бисексуальным, а двусвязным, если что, майтон )
Спасибо бро. Это ценная инфа.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39193850
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не надо тут рекурсий, списков и прочей бисексуальности. Один проход.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194147
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TНе надо тут рекурсий, списков и прочей бисексуальности. Один проход.Опиши алгоритм словами. Я сходу не вижу.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194177
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SiemarglDima TНе надо тут рекурсий, списков и прочей бисексуальности. Один проход.Опиши алгоритм словами. Я сходу не вижу.
Сверяешь текущую с предыдущей, совпало - счетчик++ ... дальше писать или догадался?
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194184
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TSiemarglпропущено...
Опиши алгоритм словами. Я сходу не вижу.
Сверяешь текущую с предыдущей, совпало - счетчик++ ... дальше писать или догадался?
Дима, понимаю твою идею но мне кажется что после удаления учёта трех единичек 111
их (по условию) надо удалить чтобы детектировать следующую цепочку 222.

Пример входных данных:
Код: plaintext
1.
10 3 3 2 1 1 1 2 2 3 3



Их можно и не удалять но тебе по любому нужно где-то хранить
и обновлять информацию о связности соседних шариков и сделать это через FSM
КМК очень сложно.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194198
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton(по условию)
Да, точно, я как-то упустил из виду "ситуация может повториться".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194208
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДима, понимаю твою идею но мне кажется что после удаления учёта трех единичек 111
их (по условию) надо удалить чтобы детектировать следующую цепочку 222.
222 окружает найденную 111, т.е. уже известно где ее искать. Удалять не обязательно, задача только посчитать.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194209
Фотография CEMb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да, точно, я как-то упустил из виду "ситуация может повториться". а я что-то пока не упустил. Взять два указателя на строчку, и от них проверку делать в две стороны. Один проход. о_о
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194214
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T222 окружает найденную 111, т.е. уже известно где ее искать. Удалять не обязательно, задача только посчитать.
Тогда или рекурсия (и/или цикл + какая нибудь коллекция)
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194215
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
CEMbВзять два указателя на строчку, и от них проверку делать в две стороны. Один проход. о_о
Это как?
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194216
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По сути тут две части:
1. Найти цепочку
2. Проверить окрестности на новую цепочку. Если найдено, то п.2 повторить.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194219
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T, согласен, но это явно смахивает "на рекурсию". Или нечто очень на нее похожее. И в любом случае, это НЕ "один проход"

p.s. понятно, что любой рекурсивный алгоритма можно заменить на не рекурсивный + коллекция
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194222
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если дотошно всматриваться, то не один проход, а максимум дважды по каждой ячейке пройтись придется. Но рекурсий и списков не надо.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194227
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsevp.s. понятно, что любой рекурсивный алгоритма можно заменить на не рекурсивный + коллекция
Ну зачем тут рекурсия? Надо просто пойти от найденного центра в обе стороны. Циклов достаточно.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194228
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Tа максимум дважды по каждой ячейке пройтись придется
откуда взялось утверждение "максимум дважды"

а если:

3011102222201113

схлопнули 11 и 222
после этого можем схлопнуть 000
потом можем схлопнуть 333

Как это сделать "максимум дважды" - мне не понять. Без рекурсии и списков - как два пальца обосновать. Но за один или "максимум дважды", мне не представить
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194242
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsevа если:
3011102222201113
Недопустимое значение.

Похоже ты ТЗ невнимательно прочитал
ванмомас намбаванЕстественно, непрерывных цепочек из трех и более одноцветных шаров в начальный момент может быть не более одной .
А у тебя их три.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194245
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне почему-то эта задача напомнила клеточные автоматы. Там невозможно никак
спрогнозировать состояние вселенной на шаге N+2 до тех пор пока ты до конца
не воспроизведешь шаг N+1.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194246
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тогда да. Беру свои слова обратно. Два прохода.

Один найти цепочку, второй от цепочки в две стороны.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194248
Фотография CEMb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid KudryavtsevЭто как?
вырезаешь из цепочки первую тройку,
1. ставишь 2 указателя на границах
по очереди ходишь от них влево-вправо, до тех пор, пока есть одинаковые.
как только насчитал 3 одинаковые штуки - вырезал, перешёл к шагу 1
в конце сложил 2 строчки
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194258
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
CEMbLeonid KudryavtsevЭто как?
вырезаешь из цепочки первую тройку,
1. ставишь 2 указателя на границах
по очереди ходишь от них влево-вправо, до тех пор, пока есть одинаковые.
как только насчитал 3 одинаковые штуки - вырезал, перешёл к шагу 1
в конце сложил 2 строчки
Мне кажется в конце надо еще раз искать "первую тройку".
Доказать не могу но кажется что можем случайно пропустить еще
одну эпоху схлопываний.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194263
Фотография NekZ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тред не читал @ сразу отвечал

ИМХО ничего не нужно схлопывать в памяти (реаллоцтровать).
1. Выделяем массив под шарики.
2. Ищем место "схлопа" (3 шарика подряд одинакового цвета).
3. Запускаем "волны" в обе стороны со счётчиками (как от камня, брошенного в воду).

Единственная заминка может быть именно этими "волнами", которые должны быть как-то синхронизированы и двигаться параллельно. Если одна "волна" "заглохла" (упёрлась в границу), то другой уже продолжать двигаться не имеет смысла, потому что на её пути никогда не встретится 3 одинаковых шарика подряд (из условий задачи по игре, не может быть в один момент времени сразу 2 и более набора шариков для схлопывания).
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194280
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Краевой случай. Для 1000 элементов и количества троек ( 1000/(3+1) = 250) разделённых
одним шариком нам нужно контролировать 500 волн (по две волны на тройку).

Где эту информацию хранить? В отдельных структурах или в самом списке?
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194292
Фотография NekZ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне до сих пор не даёт покоя, что это компьютерная игра.
"В одной компьютерной игре игрок выставляет в линию шарики разных цветов. Когда образуется непрерывная цепочка из трех и более шариков одного цвета, она удаляется из линии."
Вы тащите шарик в линию мышкой.
То есть, как только появляется последовательность из 3-х шариков, она тут же схлопывается и тянет за собой остальные по цепочке. Не может получиться так что в один момент времени будет сразу две и более последовательности в это линии.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194350
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Lines, Coloris, Zuma. Тысячи их.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194387
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonКраевой случай. Для 1000 элементов и количества троек ( 1000/(3+1) = 250) разделённых
одним шариком нам нужно контролировать 500 волн (по две волны на тройку).

Где эту информацию хранить? В отдельных структурах или в самом списке?
Не надо хранить 500, смотри по другому:
1. находим цепочку, назначаем ее краями дырки
2. проверяем края дырки на расширяемость, если расширяется - расширяем и снова п.2.
3. возвращаем размер дырки.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194393
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пора делать макет.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194410
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TmaytonКраевой случай. Для 1000 элементов и количества троек ( 1000/(3+1) = 250) разделённых
одним шариком нам нужно контролировать 500 волн (по две волны на тройку).

Где эту информацию хранить? В отдельных структурах или в самом списке?
Не надо хранить 500, смотри по другому:
1. находим цепочку, назначаем ее краями дырки
2. проверяем края дырки на расширяемость, если расширяется - расширяем и снова п.2.
3. возвращаем размер дырки.
Рекурсией это делается красиво. Но доказано, что любой рекурсивный алгоритм можно заменить на нерекурсивный.
К тому же рекурсия в данном случае тоже линейный алгоритм.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194412
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПора делать макет.
Тут кода 20-30 строк. Пусть ТС делает. Алгоритм подробно выше расписан.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194429
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TmaytonПора делать макет.
Тут кода 20-30 строк. Пусть ТС делает. Алгоритм подробно выше расписан.
Ему не под силу. Он школьников по росту сортировал и неосилил тесты.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194976
Фотография Малыхин Сергей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
нафига волны?
простой перебор цепочки с проверкой и подсчетом при схлопывании достаточно два шага назад.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194984
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Малыхин Сергей, "волна" и "перебор цепочки" это очень красивые поэтические метафоры брат.
Они достойны литературного форума.

Но может мы спустимся на землю хотя-бы до алгоритмического языка (АЯ) или псевдокода
в лучших традициях википедии?
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39194994
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Малыхин Сергейпростой перебор цепочки с проверкой и подсчетом при схлопывании достаточно два шага назад.
Согласен с этим алгоритмом. Никаких рекурсий, двух и более проходов и прочих волн.
Один проход + состояние в массиве.

maytonНо может мы спустимся на землю хотя-бы до алгоритмического языка (АЯ) или псевдокода
в лучших традициях википедии?
Скукота. Пусть ТС пишет ))
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195009
Фотография CEMb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПора делать макет.Да, пойду заведу проект в Стиме.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195026
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonDima Tпропущено...

Тут кода 20-30 строк. Пусть ТС делает. Алгоритм подробно выше расписан.
Ему не под силу. Он школьников по росту сортировал и неосилил тесты.
Задача про школьников работала нормально,проблема была в размере массива ,я просто недочитал условие
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195027
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Про волну алгоритм зачётный ,наду будет закодить
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195102
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
Глобальный счетчик

ДляВсех элемент Из массив Схлопнуть(элемент, элемент)
 Печатает счетчик
Конец

Процедура Схлопнуть(лев_край, прав_край)
  нов_лев_край = лев_край
  Пока нов_лев_край >0 и массив[--нов_лев_край] = массив[лев_край]
  //аналогично прав_край
  удалено = нов_лев_край - лев_край + нов_прав_край - прав_край
  если удалено >= 3 
     счетчик += удалено 
     Схлопнуть(нов_лев_край, нов_прав_край)
Конец
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195128
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemargl, яж не славянофил. Мог-бы и латиницей писать.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195404
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пока чай заваривается набросал алгоритм, сорри что не по-русски ))

Код: 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.
bool match_back(std::vector<int>& state, int v)
{
    return state.size() >= 2
            && state[state.size() - 1] == v
            && state[state.size() - 2] == v;
}

int erase_back(std::vector<int>& state, int v)
{
    int erased = 0;
    while (state.size() > 0 && state[state.size() - 1] == v) {
        state.pop_back();
        erased++;
    }
    return erased;
}


int main()
{
    //std::istringstream is ("5 1 3 3 3 2");
    std::istringstream is ("10 3 3 2 1 1 1 2 2 3 3");
    int erased = 0;
    std::vector<int> state;
    int erase_v = -1;
    int v;
    while (is >> v) {
        if (erase_v == v) {
            erased++;
        }
        else if (match_back(state, v)) {
            erased += erase_back(state, v);
            erase_v = v;
            erased++;
        }
        else {
            erase_v = -1;
            state.push_back(v);
        }
    }
    cout << erased << endl;
    return 0;
}
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195583
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky, давай тыщу шариков. Посмотрим как летает твой "Запорожец".
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195593
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky,

И эти люди не советуют рекурсию )))))

Я даже не поверил сначала, что это работает.

Работает. Но эффективность неочь
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195594
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonAnatoly Moskovsky, давай тыщу шариков. Посмотрим как летает твой "Запорожец".
Разрешаю ))
Сложность - O(n)
в 0.2 сек уложится, не бойтесь ))
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195600
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SiemarglAnatoly Moskovsky,

И эти люди не советуют рекурсию )))))

Я даже не поверил сначала, что это работает.

Работает. Но эффективность неочь
Во-первых, это алгоритм, а не оптимизированная программа. Цель была показать что там происходит.
Во-вторых, не верю что неочь, давайте пруфы в сравнении с другими реализациями )))
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195602
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нормально все, где вы тормоза увидели? Разве что state.push_back(v), несколько раз перевыделение памяти сделает, но это не большой тормоз на 500 элементах, и можно полечить выделив место заранее.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195607
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Коллеги а вы тестили вариант с двумя локальными минимумами?

(У меня к сож нет компиллятора под рукой щас)
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195610
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

Сложность O(n), но на каждый элемент 2 вызова функции.
И отдельно возня с динамическим массивом (хотя его тут можно заменить обычным фиксированным стеком).

Для сравнения в рекурсии - один вызов функции.
Причем хотя я написал для каждого элемента - можно вызывать ее только один раз для пары если два соседних шарика отличаются.
Т.е работы примерно вчетверо меньше.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195614
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonКоллеги а вы тестили вариант с двумя локальными минимумами?

(У меня к сож нет компиллятора под рукой щас)
По идее для кода выше без разницы сколько минимумов. Может чуть допилить надо (сходу не могу сказать), а сложность так и останется: два прохода.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195616
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
У меня по перформансу нет вопросов. Просто я (теоретически) там ожидал увидеть
рекурсию но не увидел. И один проход.... Вобщем возникло подорзрение что
какой-то кейс недотестирован.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195619
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemargl,

Ну вот пусть ТС и оптимизирует, там есть куда и все прямо в глаза бросается. Я еле удержался когда писал ))
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195622
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonУ меня по перформансу нет вопросов. Просто я (теоретически) там ожидал увидеть
рекурсию но не увидел. И один проход.... Вобщем возникло подорзрение что
какой-то кейс недотестирован.
Тут неявная рекурсия. state - это стек
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195623
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyТут неявная рекурсия
Но при этом это один из тех немногих случаев, когда алгоритм проще реализовать именно с неявной рекурсией.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195625
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskymaytonУ меня по перформансу нет вопросов. Просто я (теоретически) там ожидал увидеть
рекурсию но не увидел. И один проход.... Вобщем возникло подорзрение что
какой-то кейс недотестирован.
Тут неявная рекурсия. state - это стек
Я понял. А если использовать std::stack ?
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195631
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЯ понял. А если использовать std::stack ?
А оно внутри все равно так же устроено ))
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195632
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А ну ОК. Остался пустяк. Растолковать автору.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195633
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SiemarglТ.е работы примерно вчетверо меньше.
Не согласен. Рекурсия - однозначно вызов функции (что не быстро), а тут все функции оптимизатор заинлайнит.

vector это по сути обычный массив, который довыделяет память при необходимости, причем не по одному элементу, а сразу кратно текущему размеру (в 1,5 раза где-то читал). В принципе тут это решаемо на берегу:
Код: plaintext
1.
2.
std::vector<int> state;
state.reserve(1000);


и перевыделения памяти вообще не будет во время работы.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195641
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Почему "вызов функции" == "не быстро" ?
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195649
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid KudryavtsevПочему "вызов функции" == "не быстро" ?
Все регистры в стэк, код функции, восстановление обратно. Или современные компиляторы как-то по другому вызов делают?

Под "не быстро" имел ввиду по сравнению с инлайном, где не надо регистры сохранять/восстанавливать.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195657
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TВсе регистры в стэк...
Нет такого AFAIK
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195665
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T, есть такой трюк. Называется хвостовая рекурсия. Механию ее работы я до конца не
понимаю. Но гуры от Функциональщины говорят-де она с помощью этого "хвоста"
способна сворачивать рекурсии в обычные циклы.

Haskell, Scala теоретически ее поддерживают.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195673
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНазывается хвостовая рекурсия. Механию ее работы я до конца не
понимаю.
Думаю к этой теме это не имеет отношения.

А механика проста. При хвостовой рекурсии, после рекурсивного вызова локальные переменные вызывающей функции уже не используются, поэтому сам вызов можно не проводить, а сымитировать прямо в текущем фрейме, путем установки новых значений аргументов и перехода в начало функции.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195676
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid KudryavtsevDima TВсе регистры в стэк...
Нет такого AFAIK
Не силен в асме, кодом доказывать не буду. Пример рефакторинга собственного кода. Схематично.
Было
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
int f(value) {
  static vector<> cache;
  if(нет в кэше) {
     дозаполнение кэша с рекурсивным вызовом f()
  }
   return из кэша;
}


переписал в класс
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
class {
  static vector<> cache;

  void cache_fill() {
     дозаполнение кэша с вызовом f()
  }

  int f(value) {
   return из кэша;
  }
}


Именно так, без каких-либо доп оптимизаций. Просто скопипастил куски кода. Ну и в клиентском коде создание объекта добавил. Стало работать на 15-20% быстрее, т.к. компилятор смог инлайнить f()
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195679
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
поторопился, такой класс
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
class {
  static vector<> cache;

  void cache_fill() {
     дозаполнение кэша с вызовом f()
  }

  int f(value) {
   if(нет в кэше) cache_fill();
   return из кэша;
  }
}
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195691
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Опять поторопился :)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
class {
  static vector<> cache;

  void cache_fill() {
     дозаполнение кэша с рекурсивным вызовом cache_fill()
  }

  int f(value) {
   if(нет в кэше) cache_fill();
   return из кэша;
  }
}



Вобщем не знаю точно за счет чего, но как написал стало работать быстрее на 15-20%. Я считаю из-за инлайна.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195706
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вообще-то в данном случае под виндовсом главный тормоз будет в
Код: plaintext
1.
while (is >> v) {


Недавно тестили. 18908145
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195750
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SiemarglDima T,

Сложность O(n), но на каждый элемент 2 вызова функции.
И отдельно возня с динамическим массивом (хотя его тут можно заменить обычным фиксированным стеком).

Для сравнения в рекурсии - один вызов функции.
Причем хотя я написал для каждого элемента - можно вызывать ее только один раз для пары если два соседних шарика отличаются.
Т.е работы примерно вчетверо меньше.
Приврал. Проверил. Вдвое.
На данных 10 3 3 2 2 1 1 1 2 2 3 3
у АМ 13 вызовов функций (не включая работу с вектором)
у меня - 6

Чуть позже выложу ассемблер
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195759
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SiemarglПриврал. Проверил. Вдвое.
На данных 10 3 3 2 2 1 1 1 2 2 3 3
у АМ 13 вызовов функций (не включая работу с вектором)
у меня - 6
у АМ 0 (ноль) вызовов функций. Вызовы компилятор уберет. Если не веришь компиляторам - у него можно просто скопипастить весь код в main(), функции там только для для читаемости кода, с рекурсией это невозможно, так что 6:0, а не 6:13.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195770
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вы действительно хотите это видеть??
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.
0000002c <__Z10match_backRSt6vectorIiSaIiEEi>:
  2c:	53                   	push   ebx
  2d:	83 ec 18             	sub    esp,0x18
  30:	8b 5c 24 20          	mov    ebx,DWORD PTR [esp+0x20]
  34:	c7 44 24 08 01 00 00 	mov    DWORD PTR [esp+0x8],0x1
  3b:	00 
  3c:	c7 44 24 04 00 00 00 	mov    DWORD PTR [esp+0x4],0x0
  43:	00 
  44:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
  4b:	e8 00 00 00 00       	call   50 <__Z10match_backRSt6vectorIiSaIiEEi+0x24>
  50:	8b 13                	mov    edx,DWORD PTR [ebx]
  52:	8b 43 04             	mov    eax,DWORD PTR [ebx+0x4]
  55:	29 d0                	sub    eax,edx
  57:	c1 f8 02             	sar    eax,0x2
  5a:	83 f8 01             	cmp    eax,0x1
  5d:	76 0a                	jbe    69 <__Z10match_backRSt6vectorIiSaIiEEi+0x3d>
  5f:	8b 4c 82 fc          	mov    ecx,DWORD PTR [edx+eax*4-0x4]
  63:	3b 4c 24 24          	cmp    ecx,DWORD PTR [esp+0x24]
  67:	74 07                	je     70 <__Z10match_backRSt6vectorIiSaIiEEi+0x44>
  69:	31 c0                	xor    eax,eax
  6b:	83 c4 18             	add    esp,0x18
  6e:	5b                   	pop    ebx
  6f:	c3                   	ret    
  70:	3b 4c 82 f8          	cmp    ecx,DWORD PTR [edx+eax*4-0x8]
  74:	0f 94 c0             	sete   al
  77:	83 c4 18             	add    esp,0x18
  7a:	5b                   	pop    ebx
  7b:	c3                   	ret    

0000007c <__Z10erase_backRSt6vectorIiSaIiEEi>:
  7c:	57                   	push   edi
  7d:	56                   	push   esi
  7e:	53                   	push   ebx
  7f:	83 ec 10             	sub    esp,0x10
  82:	8b 5c 24 20          	mov    ebx,DWORD PTR [esp+0x20]
  86:	c7 44 24 08 01 00 00 	mov    DWORD PTR [esp+0x8],0x1
  8d:	00 
  8e:	c7 44 24 04 00 00 00 	mov    DWORD PTR [esp+0x4],0x0
  95:	00 
  96:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
  9d:	e8 00 00 00 00       	call   a2 <__Z10erase_backRSt6vectorIiSaIiEEi+0x26>
  a2:	8b 0b                	mov    ecx,DWORD PTR [ebx]
  a4:	8b 53 04             	mov    edx,DWORD PTR [ebx+0x4]
  a7:	89 d0                	mov    eax,edx
  a9:	29 c8                	sub    eax,ecx
  ab:	c1 f8 02             	sar    eax,0x2
  ae:	74 30                	je     e0 <__Z10erase_backRSt6vectorIiSaIiEEi+0x64>
  b0:	8b 7c 81 fc          	mov    edi,DWORD PTR [ecx+eax*4-0x4]
  b4:	31 c0                	xor    eax,eax
  b6:	3b 7c 24 24          	cmp    edi,DWORD PTR [esp+0x24]
  ba:	75 13                	jne    cf <__Z10erase_backRSt6vectorIiSaIiEEi+0x53>
  bc:	83 ea 04             	sub    edx,0x4
  bf:	40                   	inc    eax
  c0:	89 d6                	mov    esi,edx
  c2:	29 ce                	sub    esi,ecx
  c4:	c1 fe 02             	sar    esi,0x2
  c7:	75 0f                	jne    d8 <__Z10erase_backRSt6vectorIiSaIiEEi+0x5c>
  c9:	8d 76 00             	lea    esi,[esi+0x0]
  cc:	89 53 04             	mov    DWORD PTR [ebx+0x4],edx
  cf:	83 c4 10             	add    esp,0x10
  d2:	5b                   	pop    ebx
  d3:	5e                   	pop    esi
  d4:	5f                   	pop    edi
  d5:	c3                   	ret    
  d6:	66 90                	xchg   ax,ax
  d8:	39 7c b1 fc          	cmp    DWORD PTR [ecx+esi*4-0x4],edi
  dc:	75 ee                	jne    cc <__Z10erase_backRSt6vectorIiSaIiEEi+0x50>
  de:	eb dc                	jmp    bc <__Z10erase_backRSt6vectorIiSaIiEEi+0x40>
  e0:	31 c0                	xor    eax,eax
  e2:	83 c4 10             	add    esp,0x10
  e5:	5b                   	pop    ebx
  e6:	5e                   	pop    esi
  e7:	5f                   	pop    edi
  e8:	c3                   	ret    


00000000 <_main>:
   0:	8d 4c 24 04          	lea    ecx,[esp+0x4]
   4:	83 e4 f0             	and    esp,0xfffffff0
   7:	ff 71 fc             	push   DWORD PTR [ecx-0x4]
   a:	55                   	push   ebp
   b:	89 e5                	mov    ebp,esp
   d:	51                   	push   ecx
   e:	81 ec 24 01 00 00    	sub    esp,0x124
  14:	c7 85 0c ff ff ff 00 	mov    DWORD PTR [ebp-0xf4],0x0
  1b:	00 00 00 
  1e:	c7 85 10 ff ff ff 00 	mov    DWORD PTR [ebp-0xf0],0x0
  25:	00 00 00 
  28:	8d 45 f8             	lea    eax,[ebp-0x8]
  2b:	89 85 14 ff ff ff    	mov    DWORD PTR [ebp-0xec],eax
  31:	c7 85 18 ff ff ff 4c 	mov    DWORD PTR [ebp-0xe8],0x24c
  38:	02 00 00 
  3b:	89 a5 1c ff ff ff    	mov    DWORD PTR [ebp-0xe4],esp
  41:	8d 95 f4 fe ff ff    	lea    edx,[ebp-0x10c]
  47:	89 14 24             	mov    DWORD PTR [esp],edx
  4a:	e8 00 00 00 00       	call   4f <_main+0x4f>
  4f:	e8 00 00 00 00       	call   54 <_main+0x54>
  54:	8d 85 2b ff ff ff    	lea    eax,[ebp-0xd5]
  5a:	89 44 24 04          	mov    DWORD PTR [esp+0x4],eax
  5e:	c7 04 24 02 00 00 00 	mov    DWORD PTR [esp],0x2
  65:	c7 85 f8 fe ff ff ff 	mov    DWORD PTR [ebp-0x108],0xffffffff
  6c:	ff ff ff 
  6f:	8d 8d 2c ff ff ff    	lea    ecx,[ebp-0xd4]
  75:	e8 00 00 00 00       	call   7a <_main+0x7a>
  7a:	83 ec 08             	sub    esp,0x8
  7d:	c7 44 24 04 08 00 00 	mov    DWORD PTR [esp+0x4],0x8
  84:	00 
  85:	8d 85 2c ff ff ff    	lea    eax,[ebp-0xd4]
  8b:	89 04 24             	mov    DWORD PTR [esp],eax
  8e:	c7 85 f8 fe ff ff 01 	mov    DWORD PTR [ebp-0x108],0x1
  95:	00 00 00 
  98:	8d 8d 40 ff ff ff    	lea    ecx,[ebp-0xc0]
  9e:	e8 00 00 00 00       	call   a3 <_main+0xa3>
  a3:	83 ec 08             	sub    esp,0x8
  a6:	8d 8d 2c ff ff ff    	lea    ecx,[ebp-0xd4]
  ac:	e8 00 00 00 00       	call   b1 <_main+0xb1>
  b1:	c7 85 34 ff ff ff 00 	mov    DWORD PTR [ebp-0xcc],0x0
  b8:	00 00 00 
  bb:	c7 85 38 ff ff ff 00 	mov    DWORD PTR [ebp-0xc8],0x0
  c2:	00 00 00 
  c5:	c7 85 3c ff ff ff 00 	mov    DWORD PTR [ebp-0xc4],0x0
  cc:	00 00 00 
  cf:	c7 85 ec fe ff ff ff 	mov    DWORD PTR [ebp-0x114],0xffffffff
  d6:	ff ff ff 
  d9:	c7 85 f0 fe ff ff 00 	mov    DWORD PTR [ebp-0x110],0x0
  e0:	00 00 00 
  e3:	90                   	nop
  e4:	8d 85 30 ff ff ff    	lea    eax,[ebp-0xd0]
  ea:	89 04 24             	mov    DWORD PTR [esp],eax
  ed:	c7 85 f8 fe ff ff 02 	mov    DWORD PTR [ebp-0x108],0x2
  f4:	00 00 00 
  f7:	8d 8d 40 ff ff ff    	lea    ecx,[ebp-0xc0]
  fd:	e8 00 00 00 00       	call   102 <_main+0x102>
 102:	51                   	push   ecx
 103:	8b 10                	mov    edx,DWORD PTR [eax]
 105:	8b 52 f4             	mov    edx,DWORD PTR [edx-0xc]
 108:	f6 44 10 14 05       	test   BYTE PTR [eax+edx*1+0x14],0x5
 10d:	74 5d                	je     16c <_main+0x16c>
 10f:	8b 95 f0 fe ff ff    	mov    edx,DWORD PTR [ebp-0x110]
 115:	89 14 24             	mov    DWORD PTR [esp],edx
 118:	b9 00 00 00 00       	mov    ecx,0x0
 11d:	e8 00 00 00 00       	call   122 <_main+0x122>
 122:	52                   	push   edx
 123:	89 04 24             	mov    DWORD PTR [esp],eax
 126:	e8 00 00 00 00       	call   12b <_main+0x12b>
 12b:	8b 85 34 ff ff ff    	mov    eax,DWORD PTR [ebp-0xcc]
 131:	85 c0                	test   eax,eax
 133:	74 08                	je     13d <_main+0x13d>
 135:	89 04 24             	mov    DWORD PTR [esp],eax
 138:	e8 00 00 00 00       	call   13d <_main+0x13d>
 13d:	c7 85 f8 fe ff ff ff 	mov    DWORD PTR [ebp-0x108],0xffffffff
 144:	ff ff ff 
 147:	8d 8d 40 ff ff ff    	lea    ecx,[ebp-0xc0]
 14d:	e8 00 00 00 00       	call   152 <_main+0x152>
 152:	8d 95 f4 fe ff ff    	lea    edx,[ebp-0x10c]
 158:	89 14 24             	mov    DWORD PTR [esp],edx
 15b:	e8 00 00 00 00       	call   160 <_main+0x160>
 160:	31 c0                	xor    eax,eax
 162:	8b 4d fc             	mov    ecx,DWORD PTR [ebp-0x4]
 165:	c9                   	leave  
 166:	8d 61 fc             	lea    esp,[ecx-0x4]
 169:	c3                   	ret    
 16a:	66 90                	xchg   ax,ax
 16c:	8b 85 30 ff ff ff    	mov    eax,DWORD PTR [ebp-0xd0]
 172:	39 85 ec fe ff ff    	cmp    DWORD PTR [ebp-0x114],eax
 178:	75 0e                	jne    188 <_main+0x188>
 17a:	ff 85 f0 fe ff ff    	inc    DWORD PTR [ebp-0x110]
 180:	e9 5f ff ff ff       	jmp    e4 <_main+0xe4>
 185:	8d 76 00             	lea    esi,[esi+0x0]
 188:	89 44 24 04          	mov    DWORD PTR [esp+0x4],eax
 18c:	8d 95 34 ff ff ff    	lea    edx,[ebp-0xcc]
 192:	89 14 24             	mov    DWORD PTR [esp],edx
 195:	c7 85 f8 fe ff ff 02 	mov    DWORD PTR [ebp-0x108],0x2
 19c:	00 00 00 
 19f:	e8 2c 00 00 00       	call   1d0 <_main+0x1d0>
 1a4:	84 c0                	test   al,al
 1a6:	74 3c                	je     1e4 <_main+0x1e4>
 1a8:	8b 85 30 ff ff ff    	mov    eax,DWORD PTR [ebp-0xd0]
 1ae:	89 44 24 04          	mov    DWORD PTR [esp+0x4],eax
 1b2:	8d 85 34 ff ff ff    	lea    eax,[ebp-0xcc]
 1b8:	89 04 24             	mov    DWORD PTR [esp],eax
 1bb:	e8 7c 00 00 00       	call   23c <_main+0x23c>
 1c0:	8b 95 30 ff ff ff    	mov    edx,DWORD PTR [ebp-0xd0]
 1c6:	89 95 ec fe ff ff    	mov    DWORD PTR [ebp-0x114],edx
 1cc:	8b 95 f0 fe ff ff    	mov    edx,DWORD PTR [ebp-0x110]
 1d2:	8d 54 02 01          	lea    edx,[edx+eax*1+0x1]
 1d6:	89 95 f0 fe ff ff    	mov    DWORD PTR [ebp-0x110],edx
 1dc:	e9 03 ff ff ff       	jmp    e4 <_main+0xe4>
 1e1:	8d 76 00             	lea    esi,[esi+0x0]
 1e4:	8b 85 38 ff ff ff    	mov    eax,DWORD PTR [ebp-0xc8]
 1ea:	3b 85 3c ff ff ff    	cmp    eax,DWORD PTR [ebp-0xc4]
 1f0:	74 26                	je     218 <_main+0x218>
 1f2:	85 c0                	test   eax,eax
 1f4:	74 08                	je     1fe <_main+0x1fe>
 1f6:	8b 95 30 ff ff ff    	mov    edx,DWORD PTR [ebp-0xd0]
 1fc:	89 10                	mov    DWORD PTR [eax],edx
 1fe:	83 c0 04             	add    eax,0x4
 201:	89 85 38 ff ff ff    	mov    DWORD PTR [ebp-0xc8],eax
 207:	c7 85 ec fe ff ff ff 	mov    DWORD PTR [ebp-0x114],0xffffffff
 20e:	ff ff ff 
 211:	e9 ce fe ff ff       	jmp    e4 <_main+0xe4>
 216:	66 90                	xchg   ax,ax
 218:	8d 95 30 ff ff ff    	lea    edx,[ebp-0xd0]
 21e:	89 54 24 04          	mov    DWORD PTR [esp+0x4],edx
 222:	89 04 24             	mov    DWORD PTR [esp],eax
 225:	c7 85 f8 fe ff ff 02 	mov    DWORD PTR [ebp-0x108],0x2
 22c:	00 00 00 
 22f:	8d 8d 34 ff ff ff    	lea    ecx,[ebp-0xcc]
 235:	e8 00 00 00 00       	call   23a <_main+0x23a>
 23a:	83 ec 08             	sub    esp,0x8
 23d:	c7 85 ec fe ff ff ff 	mov    DWORD PTR [ebp-0x114],0xffffffff
 244:	ff ff ff 
 247:	e9 98 fe ff ff       	jmp    e4 <_main+0xe4>
 24c:	83 c5 08             	add    ebp,0x8
 24f:	8b 85 fc fe ff ff    	mov    eax,DWORD PTR [ebp-0x104]
 255:	89 85 f0 fe ff ff    	mov    DWORD PTR [ebp-0x110],eax
 25b:	8b 85 f8 fe ff ff    	mov    eax,DWORD PTR [ebp-0x108]
 261:	85 c0                	test   eax,eax
 263:	74 05                	je     26a <_main+0x26a>
 265:	48                   	dec    eax
 266:	74 25                	je     28d <_main+0x28d>
 268:	0f 0b                	ud2    
 26a:	8d 8d 2c ff ff ff    	lea    ecx,[ebp-0xd4]
 270:	e8 00 00 00 00       	call   275 <_main+0x275>
 275:	8b 95 f0 fe ff ff    	mov    edx,DWORD PTR [ebp-0x110]
 27b:	89 14 24             	mov    DWORD PTR [esp],edx
 27e:	c7 85 f8 fe ff ff ff 	mov    DWORD PTR [ebp-0x108],0xffffffff
 285:	ff ff ff 
 288:	e8 00 00 00 00       	call   28d <_main+0x28d>
 28d:	8b 85 34 ff ff ff    	mov    eax,DWORD PTR [ebp-0xcc]
 293:	85 c0                	test   eax,eax
 295:	74 08                	je     29f <_main+0x29f>
 297:	89 04 24             	mov    DWORD PTR [esp],eax
 29a:	e8 00 00 00 00       	call   29f <_main+0x29f>
 29f:	c7 85 f8 fe ff ff 00 	mov    DWORD PTR [ebp-0x108],0x0
 2a6:	00 00 00 
 2a9:	8d 8d 40 ff ff ff    	lea    ecx,[ebp-0xc0]
 2af:	e8 00 00 00 00       	call   2b4 <_main+0x2b4>
 2b4:	8b 85 f0 fe ff ff    	mov    eax,DWORD PTR [ebp-0x110]
 2ba:	89 04 24             	mov    DWORD PTR [esp],eax
 2bd:	c7 85 f8 fe ff ff ff 	mov    DWORD PTR [ebp-0x108],0xffffffff
 2c4:	ff ff ff 
 2c7:	e8 00 00 00 00       	call   2cc <__GLOBAL__sub_I__Z10match_backRSt6vectorIiSaIiEEi>

000002cc <__GLOBAL__sub_I__Z10match_backRSt6vectorIiSaIiEEi>:
 2cc:	83 ec 1c             	sub    esp,0x1c
 2cf:	b9 08 00 00 00       	mov    ecx,0x8
 2d4:	e8 00 00 00 00       	call   2d9 <__GLOBAL__sub_I__Z10match_backRSt6vectorIiSaIiEEi+0xd>
 2d9:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
 2e0:	e8 00 00 00 00       	call   2e5 <__GLOBAL__sub_I__Z10match_backRSt6vectorIiSaIiEEi+0x19>
 2e5:	83 c4 1c             	add    esp,0x1c
 2e8:	c3                   	ret    
 2e9:	90                   	nop
 2ea:	90                   	nop
 2eb:	90                   	nop



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.
000000ec <__Z7deflateii>:
  ec:	56                   	push   esi
  ed:	53                   	push   ebx
  ee:	83 ec 14             	sub    esp,0x14
  f1:	8b 5c 24 20          	mov    ebx,DWORD PTR [esp+0x20]
  f5:	8b 74 24 24          	mov    esi,DWORD PTR [esp+0x24]
  f9:	8d 76 00             	lea    esi,[esi+0x0]
  fc:	c7 44 24 08 01 00 00 	mov    DWORD PTR [esp+0x8],0x1
 103:	00 
 104:	c7 44 24 04 00 00 00 	mov    DWORD PTR [esp+0x4],0x0
 10b:	00 
 10c:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
 113:	e8 00 00 00 00       	call   118 <__Z7deflateii+0x2c>
 118:	85 db                	test   ebx,ebx
 11a:	7e 64                	jle    180 <__Z7deflateii+0x94>
 11c:	8d 4b ff             	lea    ecx,[ebx-0x1]
 11f:	8b 04 8d 00 00 00 00 	mov    eax,DWORD PTR [ecx*4+0x0]
 126:	3b 04 9d 00 00 00 00 	cmp    eax,DWORD PTR [ebx*4+0x0]
 12d:	74 35                	je     164 <__Z7deflateii+0x78>
 12f:	bb 01 00 00 00       	mov    ebx,0x1
 134:	89 f0                	mov    eax,esi
 136:	83 f8 0b             	cmp    eax,0xb
 139:	77 11                	ja     14c <__Z7deflateii+0x60>
 13b:	40                   	inc    eax
 13c:	8b 14 b5 00 00 00 00 	mov    edx,DWORD PTR [esi*4+0x0]
 143:	39 14 85 00 00 00 00 	cmp    DWORD PTR [eax*4+0x0],edx
 14a:	74 ea                	je     136 <__Z7deflateii+0x4a>
 14c:	8d 14 03             	lea    edx,[ebx+eax*1]
 14f:	29 f2                	sub    edx,esi
 151:	83 fa 02             	cmp    edx,0x2
 154:	7e 22                	jle    178 <__Z7deflateii+0x8c>
 156:	01 15 04 00 00 00    	add    DWORD PTR ds:0x4,edx
 15c:	89 cb                	mov    ebx,ecx
 15e:	89 c6                	mov    esi,eax
 160:	eb 9a                	jmp    fc <__Z7deflateii+0x10>
 162:	66 90                	xchg   ax,ax
 164:	85 c9                	test   ecx,ecx
 166:	74 cc                	je     134 <__Z7deflateii+0x48>
 168:	49                   	dec    ecx
 169:	39 04 8d 00 00 00 00 	cmp    DWORD PTR [ecx*4+0x0],eax
 170:	74 f2                	je     164 <__Z7deflateii+0x78>
 172:	29 cb                	sub    ebx,ecx
 174:	eb be                	jmp    134 <__Z7deflateii+0x48>
 176:	66 90                	xchg   ax,ax
 178:	83 c4 14             	add    esp,0x14
 17b:	5b                   	pop    ebx
 17c:	5e                   	pop    esi
 17d:	c3                   	ret    
 17e:	66 90                	xchg   ax,ax
 180:	89 d9                	mov    ecx,ebx
 182:	31 db                	xor    ebx,ebx
 184:	eb ae                	jmp    134 <__Z7deflateii+0x48>
 186:	66 90                	xchg   ax,ax

00000188 <__Z5main2v>:
 188:	56                   	push   esi
 189:	53                   	push   ebx
 18a:	83 ec 14             	sub    esp,0x14
 18d:	31 c0                	xor    eax,eax
 18f:	83 f8 0a             	cmp    eax,0xa
 192:	77 1a                	ja     1ae <__Z5main2v+0x26>
 194:	8d 50 01             	lea    edx,[eax+0x1]
 197:	8b 0c 95 00 00 00 00 	mov    ecx,DWORD PTR [edx*4+0x0]
 19e:	39 0c 85 00 00 00 00 	cmp    DWORD PTR [eax*4+0x0],ecx
 1a5:	74 51                	je     1f8 <__Z5main2v+0x70>
 1a7:	89 d0                	mov    eax,edx
 1a9:	83 f8 0a             	cmp    eax,0xa
 1ac:	76 e6                	jbe    194 <__Z5main2v+0xc>
 1ae:	a1 04 00 00 00       	mov    eax,ds:0x4
 1b3:	89 04 24             	mov    DWORD PTR [esp],eax
 1b6:	b9 00 00 00 00       	mov    ecx,0x0
 1bb:	e8 00 00 00 00       	call   1c0 <__Z5main2v+0x38>
 1c0:	53                   	push   ebx
 1c1:	89 c6                	mov    esi,eax
 1c3:	8b 00                	mov    eax,DWORD PTR [eax]
 1c5:	8b 40 f4             	mov    eax,DWORD PTR [eax-0xc]
 1c8:	8b 5c 06 7c          	mov    ebx,DWORD PTR [esi+eax*1+0x7c]
 1cc:	85 db                	test   ebx,ebx
 1ce:	74 50                	je     220 <__Z5main2v+0x98>
 1d0:	80 7b 1c 00          	cmp    BYTE PTR [ebx+0x1c],0x0
 1d4:	74 32                	je     208 <__Z5main2v+0x80>
 1d6:	8a 43 27             	mov    al,BYTE PTR [ebx+0x27]
 1d9:	0f be c0             	movsx  eax,al
 1dc:	89 04 24             	mov    DWORD PTR [esp],eax
 1df:	89 f1                	mov    ecx,esi
 1e1:	e8 00 00 00 00       	call   1e6 <__Z5main2v+0x5e>
 1e6:	52                   	push   edx
 1e7:	89 c1                	mov    ecx,eax
 1e9:	e8 00 00 00 00       	call   1ee <__Z5main2v+0x66>
 1ee:	31 c0                	xor    eax,eax
 1f0:	83 c4 14             	add    esp,0x14
 1f3:	5b                   	pop    ebx
 1f4:	5e                   	pop    esi
 1f5:	c3                   	ret    
 1f6:	66 90                	xchg   ax,ax
 1f8:	89 54 24 04          	mov    DWORD PTR [esp+0x4],edx
 1fc:	89 04 24             	mov    DWORD PTR [esp],eax
 1ff:	e8 e8 fe ff ff       	call   ec <__Z7deflateii>
 204:	eb 89                	jmp    18f <__Z5main2v+0x7>
 206:	66 90                	xchg   ax,ax
 208:	89 d9                	mov    ecx,ebx
 20a:	e8 00 00 00 00       	call   20f <__Z5main2v+0x87>
 20f:	8b 03                	mov    eax,DWORD PTR [ebx]
 211:	c7 04 24 0a 00 00 00 	mov    DWORD PTR [esp],0xa
 218:	89 d9                	mov    ecx,ebx
 21a:	ff 50 18             	call   DWORD PTR [eax+0x18]
 21d:	51                   	push   ecx
 21e:	eb b9                	jmp    1d9 <__Z5main2v+0x51>
 220:	e8 00 00 00 00       	call   225 <__Z5main2v+0x9d>
 225:	90                   	nop
 226:	90                   	nop
 227:	90                   	nop

...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195782
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mingw 4.7.1
mingw32-g++.exe -Wall -fexceptions -fomit-frame-pointer -O2
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195879
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SiemarglЧуть позже выложу ассемблер
Для начала неплохо было бы исходник хотя бы выложить )))
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39195939
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskySiemarglЧуть позже выложу ассемблер
Для начала неплохо было бы исходник хотя бы выложить )))
Да хотелось подавану дать время самому подумать. Думаешь уже хватит?
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196227
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
int erased;
int is[] = {10, 3,3, 2, 2, 1, 1, 1, 2, 2, 3, 3};
int trick;

int deflate(int left, int right)
{
    TRC;
    int new_left = left, new_right = right;
    while(new_left > 0 && is[--new_left] == is[left]);

    while(new_right < sizeof is / sizeof(is[0]) && is[++new_right] == is[right]);

    int erased_in = left - new_left + new_right - right;
    if(erased_in > 2)
    {
        erased += erased_in;
        new_right = deflate(new_left, new_right);
    }

    return new_right;
}

int main()
{

    for (int i =0; i < sizeof is / sizeof(is[0]) -1;)
        if(is[i] == is[i+1])
            i = deflate(i, i+1);
        else
            i++;

    std::cout << erased << std::endl;
    return 0;
}


Dima TSiemarglПриврал. Проверил. Вдвое.
На данных 10 3 3 2 2 1 1 1 2 2 3 3
у АМ 13 вызовов функций (не включая работу с вектором)
у меня - 6
у АМ 0 (ноль) вызовов функций. Вызовы компилятор уберет. Если не веришь компиляторам - у него можно просто скопипастить весь код в main(), функции там только для для читаемости кода, с рекурсией это невозможно, так что 6:0, а не 6:13.
Я не верю =)

ИМХО, у них от шаблонного объектного кода крыша съезжает. В простых случаях - нормально инлайнит и оптимизирует, но с сегодняшней модой на простые пятимерные шаблоны смотри сам, какой код генерится. Это типовой образец причем.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196315
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
bool match_back(std::vector<int>& state, int v)
{
	return state.size() >= 2
		&& state[state.size() - 1] == v
		&& state[state.size() - 2] == v;
}

int erase_back(std::vector<int>& state, int v)
{
	int erased = 0;
	while (state.size() > 0 && state[state.size() - 1] == v) {
		state.pop_back();
		erased++;
	}
	return erased;
}


int main()
{
00C42240  push        ebp  
00C42241  mov         ebp,esp  
00C42243  push        0FFFFFFFFh  
00C42245  push        0C6902Dh  
00C4224A  mov         eax,dword ptr fs:[00000000h]  
00C42250  push        eax  
00C42251  sub         esp,0D0h  
00C42257  mov         eax,dword ptr [__security_cookie (0C761BCh)]  
00C4225C  xor         eax,ebp  
00C4225E  mov         dword ptr [ebp-10h],eax  
00C42261  push        ebx  
00C42262  push        esi  
00C42263  push        edi  
00C42264  push        eax  
00C42265  lea         eax,[ebp-0Ch]  
00C42268  mov         dword ptr fs:[00000000h],eax  
00C4226E  push        0A8h  
00C42273  lea         eax,[is]  
00C42279  push        0  
00C4227B  push        eax  
00C4227C  call        memset (0C51E10h)  
00C42281  add         esp,0Ch  
	//std::istringstream is ("5 1 3 3 3 2");
	std::istringstream is("10 3 3 2 1 1 1 2 2 3 3");
00C42284  mov         dword ptr [ebp-18h],0Fh  
00C4228B  lea         ecx,[ebp-2Ch]  
00C4228E  mov         dword ptr [ebp-1Ch],0  
00C42295  mov         byte ptr [ebp-2Ch],0  
00C42299  push        16h  
00C4229B  push        offset string "10 3 3 2 1 1 1 2 2 3 3" (0C72888h)  
00C422A0  call        std::basic_string<char,std::char_traits<char>,std::allocator<char> >::assign (0C45000h)  
00C422A5  sub         esp,8  
00C422A8  mov         dword ptr [ebp-4],0  
00C422AF  lea         eax,[ebp-2Ch]  
00C422B2  lea         ecx,[is]  
00C422B8  push        eax  
00C422B9  call        std::basic_istringstream<char,std::char_traits<char>,std::allocator<char> >::basic_istringstream<char,std::char_traits<char>,std::allocator<char> > (0C42740h)  
00C422BE  mov         eax,dword ptr [ebp-18h]  
00C422C1  cmp         eax,10h  
00C422C4  jb          main+93h (0C422D3h)  
00C422C6  inc         eax  
00C422C7  lea         ecx,[ebp-2Ch]  
00C422CA  push        eax  
00C422CB  push        dword ptr [ebp-2Ch]  
00C422CE  call        std::allocator<char>::deallocate (0C455F0h)  
00C422D3  xorps       xmm0,xmm0  
	std::vector<int> state;
00C422D6  xor         ebx,ebx  
	int erased = 0;
00C422D8  xor         edi,edi  
00C422DA  movq        mmword ptr [ebp-20h],xmm0  
	std::vector<int> state;
00C422DF  xor         esi,esi  
	int erased = 0;
00C422E1  mov         dword ptr [ebp-0D8h],edi  
00C422E7  mov         dword ptr [state],ebx  
00C422EA  mov         dword ptr [ebp-1Ch],esi  
00C422ED  mov         dword ptr [ebp-18h],ebx  
	int erase_v = -1;
	int v;
	while (is >> v) {
00C422F0  lea         eax,[v]  
00C422F3  mov         byte ptr [ebp-4],3  
00C422F7  push        eax  
00C422F8  lea         ecx,[is]  
00C422FE  mov         dword ptr [ebp-0DCh],0FFFFFFFFh  
00C42308  call        std::basic_istream<char,std::char_traits<char> >::operator>> (0C42FB0h)  
00C4230D  mov         ecx,dword ptr [eax]  
00C4230F  mov         ecx,dword ptr [ecx+4]  
00C42312  test        byte ptr [ecx+eax+0Ch],6  
00C42317  jne         main+181h (0C423C1h)  
00C4231D  nop         dword ptr [eax]  
		if (erase_v == v) {
00C42320  mov         edx,dword ptr [v]  
00C42323  cmp         dword ptr [erase_v],edx  
00C42329  jne         main+0F4h (0C42334h)  
			erased++;
00C4232B  inc         edi  
00C4232C  mov         dword ptr [erased],edi  
00C42332  jmp         main+162h (0C423A2h)  
		}
		else if (match_back(state, v)) {
00C42334  mov         ecx,esi  
00C42336  sub         ecx,ebx  
00C42338  mov         eax,ecx  
00C4233A  sar         eax,2  
00C4233D  cmp         eax,2  
00C42340  jb          main+146h (0C42386h)  
00C42342  cmp         dword ptr [ebx+eax*4-4],edx  
00C42346  jne         main+146h (0C42386h)  
00C42348  cmp         dword ptr [ebx+eax*4-8],edx  
00C4234C  jne         main+146h (0C42386h)  
			erased += erase_back(state, v);
00C4234E  xor         edi,edi  
00C42350  test        eax,eax  
00C42352  je          main+12Dh (0C4236Dh)  
00C42354  cmp         dword ptr [ebx+eax*4-4],edx  
00C42358  jne         main+12Ah (0C4236Ah)  
00C4235A  sub         ecx,4  
00C4235D  sub         esi,4  
00C42360  mov         eax,ecx  
00C42362  inc         edi  
00C42363  sar         eax,2  
00C42366  test        eax,eax  
00C42368  jne         main+114h (0C42354h)  
00C4236A  mov         dword ptr [ebp-1Ch],esi  
			erase_v = v;
			erased++;
00C4236D  mov         eax,dword ptr [erased]  
00C42373  inc         eax  
00C42374  mov         dword ptr [erase_v],edx  
00C4237A  add         eax,edi  
00C4237C  mov         dword ptr [erased],eax  
		}
		else {
00C42382  mov         edi,eax  
00C42384  jmp         main+162h (0C423A2h)  
			erase_v = -1;
			state.push_back(v);
00C42386  lea         eax,[v]  
00C42389  mov         dword ptr [erase_v],0FFFFFFFFh  
00C42393  push        eax  
00C42394  lea         ecx,[state]  
00C42397  call        std::vector<int,std::allocator<int> >::push_back (0C42480h)  
00C4239C  mov         esi,dword ptr [ebp-1Ch]  
00C4239F  mov         ebx,dword ptr [state]  
	int erase_v = -1;
	int v;
	while (is >> v) {
00C423A2  lea         eax,[v]  
00C423A5  push        eax  
00C423A6  lea         ecx,[is]  
00C423AC  call        std::basic_istream<char,std::char_traits<char> >::operator>> (0C42FB0h)  
00C423B1  mov         ecx,dword ptr [eax]  
00C423B3  mov         ecx,dword ptr [ecx+4]  
00C423B6  test        byte ptr [ecx+eax+0Ch],6  
00C423BB  je          main+0E0h (0C42320h)  
		}
	}
	cout << erased << endl;
00C423C1  push        edi  
00C423C2  call        std::basic_ostream<char,std::char_traits<char> >::operator<< (0C42DE0h)  
00C423C7  push        eax  
00C423C8  call        std::endl<char,std::char_traits<char> > (0C48CB0h)  
00C423CD  add         esp,4  
	return 0;


Как видишь match_back() и erase_back() заинлайнились.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196321
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот так твой код скомпилировался
Код: 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.
int erased;
int is[] = { 10, 3,3, 2, 2, 1, 1, 1, 2, 2, 3, 3 };
int trick;

int deflate(int left, int right)
{
00832130  push        esi  
00832131  push        edi  
00832132  mov         edi,ecx  
	//TRC;
	int new_left = left, new_right = right;
00832134  mov         eax,edx  
00832136  mov         esi,edi  
	while (new_left > 0 && is[--new_left] == is[left]);
00832138  test        esi,esi  
0083213A  jle         deflate+20h (0832150h)  
0083213C  mov         ecx,dword ptr [esi*4+85A858h]  
00832143  dec         esi  
00832144  cmp         ecx,dword ptr is (085A85Ch)[edi*4]  
0083214B  je          deflate+8h (0832138h)  
0083214D  nop         dword ptr [eax]  

	while (new_right < sizeof is / sizeof(is[0]) && is[++new_right] == is[right]);
00832150  cmp         eax,0Ch  
00832153  jae         deflate+36h (0832166h)  
00832155  mov         ecx,dword ptr [eax*4+85A860h]  
0083215C  inc         eax  
0083215D  cmp         ecx,dword ptr is (085A85Ch)[edx*4]  
00832164  je          deflate+20h (0832150h)  

	int erased_in = left - new_left + new_right - right;
00832166  mov         ecx,eax  
00832168  sub         ecx,esi  
0083216A  sub         ecx,edx  
0083216C  add         ecx,edi  
0083216E  pop         edi  
	if (erased_in > 2)
0083216F  cmp         ecx,2  
00832172  jle         deflate+54h (0832184h)  
	{
		erased += erased_in;
00832174  add         dword ptr [erased (085FE94h)],ecx  
		new_right = deflate(new_left, new_right);
0083217A  mov         edx,eax  
0083217C  mov         ecx,esi  
0083217E  pop         esi  
0083217F  jmp         deflate (0832130h)  
00832184  pop         esi  
	}

	return new_right;
}
00832185  ret  
--- No source file -------------------------------------------------------------
00832186  int         3  
00832187  int         3  
00832188  int         3  
00832189  int         3  
0083218A  int         3  
0083218B  int         3  
0083218C  int         3  
0083218D  int         3  
0083218E  int         3  
0083218F  int         3  
--- m:\vc2015\test\test.cpp ----------------------------------------------------

int main()
{
00832190  push        esi  

	for (int i = 0; i < sizeof is / sizeof(is[0]) - 1;)
00832191  xor         edx,edx  
00832193  push        edi  
00832194  nop         dword ptr [eax]  
00832198  nop         dword ptr [eax+eax]  
		if (is[i] == is[i + 1])
008321A0  mov         ecx,dword ptr is (085A85Ch)[edx*4]  
008321A7  cmp         ecx,dword ptr [edx*4+85A860h]  
008321AE  jne         main+6Bh (08321FBh)  
			i = deflate(i, i + 1);
008321B0  lea         edi,[edx+1]  
008321B3  mov         esi,edx  
008321B5  mov         eax,edi  
008321B7  test        esi,esi  
008321B9  jle         main+35h (08321C5h)  
008321BB  dec         esi  
008321BC  cmp         dword ptr is (085A85Ch)[esi*4],ecx  
008321C3  je          main+27h (08321B7h)  
008321C5  cmp         eax,0Ch  
008321C8  jae         main+4Bh (08321DBh)  
008321CA  mov         ecx,dword ptr [eax*4+85A860h]  
008321D1  inc         eax  
008321D2  cmp         ecx,dword ptr is (085A85Ch)[edi*4]  
008321D9  je          main+35h (08321C5h)  
			i = deflate(i, i + 1);
008321DB  mov         ecx,eax  
008321DD  sub         ecx,esi  
008321DF  sub         ecx,edi  
008321E1  add         ecx,edx  
008321E3  cmp         ecx,2  
008321E6  jle         main+67h (08321F7h)  
008321E8  add         dword ptr [erased (085FE94h)],ecx  
008321EE  mov         edx,eax  
008321F0  mov         ecx,esi  
008321F2  call        deflate (0832130h)  
008321F7  mov         edx,eax  
		else
008321F9  jmp         main+6Ch (08321FCh)  
			i++;
008321FB  inc         edx  

	for (int i = 0; i < sizeof is / sizeof(is[0]) - 1;)
008321FC  cmp         edx,0Bh  
008321FF  jb          main+10h (08321A0h)  

	std::cout << erased << std::endl;
00832201  push        ecx  
00832202  call        std::basic_ostream<char,std::char_traits<char> >::operator<< (0832300h)  
00832207  push        eax  
00832208  call        std::endl<char,std::char_traits<char> > (0834790h)  
0083220D  add         esp,4  
	return 0;


deflate() не инлайнится, т.к. рекурсия.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196365
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

Рекурсия, какая рекурсия?

Где ты видишь рекурсивный вызов в ассемблере? =)
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196367
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
тут
Код: plaintext
1.
2.
3.
4.
5.
int deflate(int left, int right)
{
...
new_right = deflate(new_left, new_right);
...
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196425
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Господа, вам не стыдно сравнивать скорость кода который читает из потока и кода который работает с уже считанным массивом? )))
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196439
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyГоспода, вам не стыдно сравнивать скорость кода который читает из потока и кода который работает с уже считанным массивом? )))
Это не принципиально. Оба кода в итоге прочитают массив целиком. Хотя можно было бы и не дочитывать.

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

PS Еще код Siemargl 18954238 неправильно считает. В принципе это тоже не важно :)
Код: plaintext
1.
int is[] = { 10, 3, 3, 2, 2, 1, 1, 1, 3, 2, 3, 3 };
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196451
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TЭто не принципиально. Оба кода в итоге прочитают массив целиком. Хотя можно было бы и не дочитывать.
Это принципиально. Потому что чтение например 1000 чисел займет несколько миллисекунд, а сам алгоритм их обработки - несколько микросекунд (что один что второй). Поэтому считать такты на вызовы функций, когда I/O на порядки медленнее - бессмысленная работа ))
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196508
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

Срочный сервис пак =)
Код: plaintext
1.
2.
        if (is[new_left] == is[new_right])
            new_right = deflate(new_left, new_right);



С точки зрения практической выгоды, конечно дисковое чтение гораздо дольше.

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

Чтение из потока дает небольшую добавку в инструкциях (хотя хз, почему MSVC дважды сгенерил этот кусок)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
00C422F0  lea         eax,[v]  
00C422F3  mov         byte ptr [ebp-4],3  
00C422F7  push        eax  
00C422F8  lea         ecx,[is]  
00C422FE  mov         dword ptr [ebp-0DCh],0FFFFFFFFh  
00C42308  call        std::basic_istream<char,std::char_traits<char> >::operator>> (0C42FB0h)  
00C4230D  mov         ecx,dword ptr [eax]  
00C4230F  mov         ecx,dword ptr [ecx+4]  
00C42312  test        byte ptr [ecx+eax+0Ch],6 

...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196516
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хотя нет, GCC рекурсию оставил.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196523
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Написал для сравнения с учетом вышеизложенных замечаний. (без функций, шаблонов и потокового чтения)
Исходник
Код: 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.
int is[] = { 10, 3, 3, 2, 2, 1, 1, 1, 2, 3, 3 };

int main()
{
	int* end = is + sizeof(is) / sizeof(is[0]);
	// Поиск 3+ подряд
	int* cur = is + 1;
	int cnt = 1;
	for (; cur < end; cur++) {
		if(*(cur - 1) == *cur) {
			cnt++;
		} else if(cnt >= 3) {
			break;
		} else {
			cnt = 1;
		}
	}
	if(cnt >= 3) {
		// Схлапывание по краям найденного
		while(1) {
			int* left = cur - cnt - 1;
			if (*left != *cur) break;
			int cnt_add = 2;
			// Подсчет влево
			left--;
			if (left >= is && *left == *cur) cnt_add++;
			// Подсчет вправо
			cur++;
			if(cur < end && *(cur - 1) == *cur) cnt_add++;
			if (cnt_add < 3) break;
			cnt += cnt_add;
		}
	}

	std::cout << cnt << std::endl;
	return 0;
}


в асме
Код: 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.
	int* end = is + sizeof(is) / sizeof(is[0]);
	// Поиск 3+ подряд
	int* cur = is + 1;
00DC2130  mov         eax,0DEEB54h  
	int cnt = 1;
00DC2135  mov         edx,1  
00DC213A  nop         word ptr [eax+eax]  
		if(*(cur - 1) == *cur) {
00DC2140  mov         ecx,dword ptr [eax-4]  
00DC2143  cmp         ecx,dword ptr [eax]  
00DC2145  jne         main+1Ah (0DC214Ah)  
			cnt++;
00DC2147  inc         edx  
00DC2148  jmp         main+24h (0DC2154h)  
		} else if(cnt >= 3) {
00DC214A  cmp         edx,3  
00DC214D  jge         main+33h (0DC2163h)  
			break;
		} else {
			cnt = 1;
00DC214F  mov         edx,1  
	for (; cur < end; cur++) {
00DC2154  add         eax,4  
00DC2157  cmp         eax,0DEEB7Ch  
00DC215C  jb          main+10h (0DC2140h)  
		}
	}
	if(cnt >= 3) {
00DC215E  cmp         edx,3  
00DC2161  jl          main+91h (0DC21C1h)  
00DC2163  push        edi  
		// Схлапывание по краям найденного
		while(1) {
			int* left = cur - cnt - 1;
00DC2164  lea         ecx,[edx*4+4]  
00DC216B  mov         edi,eax  
00DC216D  sub         edi,ecx  
			if (*left != *cur) break;
00DC216F  mov         ecx,dword ptr [eax]  
00DC2171  cmp         dword ptr [edi],ecx  
00DC2173  jne         main+90h (0DC21C0h)  
00DC2175  push        ebx  
00DC2176  mov         ebx,3  
00DC217B  push        esi  
00DC217C  nop         dword ptr [eax]  
			int cnt_add = 2;
			// Подсчет влево
			left--;
00DC2180  sub         edi,4  
00DC2183  mov         esi,2  
			if (left >= is && *left == *cur) cnt_add++;
00DC2188  cmp         edi,offset is (0DEEB50h)  
00DC218E  jb          main+65h (0DC2195h)  
00DC2190  cmp         dword ptr [edi],ecx  
00DC2192  cmove       esi,ebx  
			// Подсчет вправо
			cur++;
00DC2195  add         eax,4  
			if(cur < end && *(cur - 1) == *cur) cnt_add++;
00DC2198  cmp         eax,0DEEB7Ch  
00DC219D  jae         main+77h (0DC21A7h)  
00DC219F  mov         ecx,dword ptr [eax-4]  
00DC21A2  cmp         ecx,dword ptr [eax]  
00DC21A4  jne         main+77h (0DC21A7h)  
00DC21A6  inc         esi  
			if (cnt_add < 3) break;
00DC21A7  cmp         esi,ebx  
00DC21A9  jl          main+8Eh (0DC21BEh)  
			cnt += cnt_add;
00DC21AB  add         edx,esi  
00DC21AD  mov         edi,eax  
00DC21AF  lea         ecx,[edx*4+4]  
00DC21B6  sub         edi,ecx  
			cnt += cnt_add;
00DC21B8  mov         ecx,dword ptr [eax]  
00DC21BA  cmp         dword ptr [edi],ecx  
00DC21BC  je          main+50h (0DC2180h)  
00DC21BE  pop         esi  
00DC21BF  pop         ebx  
00DC21C0  pop         edi  
		}
	}

	std::cout << cnt << std::endl;
00DC21C1  push        edx  
00DC21C2  call        std::basic_ostream<char,std::char_traits<char> >::operator<< (0DC22C0h)  
00DC21C7  push        eax  
00DC21C8  call        std::endl<char,std::char_traits<char> > (0DC4750h)  
00DC21CD  add         esp,4  
	return 0;

...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196552
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Немного потестил. Тоже срочный сервиспак надо :)
Код: 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.
int is[] = { 4, 4, 3, 3, 2, 1, 1, 1, 2, 2, 3, 4, 4 };

int main()
{
	int* end = is + sizeof(is) / sizeof(is[0]);
	// Поиск 3+ подряд
	int* cur = is + 1;
	int cnt = 1;
	for (; cur < end; cur++) {
		if(*(cur - 1) == *cur) {
			cnt++;
		} else if(cnt >= 3) {
			break;
		} else {
			cnt = 1;
		}
	}
	if(cnt < 3) {
		cnt = 0;
	} else {
		// Схлапывание по краям найденного
		int* left = cur - cnt - 1;
		while(cur < end && left >= is && *left == *cur) {
			int cnt_add = 2;
			// Подсчет влево
			left--;
			if (left >= is && *left == *cur) {
				cnt_add++;
				left--;
			}
			// Подсчет вправо
			cur++;
			if(cur < end && *(cur - 1) == *cur) {
				cnt_add++;
				cur++;
			}
			if (cnt_add < 3) break;
			cnt += cnt_add;
			
		}
	}

	std::cout << cnt << std::endl;
	return 0;
}


получилась тоже что и у тебя с рекурсией, только цикл вместо рекурсии.
...
Рейтинг: 0 / 0
Шарики(задача по программированию)
    #39196633
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

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

что то типа /Ox /G7 /Oy
...
Рейтинг: 0 / 0
93 сообщений из 93, показаны все 4 страниц
Форумы / C++ [игнор отключен] [закрыт для гостей] / Шарики(задача по программированию)
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]