Arrays/Python/Sizeof

Goodrich Python Chapter 5

R-1 Measuring size in bytes of list

This script illustrates how a list grows dynamically, in proportion to its size, when we add additional items to the list. It doubles in length each time it is resized, for an O(n) operation. If it increased in size by a constant amount, that would impose a bottleneck and be an O(n^2) operation.

import sys
data = []
for k in range(n):
  a = len(data)
  b = sys.getsizeof(data)
  print("Length: {0:3d}\tSize in bytes: {1:4d}".format(a,b))
  data.append(None)

Plot of list sizeof

R-2 Only printing the sizes where the array is exhausted and resized

import sys

n = 10000
data = []

so = sys.getsizeof(data)

for k in range(n):
    sonew = sys.getsizeof(data)

    if(sonew != so):
        so = sonew
        mylen = len(data)
        print("len {0}, sizeof (bytes) {1}".format(sonew,mylen))

    data.append(None)

and the output:

$ python listsize-exhausted.py
len 104, sizeof (bytes) 1
len 136, sizeof (bytes) 5
len 200, sizeof (bytes) 9
len 272, sizeof (bytes) 17
len 352, sizeof (bytes) 26
len 440, sizeof (bytes) 36
len 536, sizeof (bytes) 47
len 648, sizeof (bytes) 59
len 776, sizeof (bytes) 73
len 920, sizeof (bytes) 89
len 1080, sizeof (bytes) 107
len 1256, sizeof (bytes) 127
len 1456, sizeof (bytes) 149
len 1680, sizeof (bytes) 174
len 1936, sizeof (bytes) 202
len 2224, sizeof (bytes) 234
len 2544, sizeof (bytes) 270
len 2904, sizeof (bytes) 310
len 3312, sizeof (bytes) 355
len 3768, sizeof (bytes) 406
len 4280, sizeof (bytes) 463
len 4856, sizeof (bytes) 527
len 5504, sizeof (bytes) 599
len 6240, sizeof (bytes) 680
len 7064, sizeof (bytes) 772
len 7992, sizeof (bytes) 875
len 9032, sizeof (bytes) 991
len 10208, sizeof (bytes) 1121
len 11528, sizeof (bytes) 1268
len 13016, sizeof (bytes) 1433
len 14688, sizeof (bytes) 1619
len 16568, sizeof (bytes) 1828
len 18680, sizeof (bytes) 2063
len 21056, sizeof (bytes) 2327
len 23736, sizeof (bytes) 2624
len 26744, sizeof (bytes) 2959
len 30128, sizeof (bytes) 3335
len 33936, sizeof (bytes) 3758
len 38224, sizeof (bytes) 4234
len 43048, sizeof (bytes) 4770
len 48472, sizeof (bytes) 5373
len 54576, sizeof (bytes) 6051
len 61440, sizeof (bytes) 6814
len 69168, sizeof (bytes) 7672
len 77856, sizeof (bytes) 8638
len 87632, sizeof (bytes) 9724

R-3 showing dynamic shrinkage

Arrays automatically double in size as more items are added to them, but they also shrink when items are removed from them.

This is accomplished by specifying a sequence of add/remove operation sizes:

import sys
from matplotlib.pyplot import *
import seaborn as sns

data = []

sequence = [1000,-800,200,-200,1000]
tot = sum(sequence)

so = sys.getsizeof(data)

x = [0]*tot
y = [0]*tot

for n in sequence:
    if(n>0):
        print("++++ADDING ITEMS++++")
    else:
        print("----REMOVING ITEMS----")

    for k in range(abs(n)):
        sonew = sys.getsizeof(data)
        mylen = len(data)

        x.append(sonew)
        y.append(mylen)

        if(sonew != so):
            so = sonew
            print("len {0}, sizeof (bytes) {1}".format(sonew,mylen))

        if(n>0):
            data.append(None)
        else:
            data.pop()


xlabel('Array size')
ylabel('Byte size')
title('Size in bytes vs. List size')

i = 0
for n,w in zip(sequence,[abs(j) for j in sequence]):
    plot(x[i:i+w],y[i:i+w],'-o',label=str(n))
    i += w

legend()
savefig('listsize-pop.png')
show()