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

1. Вставка и удаление в vector (и операции с памятью вроде memcpy и memmove)

Пусть у нас есть изначально пустой vector v и мы 10^5 раз вызовем v.insert(v.begin(), rand()). По cppreference.com каждая такая вставка требует O(n) времени, т.е. получаем 10^10 операций, не с точностью до константы. Но замерим время на практике: ideone. На ideone это занимает 650 мс, на Codeforces 1500 мс, но в любом случае, это не похоже на обычные 10^10 операций. Также, часто в задачах на строки участники что-то делают с ними за квадрат, и это тоже иногда заходит (при n = 1e5 или даже 3e5).

2. Деление чисел с плавающей точкой

Интуитивно кажется, что деление int на int должно быть быстрее double на double, а тем более long double на long double. И на некотрых серверах (ideone, например) это действительно так. Но не на всех. Возьмём для теста два кода: целые числа и с плавающей запятой. Запуск на C++14 даёт 220 мс для первого и 130 мс для второго. Более того, long double на Codeforces тоже отработал за 130 мс, хотя long double содержит в себе не только все значения int, но и long long.

3. sqrt(double) и sqrt(long double)

Опять же, логично предположить, что sqrt(double) должен быть быстрее, т.к. double и пямяти занимает меньше, и точность меньше. На Codeforces они работают примерно одинаково. Но на ideone sqrt(long double) оказался быстрее.

4. pow

Мне казалось, что pow работает за O(1). Но, как оказалось pow(x, 1) и pow(x, 2) заметно быстрее pow(x, произвольный double) и даже pow(x, другие целые). Ну и чуть более понятный факт: pow(x, 0.5) заметно дольше sqrt(x).

5. floor(x) и int(x)

Для double int работает в 2 и более раз быстрее floor. Для long double наоборот.

Пишите в комментариях интересные факты, известные вам и не названные здесь, желательно тоже с кодом-бенчмарком.

Задача

Дан массив a из N целых чисел. Для каждого из них надо найти ближайшее большее слева.

Алгоритм со стеком

Будем считать ответы по порядку, слева направо. Поддерживаем стек. Для каждого элемента удаляем из стека все элементы меньшие или равные ему. Затем, если стек не пуст, ответом для текущей позиции будет элемент на вершине стека. Добавляем текущее число в стек.

Алгоритм без стека

Заметим, что ответы для предыдущих чисел полностью задают стек. Уберём его.

Профит

• Памяти стало в 2 раза меньше.
• Время уменьшилось на 20% (по данным Ideone.com).
• Кода тоже стало меньше.

Код обеих версий

const int N = 4e7;
int a[N];
int link[N];
int stack[N];
int ptr = 0;
 
void with_stack() {
	fill_n(link, N, -1);
	for (int i = 0; i < N; ++i) {
		while (ptr > 0 && a[stack[ptr - 1]] <= a[i]) {
			--ptr;
		}
		if (ptr) {
			link[i] = stack[ptr - 1];
		}
		stack[ptr++] = i;
	}
}
 
void without_stack() {
	for (int i = 0; i < N; ++i) {
		int &l = link[i];
		l = i - 1;
		while (l >= 0 && a[l] <= a[i]) {
			l = link[l];
		}
	}		
}

Этот же код на Ideone (можно раскомментировать вызов одной из функций и посмотреть время работы)