Chapter7_Array.tex

% LaTeX source for textbook ``How to think like a computer scientist''
% Copyright (C) 1999  Allen B. Downey
% Copyright (C) 2009  Thomas Scheffler


\chapter{Arrays}
\label{arrays}
\index{arrays}
\index{type!array}

A {\bf array} is a set of values where each value is identified and referenced by a
number (called an index).  The nice thing
about arrays is that they can be made up of any type of element,
including basic types like {\tt int}s and {\tt double}s, 
but all the values in an array have to have the same type.
%and user-defined types like {\tt Point} and {\tt Time}.


When you declare an array, you have to determine the number of
elements in the array. Otherwise the declaration looks similar to other variable types:

\begin{verbatim}
    int c[4];
    double values[10];
\end{verbatim}


%

Syntactically, array variables look like other C variables except that they are followed 
by {\tt [NUMBER\_OF\_ELEMENTS]}, the number of elements in the array enclosed in square brackets. 
The first line in our example, {\tt int c[4];} is of the type "array of integers" and creates a array of four integers named {\tt c}.
The second line, {\tt double values[10];} has the type "array of doubles" and
  creates an array of 10 {\tt double}s. 

%The number
%of elements in {\tt values} depends on {\tt size}. You can use any
%integer expression to determine the size of an array.
%!!! Not in C
%this would be dynamic arrays, that can not be initialised at definition time!!!

%

C allows you to to initialize the element values of an array immediately
after you have declared it.  The values  for the individual elements must be 
enclosed in curly brakets {\tt \{\}} and separated by comma, as in the following example:

\begin{verbatim}
    int c[4] = {0, 0, 0, 0};
\end{verbatim}

This statement creates an array of four elements and initializes
all of them to zero.
This syntax is only legal at initialisation time. Later in your program you can only
assign values for the array element by element.

%
The following figure shows how arrays are represented in state
diagrams:

%\myfig{figure=figs/array.eps}

\unitlength0.1cm

\begin{picture}(40,10)(-30,-5)
%\put(-4,1.5){{\Large \texttt{c}}}
%\put(0,1.5){\framebox(2,2)}
%\thicklines
%\put(2,2.5){\vector(1,0){8}}
%\thinlines
\put(5,1.5){{\Large \texttt{c}}}
\put(10,0){\framebox(7,5){\textbf{\textsf{0}}}}
\put(17,0){\framebox(7,5){\textbf{\textsf{0}}}}
\put(24,0){\framebox(7,5){\textbf{\textsf{0}}}}
\put(31,0){\framebox(7,5){\textbf{\textsf{0}}}}

\put(10.5,-4){{\scriptsize \texttt{c[0]}}}
\put(17.5,-4){{\scriptsize \texttt{c[1]}}}
\put(24.5,-4){{\scriptsize \texttt{c[2]}}}
\put(31.5,-4){{\scriptsize \texttt{c[3]}}}

\end{picture}

The large numbers inside the boxes are the values of the {\bf elements} in
the array.  The small numbers outside the boxes are the
indices used to identify each box.  When you allocate a new
array, without initializing, the arrays elements typically
contain arbitrary values and you must initialise them to
a meaningful value before using them.


%%
\section{Increment and decrement operators}
\index{operator!increment}
\index{operator!decrement}
\index{increment}
\index{decrement}

Incrementing and decrementing are such common operations that C
provides special operators for them.  The {\tt ++} operator adds one
to the current value of an {\tt int}, {\tt char} or {\tt double}, and
{\tt -}{\tt -} subtracts one.  
%Neither operator works on {\tt apstring}s,
%and neither {\em should} be used on {\tt bool}s.

Technically, it is legal to increment a variable and use it
in an expression at the same time.  For example, you might see
something like:

\begin{verbatim}
    printf ("%i\n ", i++);
\end{verbatim}
%
Looking at this, it is not clear whether the increment will
take effect before or after the value is displayed.  Because
expressions like this tend to be confusing, I would discourage
you from using them.  In fact, to discourage you even more,
I'm not going to tell you what the result is.  If you really
want to know, you can try it.

Using the increment operators, we can rewrite the {\tt PrintMultTable()} from Section~\ref{More generalization}:

