1.4 ArraysA data structure is a way to organize data that we wish to process with a computer program. A one-dimensional array (or array) is a data structure that stores a sequence of (references to) objects. We refer to the objects within an array as its elements. The method that we use to refer to elements in an array is numbering and then indexing them. If we have n elements in the sequence, we think of them as being numbered from 0 to n - 1. Then, we can unambiguously specify one of them by referring to the ith element for any integer i in this range. Show
A two-dimensional array is an array of (references to) one-dimensional arrays. Whereas the elements of a one-dimensional array are indexed by a single integer, the elements of a two-dimensional array are indexed by a pair of integers: the first specifying a row, and the second specifying a column. The simplest way to create an array in Python is to place comma-separated literals between matching square brackets. For example, the code
creates an array SUITS[] with four strings, and creates arrays x[] and y[], each with three floats. Given two vectors of the same length, their dot product is the sum of the products of their corresponding components. If we represent the two vectors as one-dimensional arrays x[] and y[] that are each of length n, their dot product is easy to compute:
For example, following trace shows the computation of the dot product of two vectors of length 3. It is useful to think of references to the elements in an array as stored contiguously, one after the other, in your computer's memory, as shown in the diagram at the right for the SUITS[] array defined above. Zero-based indexing.We always refer to the first element of an array a[] as a[0], the second as a[1], and so forth. It might seem more natural to refer to the first element as a[1], the second element as a[2], and so forth, but starting the indexing with 0 has some advantages and has emerged as the convention used in most modern programming languages.Array length.You can access the length of an array using Python's built-in len() function: len(a) is the number of elements in a[]. In Python, we can use the += operator to append elements to an array. For example, if a[] is the array [1, 2, 3], then the statement a += [4] extends it to [1, 2, 3, 4]. More generally, we can make an array of n floats, with each element initialized to 0.0, with the code
Bounds checking.You must be careful when programming with arrays. It is your responsibility to use legal indices when accessing an array element.Mutability.An object is mutable if its value can change. Arrays are mutable objects because we can change their elements. For example, if we create an array with the code x = [.30, .60, .10], then the assignment statement x[1] = .99 changes it to the array [.30, .99, .10]. An object-level trace of this operation is shown at the right.The following code reverses the order of the elements in an array a[]:
An informal trace of this code for a seven-element array [3, 1, 4, 1, 5, 9, 2] is shown at the right.Iteration.The following code iterates over all elements of an array to compute the average of the floats that it contains:
Python also supports iterating over the elements in an array without referring to the indices explicitly. To do so, put the array name after the in keyword in a for statement, as follows:
Built-in functions.Python has several built-in functions that can take arrays as arguments. We have already discussed the len() function. As another example, if the elements of a[] are numeric, then sum(a) computes their sum, so that we can compute their average with float(sum(a)) / len(a) instead of using either of the loops just described. Other useful built-in functions that can take arrays as arguments are min() for computing the minimum and max() for computing the maximum.Writing an array.You can write an array by passing it as an argument to stdio.write() or stdio.writeln(). Each object in the array is converted to a string.Array Aliases and CopiesBefore looking at programs that use arrays, it is worthwhile to examine two fundamental array-processing operations in more detail. Aliasing.If x[] and y[] are arrays, the statement x = y causes x and y to reference the same array. This result has an effect that is perhaps unexpected, at first, because it is natural to think of x and y as references to two independent arrays. For example, after the assignment statements
y[1] is also .99, even though the code does not refer directly to y[1]. This situation — whenever two variables refer to the same object — is known as aliasing, and is illustrated in the object-level trace at the right. Copying and slicing.So how do we make a copy y[] of a given array x[]? One answer to this question is to iterate through x[] to build y[], as in the following code:
This situation is illustrated in the object-level trace at the right. Copying an array is such a useful operation that Python provides language support for a more general operation known as slicing, The expression a[i:j] evaluates to a new array whose elements are a[i], ..., a[j-1]. Moreover, the default value for i is 0 and the default value for j is len(a), so y = x[:] is equivalent to the code given earlier. System Support for ArraysPython code for processing arrays can take many forms. We describe each briefly for context. Python's built-in list data type.In its most basic form, an array supports four core operations: creation, indexed access, indexed assignment, and iteration. In this booksite, we use Python's built-in list data type for arrays because it supports these basic operations. We consider more elaborate operations supported by Python's list data type in Chapter 4.Python's numpy module.Python's built-in list data type can have severe performance problems. For that reason, scientists and engineers often use a Python extension module called numpy for processing huge arrays of numbers, because that module uses a lower-level representation that avoids many of the inefficiencies in the standard Python representation. See Appendix: numpy for an overview of the numpy module.Our stdarray module.Earlier we introduced the booksite stdio module. Now, we introduce another booksite module: the stdarray module. Its primary purpose is to define functions for processing arrays.A fundamental operation that is found in nearly every array-processing program is to create an array of n elements, each initialized to a given value. As we have seen, you can do this in Python with code like the following:
Such code is so common that Python even has a special shorthand notation for it: the code a = [0.0]*n is equivalent to the code just given. Rather than repeat such code throughout the book, we will use code like this:
For consistency, stdarray also includes a create2D() function, which we will examine later in this section. Sample Applications of ArraysNext, we consider a number of applications that illustrate the utility of arrays and also are interesting in their own right. Representing playing cards.Suppose that we want to compose programs that process playing cards. We might start with the following code:
For example, we might use these two arrays to write a random card name, such as Queen of Clubs, as follows:
A more typical situation is when we compute the values to be stored in an array. For example, we might use the following code to initialize an array of length 52 that represents a deck of playing cards, using the two arrays just defined:
Exchange.Frequently, we wish to exchange two elements in an array. Continuing our example with playing cards, the following code exchanges the cards at indices i and j:
Shuffle. The following code shuffles our deck of cards:
Proceeding from left to right, we pick a random card from deck[i] through deck[n-1] (each card equally likely) and exchange it with deck[i]. Sampling without replacement.In many situations, we want to draw a random sample from a set such that each element in the set appears at most once in the sample. The program sample.py takes command-line arguments m and n and creates a permutation of size n whose first m elements constitute a random sample.Precomputed values.Another application of arrays is to save values that you have computed for later use. As an example, suppose that you are composing a program that performs calculations using small values of the harmonic numbers. An efficient approach is to save the values in an array, as follows:
Note that we waste one slot in the array (element 0) to make harmonic[1] correspond to the first harmonic number 1.0 and harmonic[i] correspond to the ith harmonic number. This method is not effective if we need values for huge n, but it is very effective if we need values for small n many different times. Simplifying repetitive code.As an example of another simple application of arrays, consider the following code fragment, which writes the name of a month given its number (1 for January, 2 for February, and so forth):
A more compact alternative is to use an array of strings holding the month names:
This technique would be especially useful if you needed to access the name of a month by its number in several different places in your program. Note that we intentionally waste one slot in the array (element 0) to make MONTHS[1] correspond to January, as required. Coupon collector.Suppose that you have a deck of cards and you pick cards at random (with replacement) one by one. How many cards do you need to turn up before you have seen one of each suit? That is an example of the famous coupon collector problem. In general, suppose that a trading card company issues trading cards with n different possible cards: how many do you have to collect before you have all n possibilities, assuming that each possibility is equally likely for each card that you collect? The program couponcollector.py is an example program that simulates this process. See the textbook for details.Sieve of Eratosthenes.The prime counting function π(n) is the number of primes less than or equal to n. For example π(17) = 7 since the first seven primes are 2, 3, 5, 7, 11, 13, and 17. Program primesieve.py takes a command line integer n and computes π(n) using the Sieve of Eratosthenes. See the textbook for details.Two-Dimensional ArraysIn many applications, a convenient way to store information is to use a table of numbers organized in a rectangular table and refer to rows and columns in the table. The mathematical abstraction corresponding to such tables is a matrix; the corresponding data structure is a two-dimensional array. Initialization.The simplest way to create a two-dimensional array is to place comma-separated one-dimensional arrays between matching square brackets. For example, this matrix of integers having two rows and three columnscould be represented in Python using this array of arrays:
We call such an array a 2-by-3 array. More generally, Python represents an m-by-n array as an array that contains m objects, each of which is an array that contains n objects. For example, this Python code creates an m-by-n array a[][] of floats, with all elements initialized to 0.0:
As for one-dimensional arrays, we use the self-descriptive alternative stdarray.create2D(m, n, 0.0) from our booksite module stdarray throughout this booksite. Indexing.When a[][] is a two-dimensional array, the syntax a[i] denotes a reference to its ith row. The syntax a[i][j] refers to the object at row i and column j. To access each of the elements in a two-dimensional array, we use two nested for loops. For example, this code writes each object of the m-by-n array a[][], one row per line.
This code achieves the same effect without using indices:
Matrix operations.Typical applications in science and engineering involve representing matrices as two-dimensional arrays and then implementing various mathematical operations with matrix operands. For example, we can add two n-by-n matrices a[][] and b[][] as follows:
Similarly, we can multiply two matrices. Each element c[i][j] in the product of a[][] and b[][] is computed by taking the dot product of row i of a[][] with column j of b[][].
Ragged arrays.There is actually no requirement that all rows in a two-dimensional array have the same length. An array with rows of nonuniform length is known as a ragged array. The possibility of ragged arrays creates the need for taking more care in crafting array-processing code. For example, this code writes the contents of a ragged array:
Note that the equivalent code that does not use indices works equally well with both rectangular and ragged arrays:
Multidimensional arrays.The same notation extends to allow us to compose code using arrays that have any number of dimensions. Using arrays of arrays of arrays..., we can create three-dimensional arrays, four-dimensional arrays, and so forth, and then refer to an individual element with code like a[i][j][k].Example: self-avoiding random walks.The program selfavoid.py is an application of two-dimensional arrays to chemistry. See the textbook for details.Q & AQ. Why do Python string and list indices start at 0 instead of 1? A. That convention originated with machine-language programming, where the address of an array element would be computed by adding the index to the address of the beginning of an array. Starting indices at 1 would entail either a waste of space at the beginning of the array or a waste of time to subtract the 1. Here's Edsger Dijkstra's explanation. Q. What happens if I use a negative integer to index an array? A. The answer may surprise you. Given an array a[], you can use the index -i as shorthand for len(a)-i. For example, you can refer to the last element in the array with a[-1] or a[len(a)-1] and the first element with a[-len(a)] or a[0]. Python raises an IndexError at run time if you use an index outside of the range -len(a) through len(a)-1. Q. Why does the slice a[i:j] include a[i] but exclude a[j]? A. The notation is consistent with ranges defined with range(), which includes the left endpoint but excludes the right endpoint. It leads to some appealing properties: j-i is the length of the subarray (assuming no truncation); a[0:len(a)] is the entire array; a[i:i] is the empty array; and a[i:j] + a[j:k] is the subarray a[i:k]. Q. What happens when I compare two arrays a[] and b[] with (a == b)? A. It depends. For arrays (or multidimensional arrays) of numbers, it works as you might expect: the arrays are equal if each has the same length and the corresponding elements are equal. Q. What happens when a random walk does not avoid itself? A. This case is well understood. It is a two-dimensional version of the gambler's ruin problem, as described in Section 1.3. Q. Which pitfalls should I watch out for when using arrays? A. Remember that creating an array takes time proportional to the length of the array. You need to be particularly careful about creating arrays within loops. Exercises
Creative Exercises
Is list a 1 dimensional array?You are right. The user first inputs a list, and I convert it to array. Python lists are one dimensional only.
What is 1D and 2D array?1D arrays are just one row of values, while 2D arrays contain a grid of values that has several rows/columns. 1D: 2D: An ArrayList is just like a 1D Array except it's length is unbounded and you can add as many elements as you need.
What are array items called?In computer science, array is a data type that represents a collection of elements (values or variables), each selected by one or more indices (identifying keys) that can be computed at run time during program execution. Such a collection is usually called an array variable or array value.
What is a dimensional array?An n-dimensional array N is defined to store material composition information for each point in the heterogeneous part (n is the space dimension of a material). From: Multi-Material 3D Printing Technology, 2021.
|