<jupyter_start><jupyter_text>Memory locality, Rows vs. Columns  The effect of row vs column major layoutThe way you traverse a 2D array effects speed. * [numpy arrays](https://docs.scipy.org/doc/numpy/reference/generated/numpy.array.htmlnumpy-array) are, by default, organized in a row-major order.  ```pythona=array([range(1,31)]).reshape([3,10])``` * `a[i,j]` and `a[i,j+1]` are placed in consecutive places in memory. * `a[i,j]` and `a[i+1,j]` are 10 memory locations apart. * This implies that scanning the array row by row is more local than scanning column by column. * locality implies speed.<jupyter_code>%pylab inline
from time import time

# create an n by n array
n=1000
a=ones([n,n])
%%time
# Scan column by column
s=0;
for i in range(n): s+=sum(a[:,i])
%%time
## Scan row by row
s=0;
for i in range(n): s+=sum(a[i,:])<jupyter_output>CPU times: user 7.53 ms, sys: 4 ms, total: 11.5 ms
Wall time: 7.89 ms<jupyter_text>Some experiments with row vs column scanningWe want to see how the run time of these two code snippets varies as `n`, the size of the array, is changed.<jupyter_code>def sample_run_times(T,k=10):
    """ compare the time to sum an array row by row vs column by column
        T: the sizes of the matrix, [10**e for e in T] 
        k: the number of repetitions of each experiment
    """
    all_times=[]
    for e in T:
        n=int(10**e)
        #print('\r',n)
        a=np.ones([n,n])
        times=[]

        for i in range(k):    
            t0=time()
            s=0;
            for i in range(n):
                s+=sum(a[:,i])
            t1=time()
            s=0;
            for i in range(n):
                s+=sum(a[i,:])
            t2=time()
            times.append({'row minor':t1-t0,'row major':t2-t1})
        all_times.append({'n':n,'times':times})
    return all_times

#example run
sample_run_times([1,2],k=1)<jupyter_output><empty_output><jupyter_text>Plot the ratio between run times as function of nHere we have small steps between consecutive values of `n` and only one measurement for each (`k=1`)<jupyter_code>all_times=sample_run_times(np.arange(1.5,3.01,0.001),k=1)

n_list=[a['n'] for a in all_times]
ratios=[a['times'][0]['row minor']/a['times'][0]['row major'] for a in all_times]

figure(figsize=(15,10))
plot(n_list,ratios)
grid()
xlabel('size of matrix')
ylabel('ratio or running times')
title('time ratio as a function of size of array');<jupyter_output><empty_output><jupyter_text>Conclusions* Traversing a numpy array column by column takes more than row by row.* The effect increasese proportionally to the number of elements in the array (square of the number of rows or columns).* Run time has large fluctuations. * See you next time.  Next, we want to quantify the random fluctuationsand see what is their source<jupyter_code>k=100
all_times=sample_run_times(np.arange(1,3.001,0.01),k=k)
_n=[]
_row_major_mean=[]
_row_major_std=[]
_row_major_std=[]
_row_minor_mean=[]
_row_minor_std=[]
_row_minor_min=[]
_row_minor_max=[]
_row_major_min=[]
_row_major_max=[]

for times in all_times:
    _n.append(times['n'])
    row_major=[a['row major'] for a in times['times']]
    row_minor=[a['row minor'] for a in times['times']]
    _row_major_mean.append(np.mean(row_major))
    _row_major_std.append(np.std(row_major))
    _row_major_min.append(np.min(row_major))
    _row_major_max.append(np.max(row_major))

    _row_minor_mean.append(np.mean(row_minor))
    _row_minor_std.append(np.std(row_minor))
    _row_minor_min.append(np.min(row_minor))
    _row_minor_max.append(np.max(row_minor))

_row_major_mean=np.array(_row_major_mean)
_row_major_std=np.array(_row_major_std)
_row_minor_mean=np.array(_row_minor_mean)
_row_minor_std=np.array(_row_minor_std)
figure(figsize=(20,13))
plot(_n,_row_major_mean,'o',label='row major mean')
plot(_n,_row_major_mean-_row_major_std,'x',label='row major mean-std')
plot(_n,_row_major_mean+_row_major_std,'x',label='row major mean+std')
plot(_n,_row_major_min,label='row major min among %d'%k)
plot(_n,_row_major_max,label='row major max among %d'%k)
plot(_n,_row_minor_mean,'o',label='row minor mean')
plot(_n,_row_minor_mean-_row_minor_std,'x',label='row minor mean-std')
plot(_n,_row_minor_mean+_row_minor_std,'x',label='row minor mean+std')
plot(_n,_row_minor_min,label='row minor min among %d'%k)
plot(_n,_row_minor_max,label='row minor max among %d'%k)
xlabel('size of matrix')
ylabel('running time')
legend()
grid()<jupyter_output><empty_output>