CSC300 / CSC402: XPerformanceOfArrays *2 [6/13] Previous pageContentsNext page

01
02
03
04
05
  public void push(double item) {
    if (N == a.length) resize(2*N);
    a[N] = item;
    N += 1;
  }

Output

00 
00 01 
00 01 02 03 
00 01 02 03 04 05 06 07 
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 
Elapsed count f(          512):             1,023:      2.002 [     0.000 :        NaN]
Elapsed count f(        1,024):             2,047:      2.001 [     0.000 :        NaN]
Elapsed count f(        2,048):             4,095:      2.000 [     0.000 :        NaN]
Elapsed count f(        4,096):             8,191:      2.000 [     0.000 :        NaN]
Elapsed count f(        8,192):            16,383:      2.000 [     0.000 :        NaN]
Elapsed count f(       16,384):            32,767:      2.000 [     0.001 :   Infinity]
Elapsed count f(       32,768):            65,535:      2.000 [     0.003 :      3.000]
Elapsed count f(       65,536):           131,071:      2.000 [     0.007 :      2.333]
Elapsed count f(      131,072):           262,143:      2.000 [     0.002 :      0.286]
Elapsed count f(      262,144):           524,287:      2.000 [     0.003 :      1.500]
Elapsed count f(      524,288):         1,048,575:      2.000 [     0.007 :      2.333]
Elapsed count f(    1,048,576):         2,097,151:      2.000 [     0.015 :      2.143]
Elapsed count f(    2,097,152):         4,194,303:      2.000 [     0.028 :      1.867]
Elapsed count f(    4,194,304):         8,388,607:      2.000 [     0.043 :      1.536]
Elapsed count f(    8,388,608):        16,777,215:      2.000 [     0.055 :      1.279]
Elapsed count f(   16,777,216):        33,554,431:      2.000 [     0.147 :      2.673]
Elapsed count f(   33,554,432):        67,108,863:      2.000 [     0.360 :      2.449]
Elapsed count f(   67,108,864):       134,217,727:      2.000 [     0.597 :      1.658]
Average delta: 2.000

N pushes in linear time

Each time we resize: constant pushes double

Each push is amortized constant time

Previous pageContentsNext page