#include <benchmark/benchmark.h>
#include <vector>
#include <random>
using namespace std;
static void sequentialLoop ( benchmark:: State & state) {
int n = state.range ( 0 ) ;
vector< int > v( n) , ord( n) ;
iota( ord.begin ( ) , ord.end ( ) , 0 ) ;
for ( auto _ : state) {
for ( int i = 0 ; i < n; i++ ) v[ ord[ i] ] = ord[ i] ;
benchmark:: DoNotOptimize ( v.data ( ) ) ;
benchmark:: ClobberMemory ( ) ;
}
}
BENCHMARK( sequentialLoop) - > RangeMultiplier( 2 ) - > Range( 1 << 4 , 1 << 24 ) ;
static void randomizedLoop ( benchmark:: State & state) {
int n = state.range ( 0 ) ;
vector< int > v( n) , ord( n) ;
iota( ord.begin ( ) , ord.end ( ) , 0 ) ;
shuffle( ord.begin ( ) , ord.end ( ) , mt19937( 21 ) ) ;
for ( auto _ : state) {
for ( int i = 0 ; i < n; i++ ) v[ ord[ i] ] = ord[ i] ;
benchmark:: DoNotOptimize ( v.data ( ) ) ;
benchmark:: ClobberMemory ( ) ;
}
}
BENCHMARK( randomizedLoop) - > RangeMultiplier( 2 ) - > Range( 1 << 4 , 1 << 24 ) ;
BENCHMARK_MAIN( ) ;
I2luY2x1ZGUgPGJlbmNobWFyay9iZW5jaG1hcmsuaD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHJhbmRvbT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdGF0aWMgdm9pZCBzZXF1ZW50aWFsTG9vcCAoYmVuY2htYXJrOjpTdGF0ZSYgc3RhdGUpIHsKICAgIGludCBuID0gc3RhdGUucmFuZ2UoMCk7CiAgICB2ZWN0b3I8aW50PiB2KG4pLCBvcmQobik7CiAgICBpb3RhKG9yZC5iZWdpbigpLCBvcmQuZW5kKCksIDApOwoKICAgIGZvciAoYXV0byBfIDogc3RhdGUpIHsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgdltvcmRbaV1dID0gb3JkW2ldOwogICAgICAgIGJlbmNobWFyazo6RG9Ob3RPcHRpbWl6ZSh2LmRhdGEoKSk7CiAgICAgICAgYmVuY2htYXJrOjpDbG9iYmVyTWVtb3J5KCk7CiAgICB9Cn0KQkVOQ0hNQVJLKHNlcXVlbnRpYWxMb29wKS0+UmFuZ2VNdWx0aXBsaWVyKDIpLT5SYW5nZSgxIDw8IDQsIDEgPDwgMjQpOwoKc3RhdGljIHZvaWQgcmFuZG9taXplZExvb3AgKGJlbmNobWFyazo6U3RhdGUmIHN0YXRlKSB7CiAgICBpbnQgbiA9IHN0YXRlLnJhbmdlKDApOwogICAgdmVjdG9yPGludD4gdihuKSwgb3JkKG4pOwogICAgaW90YShvcmQuYmVnaW4oKSwgb3JkLmVuZCgpLCAwKTsKICAgIHNodWZmbGUob3JkLmJlZ2luKCksIG9yZC5lbmQoKSwgbXQxOTkzNygyMSkpOwoKICAgIGZvciAoYXV0byBfIDogc3RhdGUpIHsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgdltvcmRbaV1dID0gb3JkW2ldOwogICAgICAgIGJlbmNobWFyazo6RG9Ob3RPcHRpbWl6ZSh2LmRhdGEoKSk7CiAgICAgICAgYmVuY2htYXJrOjpDbG9iYmVyTWVtb3J5KCk7CiAgICB9Cn0KQkVOQ0hNQVJLKHJhbmRvbWl6ZWRMb29wKS0+UmFuZ2VNdWx0aXBsaWVyKDIpLT5SYW5nZSgxIDw8IDQsIDEgPDwgMjQpOwoKQkVOQ0hNQVJLX01BSU4oKTs=