\begin{verbatim}
    void PrintMultTable(int high) 
    { 
        int i = 1; 
        while (i <= high) 
        { 
            PrintMultiples(i); 
            i++; 
        } 
    }
\end{verbatim}
%
It is a common error to write something like:

\begin{verbatim}
    index = index++;             /* WRONG!! */
\end{verbatim}
%
Unfortunately, this is syntactically legal, so the compiler
will not warn you.  The effect of this statement is to leave
the value of {\tt index} unchanged.  This is often a difficult
bug to track down.

Remember, you can write {\tt index = index + 1;}, or you
can write {\tt index++;}, but you shouldn't mix them.

%%
\section{Accessing elements}
\index{element}
\index{array!element}

The {\tt []} operator allows us to read and write the individual elements of an array.  
The indices start at zero, so {\tt c[0]}
refers to the first element of the array, and {\tt c[1]}
refers to the second element.  You can use the {\tt []} operator
anywhere in an expression:


\begin{verbatim}
    c[0] = 7;
    c[1] = c[0] * 2;
    c[2]++;
    c[3] -= 60;
\end{verbatim}
%
All of these are legal assignment statements.  Here is the
effect of this code fragment:


%\myfig{figure=figs/array2.eps}

\unitlength0.1cm

\begin{picture}(40,10)(-30,-5)
%\put(-11,1.5){\texttt{count}}
%\put(0,1.5){\framebox(2,2)}
%\thicklines
%\put(2,2.5){\vector(1,0){8}}
%\thinlines
\put(5,1.5){{\Large \texttt{c}}}

\put(10,0){\framebox(7,5){\textbf{\textsf{7}}}}
\put(17,0){\framebox(7,5){\textbf{\textsf{14}}}}
\put(24,0){\framebox(7,5){\textbf{\textsf{1}}}}
\put(31,0){\framebox(7,5){\textbf{\textsf{-60}}}}

\put(10.5,-4){{\scriptsize \texttt{c[0]}}}
\put(17.5,-4){{\scriptsize \texttt{c[1]}}}
\put(24.5,-4){{\scriptsize \texttt{c[2]}}}
\put(31.5,-4){{\scriptsize \texttt{c[3]}}}

\end{picture}

By now you should have noticed that the four elements of this array
are numbered from 0 to 3, which means that there is no element with
the index 4.  

Nevertheless, it is a common error to go
beyond the bounds of an array. In safer languages such as Java, this will cause an 
error and most likely the program quits. C does not check array boundaries, so
your program can go on accessing memory locations beyond the array itself, as if 
they where part of the array. This is most likely wrong and can cause very
severe bugs in your program. 
\begin{quote}

{\bf It is necessary that you, as a programmer,
make sure that your code correctly observes array boundaries!}

\end{quote}




\index{run-time error}
\index{index}
\index{expression}

You can use any expression as an index, as long as it has type {\tt
int}.  One of the most common ways to index an array is with a loop
variable.  For example:

\begin{verbatim}
    int i = 0;
    while (i < 4) 
    {
        printf ("%i\n", c[i]);
        i++;
    }
\end{verbatim}

%
This is a standard {\tt while} loop that counts from 0
up to 4, and when the loop variable {\tt i} is 4, the
condition fails and the loop terminates.  Thus, the body
of the loop is only executed when {\tt i} is 0, 1, 2 and 3.

\index{loop}
\index{loop variable}
\index{variable!loop}

Each time through the loop we use {\tt i} as an index into
the array, printing the {\tt i}th element.  This type of
array traversal is very common.  Arrays and loops go together
like fava beans and a nice Chianti.

\index{fava beans}
\index{Chianti}

%%
\section{Copying arrays}
\index{array!copying}

Arrays can be a very convenient solution for a number of problems, like
storing and processing large sets of data.

However, there is very little that C does automatically for you. For example
you can not set all the elements of an array at the same time and you can not
assign one array to the other, even if they are identical in type and number of elements.


\begin{verbatim}
    double a[3] = {1.0, 1.0, 1.0};
    double b[3];

    a = 0.0;     /* Wrong! */
    b = a;       /* Wrong! */
\end{verbatim}
%

In order to set all of the elements of an array to some value, you must do so element by element.
To copy the contents of one array to another, you must again do so, by copying each element from
one array to the other.

