Когда алгоритм верный, а всё равно TL

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

Чтение целых чисел

1. Accepted in 0.193
std::ios_base::sync_with_stdio(0);
//...
std::cin >> a[i];
2. Accepted in 0.187
scanf("%d", &a[i]);
3. Accepted in 0.109
int nextInt() {
    int res = 0,c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res;
}
//...
a[i] = nextInt();
4. Accepted in 0.098
a[i] = 00;
c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') {
    a[i] = a[i] * 10 + c - '0';
    c = getchar();
}

Наиболее интересно резкое отличие между вторым и третьим пунктом. Также интересны третий и четвёртый: ведь в последнем идёт многократное обращение к элементу массива, что по идее требует больше времени, чем один раз вызвать функцию.

Обращение к массиву

1. Time Limit Exceeded (test 9)
for(int i = 0; i < n; i ++) {
    //Много операций с array[i]
}
2. Accepted
for(int i = 0; i < n; i ++) {
    double x = array[i];
    //Много операций с x
}
Возможно, эти наблюдения смогут кому-то помочь. Мне, скажем, помогали :)
Поделиться публикацией

Комментарии 62

    0
    А в первом примере прописано ios_base::sync_with_stdio(0)?
      0
      Да. Допишу в приведённый код для ясности.
      +1
      А что бы ассемблерные вставки не попользовать как в старые добрые времена? ;)
        0
        До такого пока не доходило.
          +1
          На самом деле ассемблерные вставки почти всегда вырезаются. Если не ошибаюсь, так делает acm.timus.ru.
            0
            Неоптимизированные пользователем будет медленнее, чем код, генерируемы компилятором.
            Т.е. тот код, который пишут в универах на лабах на асме сольет по скорости современным компилерам.
            Оптимизация займет нереально много времени.
            +25
            ИМХО по этим статьям может сложиться превратное впечатление о спортивном программировании вообще. Неужели, единственное о чем автор счет нужным рассказать, так это о том, что стандартные функции scanf и printf работают медленно собственноручно написанных?
            Нашей команде за 5 лет в СП ни в одной задаче этого не потребовалось, т.к. чаще всего ввод-вывод данных занимает малую часть времени, а если это не так, то авторы задач ставят временные ограничения, чтобы scanf/printf тоже укладывался в TL. Так что эта статья бесполезна для СП-программиста. Зато у остальных может сложиться впечатление, что люди занимающиеся спортивным программированием — это люди, которые занимаются ненужной и бесполезной оптимизацией чуть ли не на уровне ассемблерных вставок.
            Лучше бы вы рассказали пример когда какой нибудь неочевидный хитрый алгоритм или оптимизация дала существенный выйгрыш во времени.
              +4
              Расскажу.
                +5
                Я думаю никто не будет против, если и вы поделитесь парочкой своих красивых алгоритмов
                  0
                  Не ответил сразу, потому что был как раз на турнире по СП :)
                  Да, я планирую это сделать в ближайшее время
                  –1
                  С другой стороны, на Хабре наконец-то появились статьи о спортивном программировании. А то, что iostream пользоваться там не стоит — must know для любого.
                    +4
                    преждевременная оптимизация — зло :)
                      –1
                      IMHO, выбор — использовать для ввода данных scanf или cin не относится к тому, что Кнут назвал premature optimization в своей знаменитой цитате :)
                  +1
                  Нифига вызов функции не быстрее чтения/записи в массив. Массив — статическая штука, а для процедуры требуется делать много лишних телодвижений.

                  По второму примеру: я не профи по оптимизации С++, но разве «вумный» компилятор не должен автоматом приводить первый вариант ко второму?
                    0
                    А где гарантия что у меня умный компилятор?
                      0
                      В спеках к тестирующей системе обычно указываются ключи компиляции, а на машине пользователя обычно стоит тот же компилятор. Так что если не точную скорость, то порядок ускорения можно высчитать и на своей машине.

                      Ну и то, что не сильно тормознутый компилятор преобразует работу с элементом массива в работу с числом на стеке (а то и в регистре уже) — вполне естественно. Обычно они так и делают =)
                      0
                      разве «вумный» компилятор не должен автоматом приводить первый вариант ко второму?


                      строго говоря, нельзя судить о «вумности» компилятора не зная, что там в теле цикла.

                      что бы компилятор мог привести первый вариант ко второму, он должен доказать, что в теле никто не пишет в массив индексу i.
                        0
                        м. Подумал. Понял, что в современном подходе (а он императивный — ООП это надстройка), такое доказать довольно тяжело. Согласился )
                          0
                          ну как бы не всегда тяжело, но иногда просто невозможно, а иногда вполне просто…

                          эту проблему (фактически — зависимости по данным) начиная, наверное, с Фортрана исследуют (для распараллеливания это тоже важно)…

                          отказавшись от мутабельности можно огрести других оптимизационных проблем, которые не особо-то легче.
                            0
                            можно тогда попросить в ящик кинуть инфы, какая по этой теме есть? Я занимаюсь чем-то вроде фреймворка на основе семантической сети (где один из профитов — явное указание очень разных зависимостей), было бы очень интересно узнать новые возможности/косяки.
                        0
                        Если бы кто-то читал внимательнее, он бы заметил, что сравнивал я многократное обращение к массиву и единичный вызов функции.
                          0
                          каюсь =)
                        +1
                        А главный секрет — как получить Accepted за 0.031 — так и не раскрыли :)
                          0
                          Действительно. ИМХО, было-бы интересней разобрать задачку и несколько вариантов её решения.
                            +1
                            Эту задачу автор уже разбирал в своей предыдущей статье. Решение — двоичный поиск либо дерево либо хэш-таблица. Вопрос в том, что за грязный хак он применил, чтобы получить такое время :)

                            Я сейчас добился 0.046. Но моё решение уже не является верным, хотя проходит тесты.
                              0
                              А ты ячейки хеш-таблицы попробуй по-разному хранить. Скажем, вектором и списком. У меня быстрее было списком, хотя в векторе я проверял содержимое за O(logsk), а в списке — за O(sk). (sk — размер класса эквивалентности)
                                0
                                Прикол в том, что у меня вообще нет хэш-таблицы :)

                                Мой алгоритм таков:

                                char a[65536];
                                для каждого x из первого списка: a[x&65535] = 1
                                для каждого x из второго списка: answer += a[x&65535]
                                  0
                                  Чтение данных: fread всего входного фала в начале программы в массив char[7000000]. Затем числа из него парсятся вручную.
                                    0
                                    Это вполне так можно назвать хеш-таблицей. x&65535 — это хеш икса. А вот с чтением данных кто-то суров!
                                      0
                                      Замена fread на чтение данных через getchar() не уменьшила время.
                                      Но ещё более грязным путём я добился 0.015 :)
                                        0
                                        Забавно. Особенно — учитывая, что это не верно.
                                        А что за грязный путь?)
                                          0
                                          Как, не верно?! Ты же сам сказал, что это можно назвать хэш-таблицей! :)
                                          В общем, суть в том, чтобы определить параметры самого большого теста и ответ для него, и сразу выдавать ответ, не тратя время на его решение.
                                            0
                                            Это я погорячился)
                                            Омг, это уж совсем не спортивно. У этой задачи слабые тестовые данные. Думаю, скоро администрация это заметит и исправит.
                                              0
                                              Какие бы ни были тестовые данные, их в любом случае можно найти за O(количество_тестов * log(размер_теста)) сабмитов.
                            0
                            Государственная тайна:) Иначе уж не интересно будет. Но обладая исследовательским интересом и содержимым этой статьи можно получить 0.031)
                            0
                            В случае с массивом странное поведение, по логике получается что автоматическая переменная в регистре, а элемент массива каждый раз добавляет обращение к памяти. Такое ощущение что с другой стороны интерпретатор языка, и не особо быстрый.
                              0
                              кстати, да — такой разброс времени выполнения наблюдается на разных компиляторах?
                                0
                                На MinGW и на microsoft'овском тестил.
                              • НЛО прилетело и опубликовало эту надпись здесь
                                  0
                                  boost божаться что у них lexical_cast даже быстрее чем itoa :)
                                    0
                                    это кстати к вопросу почему нет itoa в примерах, автор не вкурсе? :-)
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                        0
                                        юзанье буста делает свое грязное дело, уже забыл как atoi называется :)
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                              0
                                              учитывая что эту функцию я юзал года три назад последний раз, думаю простительно :)
                                    +2
                                    думается мне, что вместо
                                    4. Accepted in 0.98
                                    вы хотели написать
                                    4. Accepted in 0.098
                                      0
                                      Воистину :)
                                      0
                                      Экономия на спичках. По личному опыту знаю, TL ставится из ограничения 1.5-2*время решения жюри. Так что если тут настолько роляет одна десятая секунды, то стоит задуматься над алгоритмом. Один раз такое было, что после переписывания с плюсовых ввода из потока и std::vector на сишные считывания и указатели удалось-таки пропихнуть задачу. Разговаривали потом с автором, оказалось, что у нас просто алгоритм был тупой и лажовый, а тут мы просто задачу «навазелинили» и пропихнули.

                                      Для Java описанное более справедливо, так как там java.util.Scanner работает куда медленнее, нежели StreamTokenizer. Потому первый из них (по причине удобства) используется лишь на инпутах порядка килобайта.
                                        0
                                        Ну и это, умные обёртки (по типу потоков и всякого другого) обычно буферизуют ввод, что ускоряет всё дело, считывание же посимвольно может этого и не делать (навскидку не скажу, умеет ли getchar() буферизацию).
                                          0
                                          А ещё бывает, когда TL считали на быстрой машине, а контест запустили на медленной.
                                            0
                                            Это уже вопрос честности и профессионализма организаторов. Если уж на то пошло, могут и памяти в два раза меньше выдать. Лимиты не с потолка берут и учитывают, что команды по ним ориентируются.
                                          +1
                                          Разве это чтение _целых_ чисел? Это чтение натуральных чисел. Отрицательное число не прочитается, так как минус нигде не учитывается, ИМХО…
                                            0
                                            Учесть минус — добавить пару строчек и O(1) операций, велика разница.
                                            0
                                            4. Accepted in 0.98
                                            или
                                            4. Accepted in 0.098
                                            ?
                                              +2
                                              Прошу прощения, проглядел предыдущий аналогичный коммент с аналогичным вопросом.
                                              0
                                              Добавлю, что std::ios_base::sync_with_stdio(0), видимо, в разы ускоряет чтение, но использование cout для вывода целых чисел все равно очень тормозит по сравнению с printf("%d\n", x).
                                                0
                                                ведь в последнем идёт многократное обращение к элементу массива, что по идее требует больше времени, чем один раз вызвать функцию.


                                                Эм. А что, по вашему, делает эта функция?
                                                    0
                                                    Да-да, я читал. Только это не ответ на мой вопрос =)
                                                      0
                                                      Тогда почётче сформулируйте свой вопрос. Функция делает то же самое, но обращается не к элементу массива, а к одной переменной.
                                                  0
                                                  Хорошую вещь автор подметил, возьму на заметку) Но и с комментариями прочими согласен — если TL уже, то она не спасёт)

                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                  Самое читаемое