chapter10.html

think like a computer scientist

}
</PRE>

<P>Notice that it is legal to pass <TT>apvector</TT>s by reference. In fact it 
is quite common, since it makes it unnecessary to copy the vector. Since 
<TT>printVector</TT> does not modify the vector, we declare the parameter 
<TT>const</TT>.</P>

<P>The following code generates a vector and outputs it:</P>

<PRE>
  int numValues = 20;
  int upperBound = 10;
  apvector<int> vector = randomVector (numValues, upperBound);
  printVector (vector);
</PRE>

<P>On my machine the output is</P>

<PRE>
3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6 
</PRE>

<P>which is pretty random-looking. Your results may differ.</P>

<P>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.</P>

<P>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.</P>

<P>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 
<TT>numValues</TT>.</P>


<BR><BR>
<H3>10.8 Counting</H3>

<P>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 <B>bottom-up design</B>.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.</P>

<P>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.</P>

<P>Back in Section 7.9 we looked at a loop that traversed a string and counted 
the number of times a given letter appeared. You can think of this program as 
an example of a pattern called ``traverse and count.'' The elements of this 
pattern are:</P>

<OL>
  <LI>A set or container that can be traversed, like a string or a vector.</LI>

  <LI>A test that you can apply to each element in the container.</LI>

  <LI>A counter that keeps track of how many elements pass the test.</LI>
</OL>

<P>In this case, I have a function in mind called <TT>howMany</TT> that counts 
the number of elements in a vector that equal a given value. The parameters are
the vector and the integer value we are looking for. The return value is the 
number of times the value appears.</P>

<PRE>
int howMany (const apvector<int>& vec, int value) {
  int count = 0;
  for (int i=0; i< vec.length(); i++) {
    if (vec[i] == value) count++;
  }
  return count;
}
</PRE>


<BR><BR>
<H3>10.9 Checking the other values</H3>

<P><TT>howMany</TT> 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:</P>

<PRE>
  int numValues = 20;
  int upperBound = 10;
  apvector<int> vector = randomVector (numValues, upperBound);

  cout << "value\thowMany";

  for (int i = 0; i &lt; upperBound; i++) {
    cout << i << '\t' << howMany (vector, i) << endl;
  }
</PRE>

<P>Notice that it is legal to declare a variable inside a <TT>for</TT> 
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</TT> later, you will get a compiler error.</P>

<P>This code uses the loop variable as an argument to <TT>howMany</TT>, in 
order to check each value between 0 and 9, in order. The result is:</P>

<PRE>
value   howMany
0       2
1       1
2       3
3       3
4       0
5       2
6       5
7       2
8       0
9       2
</PRE>

<P>Again, it is hard to tell if the digits are really appearing equally often.
If we increase <TT>numValues</TT> to 100,000 we get the following:</P>

<PRE>
value   howMany
0       10130
1       10072
2       9990
3       9842
4       10174
5       9930
6       10059
7       9954
8       9891
9       9958
</PRE>

<P>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.</P>


<BR><BR>
<H3>10.10 A histogram</H3>

<P>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>, <TT>howManyTwos</TT>, 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.</P>

<P>A better solution is to use a vector 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:</P>

<PRE>
  int numValues = 100000;
  int upperBound = 10;
  apvector&lt;int&gt; vector = randomVector (numValues, upperBound);
  apvector&lt;int&gt; histogram (upperBound);

  for (int i = 0; i &lt; upperBound; i++) {
    int count = howMany (vector, i);
    histogram[i] = count;
  }
</PRE>

<P>I called the vector <B>histogram</B> because that's a statistical term for 
a vector of numbers that counts the number of appearances of a range of 
values.</P>

<P>The tricky thing here is that I am using the loop variable in two different 
ways. First, it is an argument to <TT>howMany</TT>, specifying which value I am
interested in. Second, it is an index into the histogram, specifying which 
location I should store the result in.</P>


<BR><BR>
<H3>10.11 A single-pass solution</H3>