\begin{verbatim}
    int i = 0;
    while (i < 3) 
    {
        b[i] = a[i];
        i++;
    }
\end{verbatim}

%%
\section{{\tt for} loops}

The loops we have written so far have a number of elements
in common.  All of them start by initializing a variable;
they have a test, or condition, that depends on that variable;
and inside the loop they do something to that variable,
like increment it.

\index{loop!for}
\index{for}
\index{statement!for}

This type of loop is so common that there is an alternate
loop statement, called {\tt for}, that expresses it more
concisely.  The general syntax looks like this:

\begin{verbatim}
    for (INITIALIZER; CONDITION; INCREMENTOR) 
    {
        BODY
    }
\end{verbatim}
%
This statement is exactly equivalent to

\begin{verbatim}
    INITIALIZER;
    while (CONDITION) 
    {
        BODY
        INCREMENTOR
    }
\end{verbatim}
%
except that it is more concise and, since it puts all the
loop-related statements in one place, it is easier to read.
For example:

\begin{verbatim}
    int i;
    for (i = 0; i < 4; i++) 
    {
        printf("%i\n", c[i]);
    }
\end{verbatim}
%
is equivalent to 

\begin{verbatim}
    int i = 0;
    while (i < 4) 
    {
        printf("%i\n", c[i]);
        i++;
    }
\end{verbatim}

%%
\section{Array length}
\label{Array length}
\index{length!array}
\index{array!length}
\index{sizeof}
\index{operator!sizeof}

C does not provide us with a convenient way to determine the
actual length of an array. Knowing the size of an array would
be convenient when we are looping through all elements of
the array and need to stop with the last element.

In order to determine the array length we could use the {\tt sizeof()} 
operator, that calculates the size of data types in bytes.
Most data types in C use more than one byte to store their values,
therefore it becomes necessary to divide the byte-count for the array by 
the byte-count for a single element to establish the number of elements
in the array.
\begin{verbatim}
    sizeof(ARRAY)/sizeof(ARRAY_ELEMENT)
\end{verbatim}

It is a good idea to use this value as the upper bound of a loop,
rather than a constant.  That way, if the size of the array
changes, you won't have to go through the program changing all the
loops; they will work correctly for any size array.

\begin{verbatim}
    int i, length;
    length = sizeof (c) / sizeof (c[0]);

    for (i = 0; i < length; i++) 
    {
        printf("%i\n", c[i]);
    }
\end{verbatim}
%
The last time the body of the loop gets executed, the value of {\tt i}
is {\tt length - 1}, which is the index of the last element.  When
{\tt i} is equal to {\tt length}, the condition fails and the body
is not executed, which is a good thing, since it would access a
memory location that is not part of the array.

\section{Random numbers}
\label{Random numbers}
\label{random}
\label{pseudorandom}
\index{random number}
\index{deterministic}
\index{nondeterministic}

Most computer programs do the same thing every time they are executed,
so they are said to be {\bf deterministic}.  Usually, determinism is a
good thing, since we expect the same calculation to yield the same
result.  For some applications, though, we would like the
computer to be unpredictable.  Games are an obvious example.

Making a program truly {\bf nondeterministic} turns out to be not
so easy, but there are ways to make it at least seem
nondeterministic.  One of them is to generate {pseudorandom} numbers and
use them to determine the outcome of the program.
Pseudorandom numbers
are not truly random in the mathematical sense, but 
for our purposes, they will do.

\index{header file!stdlib.h}
\index{<stdlib.h>}

C provides a function called {\tt rand()} that generates
pseudorandom numbers.  It is declared in the
header file {\tt stdlib.h}, which contains a variety of ``standard
library'' functions, hence the name.

The return value from {\tt rand()} is an integer between 0 and {\tt
RAND\_MAX}, where {\tt RAND\_MAX} is a large number (about 2 billion
on my computer) also defined in the header file.  Each time you call
{\tt rand()} you get a different randomly-generated number.  To see a
sample, run this loop:

\begin{verbatim}
    for (i = 0; i < 4; i++) 
    {
        int x = rand();
        printf("%i\n", x);
    }
\end{verbatim}
%
On my machine I got the following output:

