machine | author | commit | commit date | platform | time | checksum | check | rel time | bonus |
---|
The input consists of an ordered sequence idata
with isize
elements and an unordered sequence odata
with osize
elements.
The assignment is to distribute the odata
into (isize+1)
buckets, whose border values are defined by idata
.
In the bucket number k
, elements are greater or equal to idata[k-1]
and less than idata[k]
.
bsearch_inner
is intended to hold a searching structure,
containing data copied from idata
.typedef std::int32_t data_element; template< typename policy> class bsearch_inner { public: bsearch_inner( const data_element * idata, std::size_t isize); };
bsearch_outer
serves as a buffer for the storage of intermediate and final results.bucketize(odata)
performs the distribution to buckets as described above. This is the
function whose run-time is measured.bucketize
, a call to bucket(k)
returns a reference to the data of the
bucket number k
.
bucket
shall return in constant time.bucketize
overwrite the previous results;
any references returned from the preceding calls to bucket(k)
are no longer valid.bucketize(odata)
use the same number of elements (osize
),
specified previously in the constructor call.bucketize
or bucket
.bsearch_outer
;
all these instances are linked to the same instance of bsearch_inner
.template< typename policy> class bsearch_outer { public: bsearch_outer( const bsearch_inner< policy> & inner, std::size_t osize); void bucketize( const data_element * odata); typedef std::pair< const data_element *, std::size_t> bucket_rv; bucket_rv bucket( std::size_t k) const; };
isize and osize parameters are explained above. isize is iterated through the set { 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576 }, osize through the set { 1024, 16384, 262144 }, resulting in 24 test configurations on each platform. In Debug mode, only 6 of them are used.
repeats is an auto-adjusted parameter, used to increase running time by repeatedly calling compute. The range of the parameter is set so that the expected run time ranges from fractions of a second to seconds (stopped by the auto-adjustment mechanism after exceeding a second).