Я составляю задачу для одной олимпиады, в апреле планируется добавить тренировку в CF по задачам той олимпиады
Допустим, есть строка A = "abc", B = "def". Мне нужно их вывести, чтобы на выходе получить "abcdef". Таких строк может быть до 4 × 106 штук.
Как можно это делать быстро в С++? На Delphi решение тратит 937 мс, на C++ — 1703 мс.
Код Delphi:
write('abc');
write('def');
Код С++:
printf("abc");
printf("def");
Да, это укладывается в установленный TL = 2 секунды. Но хотелось бы быстрее. Можно ли?
UPD: Конкатенировать строки нельзя, задача на технику, ML = 4 МБ, поэтому решение с конкатенацией получает ML.
puts не быстрее?
В С++ я не силён, многого не знаю.
Я пробовал puts, он после каждой строки выводит
\n, а так не надо.Заведи большой буффер. Пихай все в него и потом один раз делай puts. Это очень быстро работает.
Написано же в посте: "UPD: Конкатенировать строки нельзя, задача на технику, ML = 4 МБ, поэтому решение с конкатенацией получает ML."
puts выводит '\n' после окончания строки
Попробуйте fputs(str,stdout)
Попробуйте
fputs("abc", stdout); fputs("def", stdout);Еще вариант:
fputsдал ускорение на 400 мс.myputsдал ускорение на 150 мс.Попробуй в myputs
заменить на банальное
У меня это дало 3-кратное ускорение (не забыть сделать myputs inline — у меня ускорило до 0.204 сек для вывода 4000000 "abc" "def")
Наверное, ты удивишься: с inline получило TL.
P.S. без inline тоже.
Странно. У меня такие результаты:
Естественно, у меня далеко не "abc" и "def", возможно, из-за этого.
fwrite() только хуже сделает, потому что это запись напрямую в буфер ядра ОС, в обход буфферизации в libc
Попробуй собрать все строки в одну большую строковую переменную, а потом выведи printf("%s\n", ans.c_str());
Упс, забыл сказать самое главное. Прочитай UPD в посте.
Что-то не верится, что Delphi такой быстрый. 24 МБ за 0,046 сек даже теоретически не записать на диск. 24 МБ / 0,046 сек ~ 521 МБ/сек ~ 4174 МБит/сек, что на порядок больше даже SSD.
У меня результаты такие:
Да, я не туда посмотрел. В старом комплекте не было больших тестов.
Delphi: 937 мс. С++ (самый быстрый результат — твой
myputs): 1311 мс.Я бы добавил сюда fputs.
Если я правильно понимаю, puts после себя делает fflush, а fputs не делает. Кстати, это правда? :-)
можно попробовать write(1,str,strlen(str)); это низкоуровневый вывод, но немогу точно сказать за сколько выполнется
Смотря где, на то он и низкоуровневый :) Для меня низкоуровневый будет так:
и еще можно вопрос, как проверить скорость работы программы?
Тыц
По этой теме есть ещё вот такой пост: http://codeforces.com/blog/entry/562
Надо туда добавить
myputsот yeputons :)ML = 4 МБ — не лучшее решение для тренировок CF, теперь ее нельзя сдать на Java
Мы делаем не тренировку на CF, а олимпиаду для младших школьников. Первые несколько задач рассчитаны только на технику программирования, поэтому содержат огромное количество всяких специальных случаев и тестов к этим случаям. А потом добавим тренировку на CF.
Да, с Java есть такие проблемы. Но в прототипе правил уже есть пункт о том, что
Жюри гарантирует наличие полного решения на языках программирования Pascal / Delphi и C / C++. Жюри не гарантирует наличие полных решений на других языках программирования.
Я бы все-таки сделал буфер мегабайта на 3, ускориться должно в разы.
Я не знаю какой буфер вы имели ввиду, поэтому уточню : 1. Буфер — массив в коде программы 2. Буфер libc, через setvbuf()
Достаточно символьного массива в коде.