Arrays

Bryce Summers

Overview

An Array is a collection of elements, where every element is associated with an index.

Arrays can be thought of as lookup Functions:

[0, N) → Elements

that allow for the efficient lookup of the elements associated with given integer indices, and N is the size of the Array.

Visual Representation

​

​

​

​

​

Fixed Size Array of size N, represented by a box diagram.

Random Access Machine

A Random Access Machine is a huge array of memory locations that can be accessed efficiently through a memory address lookup.

Fixed Size Array

Arrays are allocated as contiguous subsets of a Random Access Machine.

Array Location

Array of size 4 elements, with memory address 2.

Element Size

The element size of an array is the maximum size needed to store the data used to represent an element.

Array Location

Array of size 4 elements, with memory address 2.

Array Size

The array size is the number of elements the array can store. The memory size of an array is:

The array size*element size

Array Location

Array of size 4 elements, with memory address 2.

Memory Address

The Memory Address of an array is the location of the 1st bit in the memory region allocated for the array.

Array Location

Array of size 4 elements, with memory address 2.

Memory Lookup

The memory location of the element associated with a memory lookup at index I is:

Array Location + I*size of element

Array Location

Array with 4 elements of size 1 each,

with memory address 2.

A[3] = lookup(2 + 3*1) = e₅

Analysis of Lookup

Assume that Random Access Lookup (RAL) (address) costs 1 operation.

Assume that arithmetic operations costs 1 operation.

Array Lookup(index) = RAL(memory location + size of element*index);

Let val = memory location + size of element*index

val costs 2 operation to compute(1 addition and 1 multiplication)

Let result = RAL(val), result costs 1 operation to compute from val.

​

In total it takes 3 operations to perform any memory lookup, which is indicates that it is efficient to perform lookups on arrays implemented on a Random Access machine, which is indicative of the performance of arrays on real machines.

​

​

Unbounded Arrays

Unbounded Arrays are arrays that can efficiently change their memory size allocations.

​

Please see the Amortized Analysis section and Unbounded array sections of my book, found here for more information.

Language Specific Array Allocation.

JAVA: Type[] name = new Type[size];

​

C : Type * = (Type*)malloc(sizeof(Type)*size);