Chapter 7.2.4 – Random Access | Introduction to Programming Using Java

Chapter 7.2.4 – Random Access | Introduction to Programming Using Java

 

7.2.4 Random Access

So far, all my examples of array processing have used sequential access. That is, the elements of the array were processed one after the other in the sequence in which they occur in the array. But one of the big advantages of arrays is that they allow random access. That is, every element of the array is equally accessible at any given time.

As an example, let’s look at a well-known problem called the birthday problem: Suppose that there are N people in a room. What’s the chance that there are two people in the room who have the same birthday? (That is, they were born on the same day in the same month, but not necessarily in the same year.) Most people severely underestimate the probability. We will actually look at a different version of the question: Suppose you choose people at random and check their birthdays.

How many people will you check before you find one who has the same birthday as someone you’ve already checked? Of course, the answer in a particular case depends on random factors, but we can simulate the experiment with a computer program and run the program several times to get an idea of how many people need to be checked on average.

To simulate the experiment, we need to keep track of each birthday that we find. There are 365 different possible birthdays. (We’ll ignore leap years.) For each possible birthday, we need to keep track of whether or not we have already found a person who has that birthday. The answer to this question is a boolean value, true or false. To hold the data for all 365 possible birthdays, we can use an array of 365 boolean values:

 

Chapter 7.2.4 - Random Access | Introduction to Programming Using Java

 

The days of the year are numbered from 0 to 364. The value of used[i] is true if someone has been selected whose birthday is day number i. Initially, all the values in the array, used, are false. When we select someone whose birthday is day number i, we first check whether used[i] is true.

If so, then this is the second person with that birthday. We are done. If used[i] is false, we set used[i] to be true to record the fact that we’ve encountered someone with that birthday, and we go on to the next person. Here is a subroutine that carries out the simulated experiment (of course, in the subroutine, there are no simulated people, only simulated birthdays):

 

Chapter 7.2.4 - Random Access | Introduction to Programming Using Java

 

Chapter 7.2.4 - Random Access | Introduction to Programming Using Java

 

This subroutine makes essential use of the fact that every element in a newly created array of boolean is set to be false. If we wanted to reuse the same array in a second simulation, we would have to reset all the elements in it to be false with a for loop:

 

Chapter 7.2.4 - Random Access | Introduction to Programming Using Java

 

The program that uses this subroutine is BirthdayProblemDemo.java. An applet version of the program can be found in the online version of this section.

 

 

 

Read More…

Introduction to Programming Using Java – David J. Eck

Chapter 5.7 – Interfaces | Introduction to Programming Using Java

Chapter 5.8 – Nested Classes | Introduction to Programming Using Java

Chapter 6 – Introduction to GUI Programming | Introduction to Programming Using Java

Chapter 7 – Arrays | Introduction to Programming Using Java

1 thought on “Chapter 7.2.4 – Random Access | Introduction to Programming Using Java”

Leave a Comment