\begin{verbatim}
1804289383
846930886
1681692777
1714636915
\end{verbatim}
%
You will probably get something similar, but different, on yours.

Of course, we don't always want to work with gigantic integers.
More often we want to generate integers between 0 and some
upper bound.  A simple way to do that is with the modulus
operator.  For example:

\begin{verbatim}
    int x = rand ();
    int y = x % upperBound;
\end{verbatim}
%
Since {\tt y} is the remainder when {\tt x} is divided by
{\tt upperBound}, the only possible values for {\tt y}
are between 0 and {\tt upperBound - 1}, including both
end points.  Keep in mind, though, that {\tt y} will never
be equal to {\tt upperBound}.

It is also frequently useful to generate random floating-point values.
A common way to do that is by dividing by {\tt RAND\_MAX}.  For
example:

\begin{verbatim}
    int x = rand ();
    double y = (double) x / RAND_MAX;
\end{verbatim}
%
This code sets {\tt y} to a random value between 0.0 and 1.0,
including both end points.  As an exercise, you might want to
think about how to generate a random floating-point value in
a given range; for example, between 100.0 and 200.0.

%%
\pagebreak
\section{Statistics}
\index{statistics}
\index{distribution}
\index{mean}

The numbers generated by {\tt rand()} are supposed to be distributed
uniformly.  That means that each value in the range should be
equally likely.  If we count the number of times each value appears,
it should be roughly the same for all values, provided that we
generate a large number of values.

In the next few sections, we will write programs that generate
a sequence of random numbers and check whether this property
holds true.

%%
\section{Array of random numbers}
\label{Array of random numbers}

The first step is to generate a large number of random values
and store them in a array.  By ``large number,'' of course,
I mean 20.  It's always a good idea to start with a manageable
number, to help with debugging, and then increase it later.

The following function takes three arguments, an array of integers, 
the size of the array and an upper bound for the random values.  
It fills the array of {\tt int}s with random values between 0 and {\tt upperBound-1}.

\begin{verbatim}
    void RandomizeArray (int array[], int length, int upperBound) 
    {
        int i;
        for (i = 0; i < length; i++) 
        {
            array[i] = rand() % upperBound;
        }
    }
\end{verbatim}
%
The return type is {\tt void}, which means that
this function does not return any value to the calling function.
To test this function, it is convenient to have a function that
outputs the contents of a array.

\begin{verbatim}
    void PrintArray (int array[], int length) 
    {
        int i;
        for (i = 0; i < length; i++) 
        {
            printf ("%i ",  array[i]);
        }
    }
\end{verbatim}
%
The following code generates an array filled with random values and outputs it:

\begin{verbatim}
    int r_array[20];
    int upperBound = 10;
    int length = sizeof(r_array) / sizeof(r_array[0]);
  
    RandomizeArray (r_array, length, upperBound);
    PrintArray (r_array, length);
\end{verbatim}

%
On my machine the output is:

\begin{verbatim}
3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6 
\end{verbatim}
\nopagebreak%
which is pretty random-looking.  Your results may differ.

If these numbers are really random,
we expect each digit to appear the same number of times---twice
each.  In fact, the number 6 appears five times, and the numbers 4
and 8 never appear at all.

Do these results mean the values are not really uniform?  It's
hard to tell.  With so few values, the chances are slim
that we would get exactly what we expect.  But as the number
of values increases, the outcome should be more predictable.

To test this theory, we'll write some programs that count the
number of times each value appears, and then see what happens
when we increase the number of elements in our array.

%%
\section{Passing an array to a function}
\label{Passing an array to a function}
\index{call by reference}
\index{call by value}
\index{array parameters}
You probably have noticed that our {\tt RandomizeArray()} function 
looked a bit unusual. We pass an array to this function and expect 
to get a a randomized array back. Nevertheless, we have declared it to 
be a {\tt void} function, and miraculously the function appears to have 
altered the array.

This behaviour goes against everything what I have said about the
use of variables in functions so far.
C typically uses the so called {\bf call-by-value} evaluation of
expressions. If you pass a value to a function it gets copied from
the calling function to a variable in the called function. The same
is true if the function returns a value.
Changes to the internal variable in the called function do not affect the external 
values of the calling function.

