Hello, everyone.
In this video, we start to learn the 12th chapter, Advanced Data Structure.
Actually, it consists of two parts. The first one is advanced linear structure.
We have some advanced tree structure.
Among advanced linear structure, we firstly look at multidimensional array.
In computer science, an array is a combination of some elements of fixed type.
And the amount of elements is fixed, too.
Thus we can use fixed-size area to store these regular data.
For a static array, we set its size at the time of declaration.
For a dynamic array, we can allocate memory according to runtime.
That are differences among different languages.
Multidimensional array can be regarded as extension of one-dimensional array.
In other words, a vector of a vector is a two-dimensional array.
Then if the elements of a array are two-dimensional arrays, it is three-dimensional array, and so on, we can define multidimensional array.
In several languages, we can define the upper and lower bounds of every dimension of a multidimensional array.
In some languages, the bounds doesn't need to be continuous integer, it can be arbitrary.
We combine the upper and lower bounds of every dimension to compute the size of the whole multidimensional array.
In fact, the storage in computer is all linear.
Let's see the diagram of the space of an array.
For a two-dimensional array, we can regard it as a plane table structure.
Every element of the array is a cell in the table.
The relation is like this.
If there is a three-dimensional array, you can regard it as a 3d vector.
In computer science, we would like to put the lower dimensional ones from top to bottom.
So it is such a structure. Then we look at the storage of array.
Because in a computer, we have to give it linear storage, the data can be put line by line, or raw by raw.
Actually, different languages manage it in different ways.
C and Pascal are line-major.
Line-major means that it put the data line by line.
Let's look at the change of the array index.
Actually, the index starts to change with the last dimension, while the former ones are fixed.
After this area complete, that area begins. We can see the next changed index is the second from the rightmost, and so on.
Other than line-major, there is another method of change.
We can see, for this array, the right indexes are fixed while the leftmost index changes firstly.
And then the second index, and so on.
Let's see the formula for storage location of an array.
As we know, all elements in an array are of the same type.
In other words, the size of storage is fixed, say d.
So for the whole array, its first elements are a[0][1], a[0][2], ..., up to a[0][n].
So I can obtain the storage location.
Actually, the head address of such an array, is the address of the first cell, a[0][0][0][0].
Then when we calculate the address of some element, say j1, j2, ..., jn, the indexes of each dimensions,
we can regard it like this.
That is, the address of every element can be computed by adding the head address by ds.
Its linear space of the whole array should also be taken into consideration.
Then, how should we regard that region? As I have divided it by line-major, the leftmost region changes firstly.
We divide it into several regions, the value of the first index decides a region that we should search firstly.
When we search element a[1][1][2], we skip a[0] region and get a[1] region.
So we add the head address by the size of that region, d2 * d3.
In that region, we find the Line 1.
In Line 1, we find the right row.
Then we add the address of the row by the two offsets.
We apply such a method to compute.
Firstly, divide the array into biggest regions by the first index.
Then divide the regions into subregions by the second index, and so on, until the last index.
Finally, we add the offsets.
There are some special matrix, such as diagonal matrix and symmetric matrix.
We can apply some special strategy to store sparse matrix.
Let's look at a lower triangle matrix.
A lower triangle matrix is related to a graph structure we mentioned before.
That is, we can use a lower or upper triangle matrix to store a undirected graph.
Of course it doesn't correspond to an undirected graph, because there are values in the matrix.
We can linearise the matrix.
The rule is that element (i, j) can be put in the position i * (i + 1) / 2 + j.
For a symmetric matrix, we just store half of the elements and the rest can be computed from it.
So we just store the lower triangle of the symmetric matrix.
Actually, the formula is the same as the formula of lower triangle matrix.
Only when i and j are different, we use different formulas to compute.
There are some other special matrix.
This matrix has three oblique line with value on them, and other elements are zero.
Also you can define other matrix, such as a five-oblique-line matrix.
They are also obeying some rule.
For these matrix, we can define some formula to compute the index.
For the special cases of sparse matrix, we usually have some special storage strategy.
A sparse matrix is a matrix that only few elements are not equal to zero.
As zeros are massive, if we store the original matrix, space and time are both waste.
Because it costs a lot of time to find the valuable element.
In practise, we regard a matrix as a sparse matrix when it has less than 5 percent non-zero elements.
For a sparse matrix, we only store the non-zero elements, and ignore the zeros.
An obvious implementation is the linked list.
An other implementation is triple.
In that implementation, we usually store a triple of (i, j, v), where i, j are the indexes of an element and v is the value of the element.
So it can clearly represent the structure of a matrix.
But this implementation is rarely used now.
In memory, the most common implementation of sparse matrix storage is the orthogonal list.
An orthogonal links the non-zero elements of each line and each row.
So every non-zero element is in either the line list and the row list.
For each element, we store its line index, row index and its value.
Further more, we should store the line and row pointers in each node.
So a node of orthogonal list has 5 fields at least.
It you want to search backwards, you should add two pointers more.
For the application of matrix multiplication, let's see how to work.
Assume that A[c1..d1][c3..d3] multiplies B[c3..d3][c2..d2], the index of the result is [c1..d1][c2..d2].
The classic algorithm of matrix multiplication has a three-layers loop.
The loop is to compute every element by multiplying corresponding elements in a line of A and a row of B and adding the results together.
Let's consider the case of sparse matrix.
For the c[0][0] in the result, it is computed by multiplying the 0th line of A by the 0th row of B.
The value of c[0][0] is 0, while c[0][1] is 6.
Other elements can be computed like that.
Assuming that A and B are both sparse.
In such case, we should apply a special algorithm to save time.
Let's analyse the time complexity.
If A is p * m and B is m * n, the result C is p * n.
The total time is (ta + tb) * p * n, where ta and tb are the number of non-zero elements in A and B respectively.
It's quite small if (ta + tb) is much smaller than m.
This is a simple example.
The sparse matrix is applied in abundant occasions of scientific computation.
For example, we are dealing with such a polynomial of one indeterminate.
We use a list to store the coefficients and find that most coefficients are zero.
In other words, it is sparse.
If we store the zeros, it is a waste of space.
So we can link the non-zero elements to a linked list.
In each node, we store the coefficient and exponent of it.
Thus we can represent a polynomial of one indeterminate.
Let's consider that how to represent a polynomial of multiple indeterminate.
In other words, there are items like y^k, z^j, and so on.
Taking those into consideration, how should we use matrix to represent?
How about using a sparse matrix to represent it?
In addition, orthogonal list can be applied to solve the problem of Sudoku.
In The Art of Programming, Knuth provided a perfect solution.
What is Sudoku?
The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid contains all of the digits from 1 to 9.
The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a unique solution. (wikipedia)
It is a simple game, just like scrabble that is played by older people.
How to use an orthogonal list to solve it?
Work out your own answer.
Thank you!