| CSC300: XPerformanceOfArrays *8 [9/14] | |
01 |
public void push(double item) { if (N == a.length) resize(8*N); a[N] = item; N += 1; } |
Output
00 00 01 02 03 04 05 06 07 Elapsed count f( 512): 585: 1.778 [ 0.000 : NaN] Elapsed count f( 1,024): 1,609: 2.750 [ 0.000 : NaN] Elapsed count f( 2,048): 2,633: 1.636 [ 0.000 : NaN] Elapsed count f( 4,096): 4,681: 1.778 [ 0.000 : NaN] Elapsed count f( 8,192): 12,873: 2.750 [ 0.001 : Infinity] Elapsed count f( 16,384): 21,065: 1.636 [ 0.001 : 1.000] Elapsed count f( 32,768): 37,449: 1.778 [ 0.001 : 1.000] Elapsed count f( 65,536): 102,985: 2.750 [ 0.006 : 6.000] Elapsed count f( 131,072): 168,521: 1.636 [ 0.005 : 0.833] Elapsed count f( 262,144): 299,593: 1.778 [ 0.007 : 1.400] Elapsed count f( 524,288): 823,881: 2.750 [ 0.013 : 1.857] Elapsed count f( 1,048,576): 1,348,169: 1.636 [ 0.016 : 1.231] Elapsed count f( 2,097,152): 2,396,745: 1.778 [ 0.017 : 1.063] Elapsed count f( 4,194,304): 6,591,049: 2.750 [ 0.095 : 5.588] Elapsed count f( 8,388,608): 10,785,353: 1.636 [ 0.043 : 0.453] Elapsed count f( 16,777,216): 19,173,961: 1.778 [ 0.060 : 1.395] Elapsed count f( 33,554,432): 52,728,393: 2.750 [ 0.733 : 12.217] Elapsed count f( 67,108,864): 86,282,825: 1.636 [ 0.298 : 0.407] Average delta: 2.055
N pushes in linear time
Each time we resize: constant pushes multiply by 8
Each push is ammortized constant time