Sparse arrays

One of the most interesting programming tasks is the implementation of sparse arrays. A sparse array , or a sparse array (sparse array), is an array in which not all elements are used, available or needed at the moment. Sparse arrays are useful in cases where two conditions are met: the size of the array that is required by the application is large enough (perhaps more than the amount of available memory), and when not all elements of the array are used. Thus, a sparse array is usually a large, but rarely full array. As will be shown later, there are several ways to implement sparse arrays. But before proceeding to their consideration, let's pay attention to the problems that are solved using sparse arrays.

• Why are sparse arrays needed?
• Sparse array representation as a linked list
• Representation of a sparse array as a binary tree
• Representation of a sparse array as an array of pointers
• Hashing
• Method selection

Why are sparse arrays needed?

To understand why sparse arrays are needed, recall the following two facts:

• When describing a regular array in the C language, all the memory required to allocate the array is allocated immediately after its creation.
• Large arrays, especially multidimensional, can occupy huge amounts of memory.

The fact that the memory for an array is allocated when it is created means that the size of the largest array that you can describe in your program is limited (in particular) by the amount of available memory. If you need a larger array than the capacity of the computer allows, you will have to implement it in some other way. (For example, one or another form of virtual memory is usually used to work with completely filled large arrays.) Even if a large array is located in memory, creating it can significantly reduce the available system resources, since the memory occupied by a large array is not available for the rest of the program. and other processes running on the system. And this, in turn, may adversely affect the overall performance of the program or computer as a whole. In situations where not all elements of an array will be used, allocating memory for the entire array seems to be a particularly wasteful waste of system resources.

To get rid of the problems caused by the need for memory for large, rarely filled arrays, some techniques for working with sparse arrays were invented. All of them are characterized by one common feature: memory for array elements is allocated only when necessary. Therefore, the advantage of a sparse array is that it only requires as much memory as is needed to store only those elements that are actually used. In this case, the remaining memory can be used for other purposes. In addition, these techniques allow you to create very large arrays, the size of which is much larger than the size allowed by the system of ordinary arrays.

There are numerous examples of applications that require processing sparse arrays. Many of them are related to working with matrices or to scientific and engineering problems that are understandable only to experts in relevant fields. However, there is one very popular application in which a sparse array is usually used - a spreadsheet. Despite the fact that the matrix in the average spreadsheet is very large, at any given time only some of it is used. Formulas, values, and strings are stored in spreadsheet cells. When using a sparse array, memory for each element is allocated only when necessary. Since only a small part of the elements of the array are actually used, the whole of it (that is, the spreadsheet) seems very large, but it takes up the minimum necessary memory.

In this chapter, two terms will often be repeated: the logical array and the physical array . A logical array is an array that is thought of as existing in the system. For example, if a spreadsheet matrix has a size of 1`000x1`000, then the logical array implementing the matrix will also have a size of 1`000x1`000 - even though physically such an array does not exist in the computer. A physical array is an array that actually exists in computer memory. So, if only 100 elements of the spreadsheet matrix are used, then the memory required to store only these 100 elements is required to store the physical array. Sparse array processing methods, disclosed in this chapter, provide a link between logical and physical arrays.

Below are four different ways to create a sparse array: a linked list, a binary tree, an array of pointers, and hashing. Although the spreadsheet program is not fully developed, all examples focus on the spreadsheet matrix shown in Figure 2. 23.1. In this figure, element X is located in cell B2.

  --- A --- --- B --- --- C ---
 one
 2 X
 3
 four
 five
 6
 7
 .
 .
 . 

Fig. 23.1. Organizing a simple spreadsheet