<P>Although this code works, it is not as efficient as it could be. Every time 
it calls <TT>howMany</TT>, it traverses the entire vector. In this example we 
have to traverse the vector ten times!</P>

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

<PRE>
  apvector<int> histogram (upperBound, 0);

  for (int i = 0; i &lt; numValues; i++) {
    int index = vector[i];
    histogram[index]++;
  }
</PRE>

<P>The first line initializes the elements of the histogram to zeroes. That way,when we use the increment operator (<TT>++</TT>) inside the loop, we know we 
are starting from zero. Forgetting to initialize counters is a common error.</P>

<P>As an exercise, encapsulate this code in a function called 
<TT>histogram</TT> that takes a vector and the range of values in the vector 
(in this case 0 through 10), and that returns a histogram of the values in the 
vector.</P>


<BR><BR>
<H3>10.12 Random seeds</H3>

<P>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!</P>

<P>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 <B>seed</B>; by default, C++ uses the same seed 
every time you run the program.</P>

<P>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.</P>

<P>If you want to choose a different seed for the random number generator, you 
can use the <TT>srand</TT> function. It takes a single argument, which is an 
integer between 0 and <TT>RAND_MAX</TT>.</P>

<P>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>gettimeofday</TT> to generate something reasonably 
unpredictable and unrepeatable, like the number of milliseconds since the last 
second tick, and use that number as a seed. The details of how to do that 
depend on your development environment.</P>


<BR><BR>
<H3>10.13 Glossary</H3>

<DL>
  <DT>vector:</DT><DD> A named collection of values, where all the values have 
  the same type, and each value is identified by an index.</DD>

  <DT>element:</DT><DD> One of the values in a vector. The <TT>[]</TT> operator
  selects elements of a vector.</DD>

  <DT>index:</DT><DD> An integer variable or value used to indicate an element 
  of a vector.</DD>

  <DT>constructor:</DT><DD> A special function that creates a new object and 
  initializes its instance variables.</DD>

  <DT>deterministic:</DT><DD> A program that does the same thing every time it 
  is run.</DD>

  <DT>pseudorandom:</DT><DD> A sequence of numbers that appear to be random, 
  but which are actually the product of a deterministic computation.</DD>

  <DT>seed:</DT><DD> A value used to initialize a random number sequence. Using
  the same seed should yield the same sequence of values.</DD>

  <DT>bottom-up design:</DT><DD> A method of program development that starts by
  writing small, useful functions and then assembling them into larger 
  solutions.</DD>

  <DT>histogram:</DT><DD> A vector of integers where each integer counts the 
  number of values that fall into a certain range.</DD>
</DL>

<BR>
<DIV CLASS=navigation><HR>
  <TABLE ALIGN=center WIDTH="100%" CELLPADDING=0 CELLSPACING=2>
  <TR>
    <TD><A HREF="chapter11.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter11.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="next" 
      SRC="images/next.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/next.gif"></A>
    </TD>

    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="up" 
      SRC="images/up.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/up.gif"></A>
    </TD>

    <TD><A HREF="chapter09.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter09.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="previous"
      SRC="images/previous.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/previous.gif"></A>
    </TD>

    <TD ALIGN=center BGCOLOR="#99CCFF" WIDTH="100%">
      <B CLASS=title>How to Think Like a Computer Scientist: Chapter 10</B>
    </TD>

    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="contents"
      SRC="images/contents.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/contents.gif"></A>
    </TD>

    <TD>
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""
      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">
    </TD>

    <TD>
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""
      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">
    </TD>
  </TR>
  </TABLE>

  <B CLASS=navlabel>Next:</B>
  <SPAN CLASS=sectref><A HREF="chapter11.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter11.html">Chapter 11</A></SPAN>

  <B CLASS=navlabel>Up:</b>
  <SPAN CLASS=sectref><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">Index</A></SPAN>

  <B CLASS=navlabel>Previous:</b>
  <SPAN CLASS=sectref><A HREF="chapter09.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter09.html">Chapter 9</A></SPAN>

  <HR>
</DIV>
</BODY>
</HTML>