| CSC300: XPerformanceOfArrays *4 [8/14] | |
01 |
public void push(double item) { if (N == a.length) resize(4*N); a[N] = item; N += 1; } |
Output
00 00 01 02 03 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 Elapsed count f( 512): 853: 2.501 [ 0.000 : NaN] Elapsed count f( 1,024): 1,365: 1.600 [ 0.000 : NaN] Elapsed count f( 2,048): 3,413: 2.500 [ 0.000 : NaN] Elapsed count f( 4,096): 5,461: 1.600 [ 0.000 : NaN] Elapsed count f( 8,192): 13,653: 2.500 [ 0.001 : Infinity] Elapsed count f( 16,384): 21,845: 1.600 [ 0.001 : 1.000] Elapsed count f( 32,768): 54,613: 2.500 [ 0.002 : 2.000] Elapsed count f( 65,536): 87,381: 1.600 [ 0.003 : 1.500] Elapsed count f( 131,072): 218,453: 2.500 [ 0.007 : 2.333] Elapsed count f( 262,144): 349,525: 1.600 [ 0.006 : 0.857] Elapsed count f( 524,288): 873,813: 2.500 [ 0.008 : 1.333] Elapsed count f( 1,048,576): 1,398,101: 1.600 [ 0.010 : 1.250] Elapsed count f( 2,097,152): 3,495,253: 2.500 [ 0.037 : 3.700] Elapsed count f( 4,194,304): 5,592,405: 1.600 [ 0.029 : 0.784] Elapsed count f( 8,388,608): 13,981,013: 2.500 [ 0.100 : 3.448] Elapsed count f( 16,777,216): 22,369,621: 1.600 [ 0.061 : 0.610] Elapsed count f( 33,554,432): 55,924,053: 2.500 [ 0.429 : 7.033] Elapsed count f( 67,108,864): 89,478,485: 1.600 [ 0.288 : 0.671] Average delta: 2.050
N pushes in linear time
Each time we resize: constant pushes quadruple
Each push is ammortized constant time