С++ в относительно новых стандартах

Вопросы написания собственного программного кода (на любых языках)

Модератор: Olej

Аватара пользователя
Olej
Писатель
Сообщения: 14426
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: С++ в относительно новых стандартах

Непрочитанное сообщение Olej » 16 фев 2021, 09:41

Olej писал(а):
15 фев 2021, 16:16
Ещё раз о множествах и совместимости стандартов тоже...
И ещё раз о множествах...
В сети на удивление много обсуждений "что будет быстрее искать count или find" :lol: ... и "на хлопський розум" обсужданты приходят к выводу:
- что якобы find будет быстрее, потому как если найдёт, то сразу возвратится...
- а count должен будет искать до конца.
P.S. И тема, откровенно говоря, выросла из того, что ... мой нынешний работодатель указал на мой код: "а вот find был бы намного быстрее, чем count, да и логику происходящего лучше раскрывает" :lol:

Рассуждения принципиально неверные в корне:
- set - не линейная структура, это хэш-таблица, только в которой ключи совпадают со значениями;
- там просто нет никакого "конца" - поиск в шэш-таблице делается нелинейно, могут использоваться в реализации разные алгоритмы;
- после нахождения в count элемента, зная что это set, множество, и count не может быть >1 - нужно сразу прекращать поиск ... и реализаторы не могут этого не учитывать.

Но интересно это проверить ... а заодно сравнить время поиска с аналогичным поиском в линейной структуре ... вектор - как простейший прототип. И, очевидно, что время поиска будет сильно различаться для наличия искомого элемента и его полного отсутствия.
Итак:

Код: Выделить всё

#include <iostream>
#include <set>
#include <vector>
#include <chrono>

int main(int argc, char *argv[])
{
	unsigned long num = (argc > 1 && atol( argv[1] ) > 0) ?
	                    atol(argv[1]) : 10000;

	std::set<unsigned long> exs;
	std::vector<unsigned long> exv;

	for(unsigned long i = 0; i < num; i++ )
	{
		exs.insert( i );
		exv.push_back( i );
	}

	auto testv = [](std::vector<unsigned long> &v, unsigned long n)->void { find(v.begin(), v.end(), n); };
	for(unsigned long m: {num / 2, num + 1})
	{
			auto tbegin = std::chrono::steady_clock::now();
			testv(exv, m);
			auto tend = std::chrono::steady_clock::now();
			auto dur = std::chrono::duration_cast<std::chrono::nanoseconds>(tend - tbegin);
			std::cout << "elapsed time = " << dur.count() << std::endl;
	}

	void (*tests[])(std::set<unsigned long>&, unsigned long) = {
		[](std::set<unsigned long> &s, unsigned long n)->void { s.find(n); },
		[](std::set<unsigned long> &s, unsigned long n)->void { s.count(n); },
		[](std::set<unsigned long> &s, unsigned long n)->void { s.contains(n); } 
	};
	for(size_t i = 0; i < sizeof(tests) / sizeof(tests[0]); i++ )
		for(unsigned long m: {num / 2, num + 1})
		{
			auto tbegin = std::chrono::steady_clock::now();
			tests[i](exs, m);
			auto tend = std::chrono::steady_clock::now();
			auto dur = std::chrono::duration_cast<std::chrono::nanoseconds>(tend - tbegin);
			std::cout << "elapsed time = " << dur.count() << std::endl;
		}
}
Вложения
set4.cc
(1.42 КБ) 11 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 14426
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: С++ в относительно новых стандартах

Непрочитанное сообщение Olej » 16 фев 2021, 09:55

Olej писал(а):
16 фев 2021, 09:41
Итак:

Код: Выделить всё

olej@nvme:~/2021/OWN_TEST.codes/set$ make
g++ -Wall -pedantic -std=c++2a set4.cc -o set4
Как уже говорилось, опция стандарта -std=c++2a - обязательна!
Выполняем:

Код: Выделить всё

