program ideone;
{$mode delphi}
uses SysUtils, Math;
type
TLongWordArr = array of longword;
TCallFunc = function ( constref arr: TLongWordArr) : longword;
function ArrNzItCnt( constref arr: TLongWordArr) : longword;
var
i: integer ;
begin
Result: = 0 ;
for i: = 0 to Length( arr) - 1 do
if arr[ i] <>0 then
Inc( Result) ;
end ;
const
MAXDWORD = $FFFFFFFF ;
function ArrNzItCnt2( constref arr: TLongWordArr) : longword;
var
n, m: longword;
i : integer ;
begin
Result: = 0 ;
n : = 1 + Trunc( ln ( Double( MAXDWORD) ) / ln ( 2 ) ) ;
m : = 1 <<n- 1 ;
for i: = 0 to Length( arr) - 1 do
Inc( Result, ( arr[ i] + m) >>n) ;
end ;
function ArrNzItCntBoolcast( constref arr: TLongWordArr) : longword;
var
i: integer ;
begin
Result: = 0 ;
for i: = 0 to Length( arr) - 1 do
Inc( Result, Ord ( arr[ i] <>0 ) ) ;
end ;
const
TestSize = 10000000 ;
func_call : array [ 0 .. 2 ] of record
name : string ;
func : TCallFunc;
end = (
( name : 'Normal' ; func: ArrNzItCnt )
, ( name : 'Math' ; func: ArrNzItCnt2 )
, ( name : 'Boolcast' ; func: ArrNzItCntBoolcast )
// add more functions here, if needed
) ;
var
t : Int64;
i, j : integer ;
arr_test: TLongWordArr;
ArrCnt : TCallFunc;
nm : string ;
begin
(* your code goes here *)
SetLength( arr_test, TestSize) ;
for j : = low( func_call) to high( func_call) do
begin
ArrCnt : = func_call[ j] . func ;
nm : = func_call[ j] . name ;
for i: = 0 to length( arr_test) - 1 do arr_test[ i] : = 0 ;
t: = GetTickCount64;
ArrCnt( arr_test) ;
t: = GetTickCount64- t;
writeln ( nm, ' Test 1: ' , t, 'ms' ) ;
for i: = 0 to length( arr_test) - 1 do arr_test[ i] : = 1 ;
t: = GetTickCount64;
ArrCnt( arr_test) ;
t: = GetTickCount64- t;
writeln ( nm, ' Test 2: ' , t, 'ms' ) ;
for i: = 0 to length( arr_test) - 1 do arr_test[ i] : = Random( 2 ) ;
t: = GetTickCount64;
ArrCnt( arr_test) ;
t: = GetTickCount64- t;
writeln ( nm, ' Test 3: ' , t, 'ms' ) ;
for i: = 0 to length( arr_test) div 2 - 1 do
arr_test[ 2 * i+ 0 ] : = 1 ;
for i: = 0 to length( arr_test) div 2 - 1 do
arr_test[ 2 * i+ 1 ] : = 0 ;
t: = GetTickCount64;
ArrCnt( arr_test) ;
t: = GetTickCount64- t;
writeln ( nm, ' Test 4: ' , t, 'ms' ) ;
for i: = 0 to length( arr_test) div 2 - 1 do
arr_test[ 2 * i+ 0 ] : = 0 ;
for i: = 0 to length( arr_test) div 2 - 1 do
arr_test[ 2 * i+ 1 ] : = 1 ;
t: = GetTickCount64;
ArrCnt( arr_test) ;
t: = GetTickCount64- t;
writeln ( nm, ' Test 5: ' , t, 'ms' ) ;
end ;
end .
cHJvZ3JhbSBpZGVvbmU7CnskbW9kZSBkZWxwaGl9CnVzZXMgU3lzVXRpbHMsIE1hdGg7Cgp0eXBlCiAgVExvbmdXb3JkQXJyID0gYXJyYXkgb2YgbG9uZ3dvcmQ7CiAgVENhbGxGdW5jID0gZnVuY3Rpb24oY29uc3RyZWYgYXJyOlRMb25nV29yZEFycik6IGxvbmd3b3JkOwoKZnVuY3Rpb24gQXJyTnpJdENudChjb25zdHJlZiBhcnI6VExvbmdXb3JkQXJyKTogbG9uZ3dvcmQ7CnZhcgogIGk6IGludGVnZXI7CmJlZ2luCiAgUmVzdWx0Oj0wOwogIGZvciBpOj0wIHRvIExlbmd0aChhcnIpLTEgZG8KICAgIGlmIGFycltpXTw+MCB0aGVuCiAgICAgIEluYyhSZXN1bHQpOwplbmQ7Cgpjb25zdCAgIAogIE1BWERXT1JEID0gJEZGRkZGRkZGOyAgCgpmdW5jdGlvbiBBcnJOekl0Q250Mihjb25zdHJlZiBhcnI6VExvbmdXb3JkQXJyKTogbG9uZ3dvcmQ7CnZhcgogIG4sbTogbG9uZ3dvcmQ7CiAgaSAgOiBpbnRlZ2VyOwpiZWdpbgogIFJlc3VsdDo9MDsKICBuICAgICA6PTErVHJ1bmMobG4oRG91YmxlKE1BWERXT1JEKSkvbG4oMikpOyAKICBtICAgICA6PTE8PG4tMTsKICBmb3IgaTo9MCB0byBMZW5ndGgoYXJyKS0xIGRvCiAgICBJbmMoUmVzdWx0LChhcnJbaV0rbSk+Pm4pOwplbmQ7CgpmdW5jdGlvbiBBcnJOekl0Q250Qm9vbGNhc3QoY29uc3RyZWYgYXJyOlRMb25nV29yZEFycik6IGxvbmd3b3JkOwp2YXIKICBpOiBpbnRlZ2VyOwpiZWdpbgogIFJlc3VsdDo9MDsKICBmb3IgaTo9MCB0byBMZW5ndGgoYXJyKS0xIGRvCiAgICBJbmMoUmVzdWx0LCBPcmQoYXJyW2ldPD4wKSk7CmVuZDsKCmNvbnN0CiAgVGVzdFNpemUgPSAxMDAwMDAwMDsKICBmdW5jX2NhbGwgOiBhcnJheSBbMC4uMl0gb2YgcmVjb3JkIAogICAgICAgICAgICAgICAgIG5hbWUgOiBzdHJpbmc7CiAgICAgICAgICAgICAgICAgZnVuYyA6IFRDYWxsRnVuYzsgCiAgICAgICAgICAgICAgZW5kID0gKCAKICAgICAgICAgICAgICAgIChuYW1lOidOb3JtYWwnOyBmdW5jOiBBcnJOekl0Q250ICkKICAgICAgICAgICAgICAgLChuYW1lOidNYXRoJzsgZnVuYzogQXJyTnpJdENudDIgKQogICAgICAgICAgICAgICAsKG5hbWU6J0Jvb2xjYXN0JzsgZnVuYzogQXJyTnpJdENudEJvb2xjYXN0ICkKICAgICAgICAgICAgICAgLy8gYWRkIG1vcmUgZnVuY3Rpb25zIGhlcmUsIGlmIG5lZWRlZAogICAgICAgICAgICAgICk7CnZhcgogIHQgOiBJbnQ2NDsKICBpLCBqIDogaW50ZWdlcjsKICBhcnJfdGVzdDogVExvbmdXb3JkQXJyOwogIEFyckNudCA6IFRDYWxsRnVuYzsKICBubSA6IHN0cmluZzsKYmVnaW4KCSgqIHlvdXIgY29kZSBnb2VzIGhlcmUgKikKICAKICBTZXRMZW5ndGgoYXJyX3Rlc3QsVGVzdFNpemUpOwogIAogIGZvciBqIDo9IGxvdyhmdW5jX2NhbGwpIHRvIGhpZ2goZnVuY19jYWxsKSBkbyAKICBiZWdpbgogCQogCUFyckNudCA6PSBmdW5jX2NhbGxbal0uZnVuYzsKIAlubSA6PSBmdW5jX2NhbGxbal0ubmFtZTsKIAkKICAgIGZvciBpOj0wIHRvIGxlbmd0aChhcnJfdGVzdCktMSBkbyBhcnJfdGVzdFtpXTo9MDsKICAgIHQ6PUdldFRpY2tDb3VudDY0OwkKICAgIEFyckNudChhcnJfdGVzdCk7CiAgICB0Oj1HZXRUaWNrQ291bnQ2NC10OwogICAgd3JpdGVsbihubSwnIFRlc3QgMTogJywgdCwnbXMnKTsKICAKICAgIGZvciBpOj0wIHRvIGxlbmd0aChhcnJfdGVzdCktMSBkbyBhcnJfdGVzdFtpXTo9MTsKICAgIHQ6PUdldFRpY2tDb3VudDY0OwkKICAgIEFyckNudChhcnJfdGVzdCk7CiAgICB0Oj1HZXRUaWNrQ291bnQ2NC10OwogICAgd3JpdGVsbihubSwnIFRlc3QgMjogJywgdCwnbXMnKTsKICAKICAgIGZvciBpOj0wIHRvIGxlbmd0aChhcnJfdGVzdCktMSBkbyBhcnJfdGVzdFtpXTo9UmFuZG9tKDIpOyAgCiAgICB0Oj1HZXRUaWNrQ291bnQ2NDsJCiAgICBBcnJDbnQoYXJyX3Rlc3QpOwogICAgdDo9R2V0VGlja0NvdW50NjQtdDsKICAgIHdyaXRlbG4obm0sJyBUZXN0IDM6ICcsIHQsJ21zJyk7CiAgCiAgICBmb3IgaTo9MCB0byBsZW5ndGgoYXJyX3Rlc3QpIGRpdiAyIC0xIGRvCiAgICAgIGFycl90ZXN0WzIqaSswXTo9MTsKICAgIGZvciBpOj0wIHRvIGxlbmd0aChhcnJfdGVzdCkgZGl2IDIgLTEgZG8KICAgICAgYXJyX3Rlc3RbMippKzFdOj0wOwogICAgdDo9R2V0VGlja0NvdW50NjQ7CQogICAgQXJyQ250KGFycl90ZXN0KTsKICAgIHQ6PUdldFRpY2tDb3VudDY0LXQ7CiAgICB3cml0ZWxuKG5tLCcgVGVzdCA0OiAnLCB0LCdtcycpOwogIAogICAgZm9yIGk6PTAgdG8gbGVuZ3RoKGFycl90ZXN0KSBkaXYgMi0xIGRvCiAgICAgIGFycl90ZXN0WzIqaSswXTo9MDsKICAgIGZvciBpOj0wIHRvIGxlbmd0aChhcnJfdGVzdCkgZGl2IDItMSBkbwogICAgICBhcnJfdGVzdFsyKmkrMV06PTE7CiAgICB0Oj1HZXRUaWNrQ291bnQ2NDsJCiAgICBBcnJDbnQoYXJyX3Rlc3QpOwogICAgdDo9R2V0VGlja0NvdW50NjQtdDsKICAgIHdyaXRlbG4obm0sJyBUZXN0IDU6ICcsIHQsJ21zJyk7ICAgIAogIGVuZDsKZW5kLg==