Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1 2 3
  21  Егоров Илья Валерьевич, 20 августа 2019 г. 21:52:43
     Хорошие методы ввода по убыванию производительности: 0) См. пункт 1. В дополнение к там описанному еще и снижение влияния предсказателя ветвлений, зная максимальную длину токена (т.е. вместо проверки достижения конца буфера после каждого символа делаем это после считывания полностью числа). Еще более небезопасно, но еще более быстрее. 1) fread из stdio или in.read из iostream (с отключением блокировки) с кастомным небезопасным парсером. Если верить анализу выхлопа на ассемблере, fread все же быстрее из-за меньшего кол-ва инструкций. Очень быстро, но в прод лучше не надо. 2) fgetc из stdio с тем же парсером, но из-за идентичности логики и отсутствия буферизации смысла не имеет. 3) scanf из stdio. Как компромисс между скоростью, безопасностью и удобством. 4) Ввод через >> из iostream. Медленный, но безопасный и удобный. Отключайте синхронизацию только если уверены, что вы не будете смешивать чтение через stdio и iostream. Вы можете сами убедиться в их производительности, если пожелаете.
  22  Егоров Илья Валерьевич, 20 августа 2019 г. 21:36:53
     Не соглашусь. Без отключения синхронизации iostream будет делать лишние действия, а если вы отключаете синхронизацию для iostream, но используете при этом stdio, то это не имеет смысла. Заметить мало: надо еще и доказать. Увы, мои бенчмарки не подтверждают ваши наблюдения.
  23  Ерёменко Владислав Владиславович, 20 августа 2019 г. 14:49:39
     Давно заметил одну штуку, что обычный файловый ввод-вывод работает лучше таких бустов, как ios_base::sync_with_stdio... и printf, scanf. Поэтому напишите программу через cin, cout и вставьте в самом начале это: ifstream cin("input.txt"); ofstream cout("output.txt"); И всё, тогда пройдёт.
  24  ГРигорий горбаченко, 29 января 2019 г. 18:58:40
     тест который помог 3 -30000 -30000 -30000
  25  Коншин Андрей Сергеевич, 04 сентября 2018 г. 11:14:24
     Если кому-то интересно, почему потоки ввода в C++ медленные, то вот статья: https://habr.com/post/246257/ А если ничего из статья непонятно, то просто перед первым вводов напишите: std::ios::sync_with_stdio(false);
     Ещё рекомендуют std::cin.tie(nullptr);
  26  Винк В В, 27 июня 2018 г. 8:37:44
     Используем <stdio.h> и scanf() и всё заходит за полсекунды. И printf("%lld",ans) нормально работает. Ну и, конечно, алгоритм должен быть близок к оптимальному.
  27  Егоров Илья Валерьевич, 21 апреля 2018 г. 0:31:40
     Кирилл, вот только как это избавит от сохранения всей строки (без использования ctypes)?
  28  Генералов Кирилл Витальевич, 20 апреля 2018 г. 12:05:00
     Илья, у меня появилась идея. Можно сделать подмассив, как срез, из 5 чисел (3 макс. и 2 мин.) и просто двигать его вправо посимвольно, тем самым ища нужные элементы, не взаимодействуя кучу раз со списком. Ну, к примеру, как ползунок на календаре будет работать, только из 5 ячеек.
  29  Егоров Илья Валерьевич, 11 апреля 2018 г. 14:56:05
     По-хорошему, видимо, не следует на Python сохранять всю строку (иначе упирается в память). На уме пока что 3 варианта: 1) Считывать посимвольно (хранить только 1 символ); 2) Считывать частями (своим буфером); 3) Считывать токенами. Представляю лишь реализацию через ctypes, но пока что TLE на 48
  30  Генералов Кирилл Витальевич, 10 апреля 2018 г. 18:47:43
     Да, Вы не ошиблись, именно .split(). Таким образом, нужно строку чисел посимвольно вбивать в список? Вручную,а не функцией?
  31  Егоров Илья Валерьевич, 08 апреля 2018 г. 12:17:29
     Кирилл, вы наверняка используете split, да? Так вот, по сравнению с просто считыванием всего файла (и дальнейшим использованием регулярок или посимвольной обработки) это сугубо в 2 раза больше потребляет память: как ни как, сначала считали строку, а затем разбили на подстроки, и всё это вынуждено храниться в памяти
  32  Генералов Кирилл Витальевич, 07 апреля 2018 г. 13:53:55
     Админ, что за веселье? :D. Вроде бы Питон и не может испытывать проблем из - за типов (int/int64), тогда почему у меня с 47 теста на 48 память прыгает с 2,5+-мб до 38мб. Что я делаю не так в этой жизни? Спасибо.
  33  Харченко Кирилл Константинович, 29 марта 2018 г. 21:41:32
     Одна из самых проблемных задач на сайте. Даже самая оптимизированная программа может не пройти по времени из-за загруженности системы. На личном компьютере результат равняется половины секунды, а здесь ставит 1.03 Но тем не менее, Accepted Ещё одна проблемная - задача №20 - Пилообразная последовательность.
     Попробуйте освоить чтение через fread, о котором говорит автор ниже. Зайдёт быстрее чем за десятую долю секунды. А вообще stdio.h + scanf("%d" хватает, чтобы сдать не совсем вплотную к ограничению по времени.
  34  Егоров Илья Валерьевич, 28 марта 2018 г. 17:34:53
     Комментарий к комментарию: Да, не идеальны. Тем не менее, статистика (не пара решений, а целое множество) обычно показывает действительность (колебание в пределах таких-то значений). У меня не одна !сотня! отправлений - ни одного 0.03. И всё оптимизируя да оптимизируя (уже почти некуда, подумываю об ассемблерных вставках), я улучшаю статистику. Раньше у меня, например, почти не было 0.062 - минимум 0.092. Теперь же 0.062 попадается значительно чаще
  35  Егоров Илья Валерьевич, 28 марта 2018 г. 17:13:11
     [продолжение] с оптимизацией 9) Если не уверены с выбором компилятора в тестирующей системе, опробуйте Visual C++. Ходят слухи, что он тут и жрёт меньше (доказано), и генерирует более эффективный код (под сомнением) 10) Указатели не панацея, бит'цы тоже. Их использование не ускорит магическим образом вашу программу: помните, что они могут сделать даже хуже; Эти рекомендации также годны для тех, кто не стремится выжать все соки, а у кого всего лишь с корректным алгоритмом не проходит по времени / памяти. Ну и добавочно для таких: 1) Если используете <iostream>, лучше всего отключить синхронизацию и автоматический flush, добавив эти 2 "магические строчки" в начало main: ios_base::sync_with_stdio(false); cin.tie(NULL); На данный момент мой рекорд для данной задачи - 0.062 сек. с 176 Кб потребления памяти при компиляторе Visual C++, но цель, ради которой я продолжаю оптимизацию, - 0.03; P.s. Да, я знаю, что лучшим решением тут считается кротчайшее решение, но мало ли кто тут бродит
     Замеры времени на acmp не идеальны, можете попробовать несколько раз сдать одно решение, может повезёт и 0.062 превратится в 0.03.
  36  Егоров Илья Валерьевич, 28 марта 2018 г. 17:12:47
     [продолжение], в собственной реализации парсинга). Причина: есть некий "модуль предсказания переходов", который, если не угадывает путь ветвления, отменяет инструкции, которые он заготовил для своей предсказанной версии, и загружает уже подходящие, на что тратит значительное (относительно) время. Замечание: см. пункт 7 6.1) Вычисление всяких == и т.п. не требует предсказателя (a == b, собственно, то же самое, что !(a ^ b)), так что этим можно воспользоваться для избавления от ветвления 7) Опираясь на пункт 0, замерять время работы после изменений (сугубо раз 7 хотя бы, т.к. из-за ветвления время получается разным: предсказатель то угадывает, то нет). Например, реализовав max через битовые операции, вы можете только ухудшить эффективность программы 7.1) Научитесь изучать получаемый ассемблерный код (хотя б на кол-во инструкций внимание обратите). Достаточно вбить в поисковик "compile explorer". Так вы можете провести достаточно тонкую оптимизацию 8) Вооружитесь const и static. Этим вы поможете компилятору
  37  Егоров Илья Валерьевич, 28 марта 2018 г. 17:11:40
     -Для гиков и не только- Как достичь наилучших результатов по времени и памяти на C++: 0) Тестировать у себя (этак при N = 10^7). Проще всего под unix, используя time 1) Алгоритм за O(n) 2) Достаточно хранить, как проспойлерили ранее, только 5 чисел из последовательности 3) fread/fgets (<stdio.h>) (да, он быстрее всяких getchar) со своим парсингом. Можно и _unlocked/_nolock версию. При этом надо подобрать оптимальный размер буфера (желательно равный 2 в некой степени) 3.1) Знание Великого ASCII поможет в создании быстрого парсинга 4) Реализация своего буферизированного вывода может ухудшить ситуацию, поэтому лучше воспользоваться старым-добрым (f)printf (тот же <stdio.h>) 5) Использовать int и, при необходимости, его аналоги фиксированного размера (int64 и т.п.), но не long long. Помните, что лучше максимум операций производить именно над int, так как меньшие типы в случае арифметических операций всё равно приводятся к int, да и в случае бОльших тоже не так всё радужно 6) Избегать ветвления (например
  38  Завгородний Михаил Сергеевич, 23 февраля 2018 г. 7:12:37
     Хорошая задача. Наконец-то ее решил
  39  Юсупов Темиржан Нурланович, 11 марта 2017 г. 9:24:24
     Библиотека <stdio.h> видимо работает быстрее всех остальных, попробуйте ее
  40  Давид Нигматуллин, 04 марта 2017 г. 11:15:44
     48 тест:
1) Замените лонги на инты там, где можно
2) Замените iostream (cin, cout) на stdio.h (scanf, printf)
1 пункт, лонги менять не нужно, так как в С++, long == int, а вот long long и __int64, да, где можно замените на int
 1 2 3

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru