Есть несколько улучшений, которые вы можете внести в ваш текущий алгоритм, например, прямое удаление символов без сохранения '$' в качестве заполнителя. например, сделайте один проход удаления пары на месте (как ваша вторая версия, но не останавливаясь после первой пары), затем повторяйте, пока длина не перестанет меняться. (В al oop вместо хвостовой рекурсии).
Но на самом деле другой алгоритм имеет гораздо больше смысла.
Это возможно на месте (O (1) хранилище ), за один проход (O (n) время) с низкими постоянными коэффициентами , вероятно, порядка пары-нескольких тактов на байт при компиляции для современной x86. Неправильное прогнозирование ветвей - это, вероятно, самая большая переменная.
Похоже, это связано с существующей проблемой в сети. https://www.hackerearth.com/practice/data-structures/stacks/basics-of-stacks/practice-problems/algorithm/super-reduced-strings-303701dd/. Вы можете посмотреть на существующие решения, такие как https://www.hackerearth.com/submission/35083740/ (и увидеть, что многие из них закодированы как дерьмо, с глобальными переменными и однобуквенными именами переменных, и i < strlen(s), который повторно запускает strlen при каждой итерации. ) Но фактический алгоритм из 2, на который я смотрел, был хорош (кроме strlen в l oop, делающем его O (n ^ 2), и подтвердил мою идею, что было бы возможно сделать это за один проход, если вы Если вы сможете откатиться назад после свертывания серии пар, вы создадите новую пару между нечетными буквами до и после пробела, то есть вы можете go вернуться назад и снова посмотреть на буквы, которые должны были быть частью вывода.
Моя версия оптимизирована для входов, которые могут содержать 3 или более одинаковых символа, а не только разбросанные пары, но в этом случае тоже хорошо.
Для микрооптимизации убрать проверку на обратное отслеживание от начала строки, фактические строковые данные находятся в буфере, который имеет начальный 0 байт ('\0' символ). Это означает, что нам не нужно проверять * 10 24 * до buf[wpos-1] == c.
На веб-сайте хакерских соревнований / упражнений это заносится в «стек» упражнения. Вы можете думать о позиции записи как о стеке.
// This is my version. Don't submit it as yours on online contests.
// But feel free to use it in anything else. Licence = public domain for the code part of this answer.
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
// first non-match = one past the end of a run
inline size_t find_not(const char *base, size_t pos, char needle) {
while(base[pos] == needle) {
pos++;
}
return pos;
}
static char static_buf[10000002];
int main(int argc, char *argv[])
{
char *buf = static_buf+1;
int infd = 0;
if (argc>1) infd=open(argv[1], O_RDONLY);
//size_t len =
read(infd, buf, sizeof(static_buf) - 4); // FIXME: short read isn't handled
// 1 byte of padding at start with a value that can't appear in strings simplifies backtracking
// I don't think we read past the end; c !=0 so checking for runs of that can't go too far.
//static_buf[0] = 0; // str[-1]
//str[len] = 0;
size_t rpos=0;
while (buf[rpos] && buf[rpos] != buf[rpos+1]) // std::adjacent_find
rpos++;
// read-only until first pair, or end of string. could SIMD this with a byte-shift like palignr to feed pcmpeqb
if (buf[rpos]) {
// we stopped early, on a pair
size_t wpos = rpos; // next write position. prev char = a 0 before the string, or last non-pair
rpos+=2; // read from after the pair
// rpos = find_not(buf, rpos+2, buf[rpos]); // read from after the run
// wpos += (rpos-(wpos+1)) % 2; // odd run length -> keep one, else 0
char c;
while ( (c = buf[rpos]) != 0) {
size_t run_end = find_not(buf, rpos+1, c);
if ((run_end - rpos) % 2) {
// one char left from the read side, cancelling or not with the write side.
if (buf[wpos-1] == c) // the 0 before the start of the string always compares false
--wpos;
else
buf[wpos++] = c;
}
rpos = run_end;
}
buf[wpos] = 0;
} // else we hit a terminating 0 without finding a pair
puts(buf[0] ? buf : "Empty String");
if (infd == 0)
lseek(infd, 0, SEEK_SET); // rewind stdin so another run under perf stat can re-read
}
Предполагать, что один read будет читать все доступные входные данные, не очень хорошая идея. Это не может быть, например, из трубы. Я использовал POSIX read вместо stdio fread, потому что думал, что собираюсь использовать длину вместо вызова strlen. C Функции линейного ввода stdio в основном тупые и не возвращают только что найденную длину строки.
Другая микрооптимизация для G CC будет записывать (run_end - rpos) % 2 как (run_end + rpos) % 2. G CC знает, что unsigned %2 просто берет младший бит, но он не понимает, что когда вы хотите только младший бит, ADD, SUB и XOR (добавление без переноса) все эквивалентны, отличаются только в старших битах, где перенос / заимствование / ничто не распространяется из младших битов. + является коммутативным и может быть реализован на x86 с помощью инструкции LEA для копирования и добавления. В данном конкретном случае происходит сохранение 2 mov инструкций вокруг sub, вместо этого просто выполняется add / and.
( проводник компилятора Godbolt )
Неудивительно, что вывод asm - гнездо ветвления крыс. : / Если бы большие пробеги были ожидаемыми , можно было бы использовать x86 SIMD для сканирования 16 байтов за раз для запуска одного и того же символа. Например, _mm_set1_epi8(c) и _mm_cmpeq_epi8 / _mm_movemask_epi8, чтобы получить битовую маску для сравнения со следующими 16 байтами. Продолжайте, если все, иначе __builtin_ctz(~match_bitmask), чтобы найти первое несоответствие. run_end +=, что.
Я проверил это с входными файлами, загруженными из конкурса, неоднократно объединенными, чтобы сделать один большой файл (используя yes $(<input.txt) | tr -d '\n' | head -c 3000000 > big.txt). Input.txt я тестировал с это один:
kzgnywawwacatvccwcpehkgbizefkstszqobqjephaderkwqviqcmdjuxxqutskmxlljsxccicmcddauhwngklfvbqfonkbktqvogolczxmkehycgrmhygfwjvnxtomcygecnkwqzljqshzlarrxfgyamcpemtsqympmmiyngtioifpemaainhueolkndcguoclnobfidksxyzyvnamtrkhwsjkrqxfakfpmyonjanckthlkpyguyhhtscocumxxbycvkxrtlskzuorgpzeohpxfxgeunjfcfccyibcbynnpdjopbcjuodsjdzocezdymzfjrzezyfnkelrliakfabrungdynzjebuwcrdrtzmdlunaibohg
1067 *
Моя версия согласуется с одним из представленных рабочих конкурсов, хотя я не проверял каждый возможный угловой случай (например, пару или серию из 3 в начале и / или конце).
Это больше, чем в два раза быстрее, чем предполагаемая «лучшая» подача на конкурс , которая все еще O (n), но не на месте, и записана менее эффективно (например, сохранение '\0' в массиве на «pop») , а также с ужасным форматированием и плохим стилем кодирования (глобальные переменные). И это после Я смотрю strlen из l oop для представления Тора 8. Это сделало необычайно медленным, как я убил это после 10 секунд против окончания за ~ 12 миллисекунд для этого 3 МБ ввода.
IDK, как онлайн-судья компилирует и рассчитывает что угодно, но даже оригинальную версию со strlen в l oop (что не по какой-то причине был поднят во время компиляции) не потребовалось ни одного около 0,1 секунды для крошечного 372-байтового ввода, с которым он тестировался. Тем не менее, онлайн-судья утверждает, что время равно 0,101484 se c. ess perf тестирование происходит с гораздо большим вводом, который вы не можете загрузить? ИДК, как никто не представил что-то, что было бы быстрее, чем стрельба в l oop, если только онлайн-тестирование перф тестирования просто не сломано.
В моей версии меньше половины инструкций и циклов, и чуть меньше половины ветви против Thor8, когда скомпилированы с gcc9.2 -O3 и профилированы на моем i7-6700k (Skylake) в perf stat для этого большого ввода). Низкий уровень ошибочного предсказания ветвления (0,58% на моем SKL i7-6700k), потому что вход повторяет один и тот же шаблон каждые 372 байта
Это не очень хороший тест. Я профилирую весь процесс, включая Dynami c, связывающий издержки запуска, и он работает только ~ 10 мс, и я не удосужился контролировать методы ввода-вывода между версиями . Я повторил весь процесс 100 раз, чтобы дать perf stat что-то для усреднения, и чтобы процессор работал с максимальным турбо режимом для большинства циклов. Если бы я больше заботился о точных результатах, а не о приблизительных оценках, я бы повторил это oop. Алгоритм работает на месте, но повторное копирование буфера small между итерациями было бы хорошо.
# mine
$ perf stat -r 100 ./pjc-strpair.gcc-O3 < big.txt >&-
Performance counter stats for './pjc-strpair.gcc-O3' (100 runs):
5.37 msec task-clock # 0.970 CPUs utilized ( +- 0.12% )
0 context-switches # 0.047 K/sec ( +- 17.41% )
0 cpu-migrations # 0.000 K/sec
561 page-faults # 0.104 M/sec ( +- 0.03% )
20,892,724 cycles # 3.893 GHz ( +- 0.07% )
47,546,026 instructions # 2.28 insn per cycle ( +- 0.01% )
12,299,984 branches # 2291.692 M/sec ( +- 0.00% )
70,862 branch-misses # 0.58% of all branches ( +- 0.23% )
0.00553091 +- 0.00000647 seconds time elapsed ( +- 0.12% )
После -fprofile-generate + тренировочного прогона перестройка с -fprofile-use делает его запустить в 3,61 мс. 9,6 млн. Филиалов, процент ошибочных прогнозов 0,17%. 14M циклов, 44,6M инструкций (так что всего инструкций меньше). Использование -fno-pie -no-pie также сокращает до 41,7M инструкций, но экономит менее 1% циклов. (Интересно сократить частоту пропадания веток вдвое, но она уже была достаточно низкой, чтобы не снижать производительность на этих простых данных).
G CC вообще не разворачивает циклы, если вы не используете -fprofile-use, и это, вероятно, помогает G CC лучше планировать ответвления, причем в обычных случаях это может быть провал.
# thor8, "best" submission
$ perf stat -r 100 ./thor-strpair.gcc-O3 < big.txt >&-
Performance counter stats for './thor-strpair.gcc-O3' (100 runs):
12.19 msec task-clock # 0.985 CPUs utilized ( +- 0.24% )
0 context-switches # 0.011 K/sec ( +- 26.00% )
0 cpu-migrations # 0.000 K/sec
1,120 page-faults # 0.092 M/sec ( +- 2.19% )
47,525,048 cycles # 3.898 GHz ( +- 0.24% )
125,445,423 instructions # 2.64 insn per cycle ( +- 0.08% )
28,943,829 branches # 2374.152 M/sec ( +- 0.07% )
110,100 branch-misses # 0.38% of all branches ( +- 0.14% )
0.0123707 +- 0.0000296 seconds time elapsed ( +- 0.24% )
Обратите внимание, что количество сбоев страниц в два раза больше, чем касание ОЗУ в два раза.
-fprofile-generate / use только ускоряет его до 11,21 мс, но, как и в моей версии, промахи в ветках сильно упали. Согласно perf record / report, 41% его времени тратится внутри __vfscanf_internal, поэтому большая часть разницы составляет в затратах ввода-вывода, а не в алгоритме. против 23% в main (большая часть остального в ядре для ошибок страниц. Когда даже менее эффективная версия алгоритма работает быстрее, чем scanf, это довольно хороший признак того, что он достаточно эффективен. Но вы спросил о микрооптимизации и оптимизации.
Мне пришлось добавить rewind(stdin) к версии Thor8 (и lseek к моей версии), в противном случае последующие запуски под perf stat -r100 приведут к пустому stdin!
В этом случае больше инструкций за цикл означает, что он выполнил ту же самую реальную работу с большим количеством инструкций, и лучший прогноз ветвления скорость состоит в том, что он выполнял больше полных ветвей, некоторые из них полностью предсказуемы как top!=-1 часть одного условия l oop.
G CC выполняет встроенные вызовы функций и оптимизирует глобальные переменные в регистры для версии Thor8, но все еще есть некоторое расширение знака от 32-разрядного int со знаком до 64-разрядной ширины указателя, так как я компилировал для x86- 64.
Я предполагаю, что большинство времени выполнения исходит от фактического l oop, хотя stdio scanf должен искать границу слова, тогда как read просто memcpy (внутри ядра). Тем не менее, реальные программы должны выполнять ввод / вывод, и моя версия оптимизирована на основе того факта, что мы все равно должны читать ввод из stdin, а не из буфера ввода, так что наличие ведущей * 1136 ничего не стоит * в массиве и прочитайте его после этого.
Реализация этого в идиоматизме c C ++ оставлена в качестве упражнения для читателя . В C ++ нет find_not, поэтому вы можете использовать мою версию или использовать std::find_if_not или std::find_if с лямбда-выражением в качестве предиката.
Существует std::adjacent_find, который может реализовать только для чтения l oop, который останавливается на первом дубликате.
Избегать копирования при чтении в std::string или vector<char> с добавленным байтом 0 может быть проблемой. Строки неявной длины, кажется, полезны для этой задачи, потому что поиск соответствия для известного не-NUL c также говорит вам, что символ, который вы только что посмотрели, не является NUL. Так что вам также не нужно проверять длину. Конечно, это всего лишь незначительный постоянный фактор, чтобы добавить дополнительную проверку к al oop, но все равно O (n) время выполнения.