Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #82509

Re: binary_search accoring to its name

Show all headers | View raw

This is a small benchmark:

	auto bench = [&]<typename SearchFn>( SearchFn searchFn ) -> double
		requires requires( SearchFn searchFn, vsv_it iterator, string_view 
const &key )
		{
			{ searchFn( iterator, iterator, key ) } -> convertible_to<vsv_it>;
		}
	{
		size_t sumExist = 0;
		auto start = high_resolution_clock::now();
		for( size_t it = ITERATIONS; it; --it )
			sumExist += searchFn( strings.begin(), strings.end(), 
strings[uidIndex( mt )] ) != strings.end();
		double ns = (double)(int64_t)duration_cast<nanoseconds>( 
high_resolution_clock::now() - start ).count() / ITERATIONS;
		aSumExist += sumExist;
		return ns;
	};
	double lb = bench( []( vsv_it begin, vsv_it end, string_view const &key 
) -> vsv_it
		{
			vsv_it it = lower_bound( begin, end, key );
			if( it == end && *it != key )
				return end;
			return it;
		} );
	cout << "lb: " << lb << endl;
	double xlb = bench( []( vsv_it begin, vsv_it end, string_view const 
&key ) -> vsv_it
		{
			vsv_it it = xlower_bound( begin, end, key,
				[]( string_view &elem, string_view const &key ) -> strong_ordering { 
return elem <=> key; } );
			if( it == end && *it != key )
				return end;
			return it;
		} );
	cout << "xlb: " << xlb << endl;
	double xbs = bench( []( vsv_it begin, vsv_it end, string_view const &key )
		{
			return xbinary_search( begin, end, key,
				[]( string_view &elem, string_view const &key ) -> strong_ordering { 
return elem <=> key; } );
		} );
	cout << "xbs: " << xbs << endl;

vsv_it is vector<string_view>::iterator

144,420,73 sorted string_view items, avgerage length: 8.68825 characters
lower_bound: 1835.47ns
xlower_bound: 1741.33ns
xbinary_search: 1845.06

I think with such a large dataset the time isn't decided upon the
algorithm but upon the random memory-accesses.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-27 15:38 +0100
  Re: binary_search accoring to its name Marcel Mueller <news.5.maazl@spamgourmet.org> - 2021-11-28 12:27 +0100
    Re: binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-28 17:03 +0100
    Re: binary_search accoring to its name Juha Nieminen <nospam@thanks.invalid> - 2021-11-29 05:57 +0000
      Re: binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-29 08:26 +0100
        Re: binary_search accoring to its name Bonita Montero <Bonita.Montero@gmail.com> - 2021-11-29 14:02 +0100

csiph-web