|
|
|
|
|
|
|
Вернуться
| 21 Егоров Илья Валерьевич, 15 сентября 2020 г. 3:04:16 | |
|
...тора неровностей за O(1), о которых мною сказано ранее.
|
|
|
| 22 Егоров Илья Валерьевич, 15 сентября 2020 г. 3:04:01 | |
Пожалуй, не буду ждать и прямо отвечу на вопрос. Как я полагаю, основная причина кроется в передаче по значению vector<int>. Покажу на простом примере (где ~~ обозначает 1 отступ):
#include <vector>
static void test(std::vector<int> a) {
~~// none
}
int main() {
~~const int N = 100000;
~~
~~std::vector<int> a(N);
~~
~~for (int i = 0; i < N; i += 1) {
~~~~test(a);
~~}
}
Как может показаться на первый взгляд, этот код ничего не делает. На самом деле это не так: тут N раз забавы ради копируется вектор с N нулями, поскольку передается он по значению. В силу сохранения побочных эффектов (злейшего врага ряда разработчиков) компилятор не может отбросить такое даже на -O3, а уж с -O2 и остальным вагоном указанных в "Работа в системе" параметров выдает в godbolt полноценные 87 строк ассемблера.
Возьмем упрощенную модель: инициализация памяти, равно как и копирование, по сложности составляет O(n), что образно похоже на простой поэлементный форик. Это не далеко от истины, даже если предположить возможные оптимизации со стороны стандартной библиотеки. Итак, вместе с последним фориком принимаем асимптотическую сложность приведенного кода равной O(n^2). На моей машине выполняется такой код за условные ~1.333 сек.
Что будет, если заменить передачу по значению на передачу по ссылке (приписать &)? А вот что: компилятор возьмет да спокойно отбросит и функцию, и сам форик, оставив только инициализацию памяти для вектора. В предыдущем абзаце она была упомянута не просто так: компилятор не может просто взять и выбросить вектор. В конструкторе вектора происходит явный вызов memset, что и проглядывается в получаемом выхлопе на ассемблере в 14 строк. Указанную сложность также приводит cppreference. Получаем O(n), что выполняется менее чем за сотую долю секунды и превышает секунду лишь с добавлением к N аж 4 нулей.
Вывод: вместо ожидаемого вами O(nlogn) ваше решение, благодаря копированию вектора, получилось за квадрат, к чему также приплелись отягчающие обстоятельства в виде небольших неудобных для компиля
|
|
|
| 23 Егоров Илья Валерьевич, 15 сентября 2020 г. 0:47:14 | |
|
Вдобавок скажу, что если нет определенных навыков и/или понимания "что есть излишний функционал в стандартных функциях и как таковой спилить", то предпочтительно использовать упомянутые стандартные функции, да структуры данных подбирать с умом. Если, конечно, не созрела кристально чистая мысль наточить свое мастерство, даб стать способным писать действительно эффективные решения. Как ни как, незначительные детали тоже влияют на итоговую асимптотическую сложность (как пример подумайте к чему приводит ваше "vector<int> a" в контексте функции), хоть иногда подобное упускается из виду в силу гипотетической неявности (а на самом деле просто набитости руки с сопутствующим непониманием происходящего) и приводит к таким ситуациям, как почти полная неприменимость комика-змеи в условиях определенных задач.
|
|
|
| 24 Егоров Илья Валерьевич, 15 сентября 2020 г. 0:01:42 | |
|
А тут и нечего удивляться. Передача по значению, чрезмерные вызовы .size(), да и сама функция ни inline, ни static (что в контексте глобальном как правило (но не во всех случаях) эквивалентно по действию inline) — все это несет определенный оверхэд. И что уж говорить о том, что binary_search — функция шаблонная через итераторы, с не самым примитивным алгоритмом, так что компилятором оптимизируется на ура, в то время как ваша реализация даже в банальном построении ветвления проигрывает: нет никакого значимого довода первым проверять a[mid]==x, когда true достигается только в конце алгоритма. Но это лишь догадки, т.к. вашим решением я не располагаю, однако величина разницы вполне реальная: в моем любимом 224 не совсем банальная оптимизация ввода-вывода ускоряет решение за постоянное O(n) в ~33 раза. Хотите докопаться до истины — лучше сами проверьте, пробуя менять узкое место своего кода.
|
|
|
| 25 Зараник Богдан Юрьевич, 14 сентября 2020 г. 21:52:46 | |
|
За счёт чего ТАКОЙ выигрыш по времени? Ну я ещё поверил, если бы было 0,842 vs 0.65. НО в 28 раз!
|
|
|
| 26 Зараник Богдан Юрьевич, 14 сентября 2020 г. 21:44:18 | |
Ребята, вопросик такой: написал задачу 638. O(nlogn). Если кто знает, как решить за О(n), намекните плиз). Но я не за то спрашиваю. Написал бинпоиск (вполне нормальный)
bool bs(vector<int> a, int x){
if(a.size()==0)return 0;
int l=0, r=a.size()-1, mid;
while(r-l>1){
mid=(l+r)/2;
if(a[mid]==x)return 1;
else if(a[mid]>x)r=mid;
else l=mid;
}
return (a[r]==x || a[l]==x);
}
Вся программа работает за 0,842.
Написал с binarysearch(встроенный) - 0.03!!!!
Вопрос один: как такое может быть?
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