When we pass an array to a function this behaviour changes to
something called {\bf call-by-reference} evaluation.
C does not copy the array to an internal array --  it rather generates a
reference to the original array and any operation in the called function 
directly affects the original array.
This is also the reason why we do not have to return anything from our 
function. The changes have already taken place. 

Call by reference also makes it necessary to supply the length of
the array to the called function, since invoking  the {\tt sizeof}
operator in the called function would determine the size of the reference
and not the original array.

%!!!Reference to later chapter needed!!!
We will further discuss call by reference and call by value in 
Section~\ref{Pointers and Addresses}, Section~\ref{Call by value} and
\ref{Call by reference}.

%%
\section{Counting}
\label{counting}
\index{traverse!counting}
\index{loop!counting}
\index{counter}

A good approach to problems like this is to think of simple functions
that are easy to write, and that might turn out to be useful.  Then
you can combine them into a solution.  This approach is sometimes
called {\bf bottom-up design}.  

Of course, it is not easy to
know ahead of time which functions are likely to be useful, but as you
gain experience you will have a better idea.
\index{bottom-up design}
\index{program development!bottom-up}
Also, it is not always obvious what sort of things are easy to write,
but a good approach is to look for subproblems that fit a pattern you
have seen before.

\index{pattern!counter}

%Back in Section~\ref{loopcount} we looked at a loop that traversed a
%string and counted the number of times a given letter appeared.  
In our current example we want to examine a potentially large set
of elements and count the number of times a certain value appears.
You
can think of this program as an example of a pattern called ``traverse
and count.''  The elements of this pattern are:

\begin{itemize}

\item A set or container that can be traversed, like a string
or a array.

\item A test that you can apply to each element in the container.

\item A counter that keeps track of how many elements pass
the test.

\end{itemize}

In this case, I have a function in mind called {\tt HowMany()} that
counts the number of elements in a array that are equal to a given value.
The parameters are the array, the length of the array and the integer value we are looking
for.  The return value is the number of times the value appears.

\begin{verbatim}
    int HowMany (int array[], int length, int value) 
    {
        int i; 
        int count = 0;
  
        for (i=0; i < length; i++) 
            {
                if (array[i] == value) count++;
            }
        return count;
    }
\end{verbatim}


\section{Checking the other values}

{\tt HowMany()} only counts the occurrences of a particular value, and
we are interested in seeing how many times each value appears.
We can solve that problem with a loop:

\begin{verbatim}
    int i;
    int r_array[20];
    int upperBound = 10;
    int length = sizeof(r_array) / sizeof(r_array[0]);
  
    RandomizeArray(r_array, length, upperBound);

    printf ("value\tHowMany\n");
    for (i = 0; i < upperBound; i++) 
    {
        printf("%i\t%i\n", i, HowMany(r_array, length, i));
    }
\end{verbatim}
%

%! ! ! Applies only to C++! ! !
%Notice that it is legal to declare a variable inside a {\tt for}
%statement.  This syntax is sometimes convenient, but you should
%be aware that a variable declared inside a loop only exists
%inside the loop.  If you try to refer to {\tt i} later, you
%will get a compiler error.

This code uses the loop variable as an argument to
{\tt HowMany()}, in order to check each value between 0 and 9,
in order.  The result is:

\begin{verbatim}
value   HowMany
0       2
1       1
2       3
3       3
4       0
5       2
6       5
7       2
8       0
9       2
\end{verbatim}
%
Again, it is hard to tell if the digits are really appearing
equally often.  If we increase the size of the array to 100,000 we
get the following:

\begin{verbatim}
value   HowMany
0       10130
1       10072
2       9990
3       9842
4       10174
5       9930
6       10059
7       9954
8       9891
9       9958
\end{verbatim}
%
In each case, the number of appearances is within about 1\% of
the expected value (10,000), so we conclude that the random
numbers are probably uniform.

\section {A histogram}
\index{histogram}

It is often useful to take the data from the previous tables
and store them for later access, rather than just print them.
What we need is a way to store 10 integers.  We could create
10 integer variables with names like {\tt howManyOnes},
{\tt howManyTwos}, etc.  But that would require a lot of
typing, and it would be a real pain later if we decided to
change the range of values.