olej@nvme:~/2021/OWN_TEST.codes/set$ ./set4 1000000
elapsed time = 3400469
elapsed time = 6800886
elapsed time = 2911
elapsed time = 3481
elapsed time = 1186
elapsed time = 952
elapsed time = 748
elapsed time = 842
:-o :shock:
Результаты изумляют:
- поиск в set на 3-4 порядка быстрее чем в vector;
- в vector нет метода find(), поэтому используем алгоритм find();
- для set используем его родные методы;
- самый длинный способ поиска - метод find();
- метод count(), вопреки злым языкам, в 2-3 раза быстрее;
- а ново введенный в стандарт метод contains() - ещё на 20-30% быстрее;

Аватара пользователя
Olej
Писатель
Сообщения: 14426
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: С++ в относительно новых стандартах

Непрочитанное сообщение Olej » 17 фев 2021, 23:10

Маленькое лирическое отступление... :
Зачем это я сделал такую тему со странным названием "С++ в относительно новых стандартах" - тема не о чём, всё свалено в кучу... :-?

А вот зачем:
- во первых, это для меня испытательная площадка, где я испытываю те или иные конструкции, которые я предположил использовать в крупном реальном проекте, в котором участвую...
- а во-вторых, в C++11, C++14, C++17, C++20, C++23 ... и далее - ввели очень много замечательных нововведений ... а ещё больше (~60-70%) - непотребной шелупени - у угоду пожеланиям IT супер-корпорациям...
- так вот в такой теме я для себя, любимого, вычленяю: что есть находки, и что есть шелупень (IMHO, разумеется);
- а все фрагменты здесь, которые мне покажутся стоящими - позже разовьются просто в отдельные самостоятельные темы в этом нашем форуме! :!:

Аватара пользователя
Olej
Писатель
Сообщения: 14426
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: С++ в относительно новых стандартах

Непрочитанное сообщение Olej » 20 фев 2021, 15:17

Следующая часть нашего марлизонского балета: <atomic>, атомарные операции ... это надолго и всерьёз!
Это было написано как следующим сообщением здесь в теме... И это действительно так.
Но это насколько отдельная и объёмная тема, что я их я отнёс в отдельную, уже существовавшую для того, тему: C++: параллельность, асинхронность и атомарность.

Аватара пользователя
Olej
Писатель
Сообщения: 14426
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: С++ в относительно новых стандартах

Непрочитанное сообщение Olej » 22 фев 2021, 02:55

В продолжение ...
Olej писал(а):
08 янв 2021, 21:52
vector<int> v0( limit );
for ( auto& u: v0 )
u = dice();
Olej писал(а):
08 янв 2021, 21:52
vector<int> v2 = v0;
Actor act2;
for( int& i : v2 )
act2( i );
Маленькое замечание, не очевидное, относительно любых конструкций C++11 (и далее) вида: for( auto& ... ) ... мне оно стоили 1/2 дня переделки кода :-( :

Код: Выделить всё

    struct X {...};
    vector<X> v = ...;
    Actor actor(...); // функтор
    for( const auto &x : v )
	actor( x );
- т.е. квалификатор константности const устанавливается и для типа, выводимого из контекста auto (при условии, естественно, что функтор ничего не делает с переданными ему элементами, а только что-то там подсчитывает ;-) ).

А вот в таком варианте:

Код: Выделить всё

    for( const auto x : v )
	actor( x );
- пожалуй, вообще всегда уместно const, поскольку в функтор здесь передаётся копия x.

Аватара пользователя
Olej
Писатель
Сообщения: 14426
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: С++ в относительно новых стандартах

Непрочитанное сообщение Olej » 01 май 2021, 22:56

Olej писал(а):
21 дек 2020, 02:32
Смотрю что там на счёт move семантики в C++11 ...
Углубляемся в C++: move семантика и rvalue
Урок №192. Функция std::move()
Интересное обсуждение относительно return std::move(s) и то, почему для локальных переменных (значений) в большинстве случаев не нужно делать: Надо ли писать return std::move(local_var)? (правило copy elision).

Ответить

Вернуться в «Программирование»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 4 гостя