A better solution is to use a array with length 10.  That
way we can create all ten storage locations at once and we
can access them using indices, rather than ten different names.
Here's how:

\begin{verbatim}
    int i;
    int upperBound = 10;
    int r_array[100000];
    int histogram[upperBound];
    int r_array_length = sizeof(r_array) / sizeof(r_array[0]);
  
    RandomizeArray(r_array, r_array_length, upperBound);

    for (i = 0; i < upperBound; i++) 
    {
        int count = HowMany(r_array, length, i);
        histogram[i] = count;
    }  
\end{verbatim}
%
I called the array {\bf histogram} because that's
a statistical term for a array of numbers that counts the
number of appearances of a range of values.

\index{histogram}

The tricky thing here is that I am using the loop variable
in two different ways.  First, it is an argument to {\tt HowMany()},
specifying which value I am interested in.  Second, it is
an index into the histogram, specifying which location I should
store the result in.

\section{A single-pass solution}

Although this code works, it is not as efficient as it could
be.  Every time it calls {\tt HowMany()}, it traverses the
entire array.  In this example we have to traverse the
array ten times!

It would be better to make a single pass through the array.
For each value in the array we could find the corresponding
counter and increment it.  In other words, we can use the
value from the array as an index into the histogram.  Here's
what that looks like:

\begin{verbatim}
    int upperBound = 10;
    int histogram[upperBound] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

    for (i = 0; i < r_array_length; i++) 
    {
        int index = r_array[i];
        histogram[index]++;
    }
\end{verbatim}
%
The second line initializes the elements of the histogram to
zeroes.  That way, when we use the increment
operator ({\tt ++}) inside the loop, we know we are starting from zero.
Forgetting to initialize counters is a common error.

As an exercise, encapsulate this code in a function called {\tt Histogram()} 
that takes an array and the range of values in the array
(in this case 0 through 10) as two parameters \texttt{min} and \texttt{max}. 
You should pass a second array to the function where a histogram of the
values in the array can be stored.

\section{Random seeds}
\label{Random seeds}
\index{seed}
\index{random}

If you have run the code in this chapter a few times, you might
have noticed that you are getting the same ``random'' values
every time.  That's not very random!

One of the properties of pseudorandom number generators is that
if they start from the same place they will generate
the same sequence of values.  The starting place is called
a {\bf seed}; by default, C uses
the same seed every time you run the program.

While you are debugging, it is often helpful to
see the same sequence over and over.  That way, when you make
a change to the program you can compare the output before and
after the change.

If you want to choose a different seed for the random number
generator, you can use the {\tt srand()} function.  It takes
a single argument, which is an integer between 0 and {\tt RAND\_MAX}.

For many applications, like games, you want to see a different
random sequence every time the program runs.  A common way to
do that is to use a library function like {\tt time()}
to generate something reasonably unpredictable
and unrepeatable, like the number of seconds since January
1970, and use that number as a seed.  The details
of how to do that depend on your development environment.

\section{Glossary}

\begin{description}

\item[array:]  A named collection of values, where all the
values have the same type, and each value is identified by
an index.

\item[element:]  One of the values in a array.  The {\tt []}
operator selects elements of a array.

\item[index:]  An integer variable or value used to indicate
an element of a array.

\item[increment:]  Increase the value of a variable by one.
The increment operator in C is {\tt ++}. 

\item[decrement:]  Decrease the value of a variable by one.
The decrement operator in C is {\tt -}{\tt -}.

\item[deterministic:]  A program that does the same thing every
time it is run.

\item[pseudorandom:]  A sequence of numbers that appear to be
random, but which are actually the product of a deterministic
computation.

\item[seed:]  A value used to initialize a random number sequence.
Using the same seed should yield the same sequence of values.

\item[bottom-up design:]  A method of program development that
starts by writing small, useful functions and then assembling
them into larger solutions.

\item[histogram:]  A array of integers where each integer
counts the number of values that fall into a certain range.

\index{array}
\index{element}
\index{index}
\index{deterministic}
\index{pseudorandom}
\index{seed}
\index{histogram}

\end{description}

%%
\section{Exercises}
\setcounter{exercisenum}{0}


\input{exercises/Exercise_7_english}