You get a bonus - 1 coin for daily activity. Now you have 1 coin

Choosing a method for implementing sparse array in C

Lecture



Method selection

When choosing one of the methods for representing a sparse array — using a linked list, binary tree, pointer array, or hashing — you must be guided by the requirements for speed and efficient use of memory. In addition, it is necessary to take into account how dense the sparse array will be filled.

If the logical array is filled very rarely, linked lists and binary trees are the most efficient in terms of memory usage, since they allocate memory only for those elements that are actually used. The links themselves require very little additional memory, which can usually be neglected. Representation in the form of an array of pointers involves the creation of the entire array of pointers, even if some elements are not used. In this case, the memory should not only fit the entire array, but also should remain free memory for the application. In some cases this can be a serious problem. You can usually estimate in advance the approximate amount of free memory and decide whether it is sufficient for your program. The hashing method takes an intermediate position between views using an array of pointers and a linked list or binary tree. Despite the fact that the entire primary array, even if it is not used, must be in memory, this array will still be smaller than the array of pointers.

If the logical array is filled fairly densely, the situation changes significantly. In this case, creating an array of pointers and hashing becomes more acceptable methods. Moreover, the search time for an element in the array of pointers is constant and does not depend on the degree of filling of the logical array. Although the search time for hashing is not constant, it is bounded above by some small value. But in the case of a linked list and a binary tree, the average search time increases as the array is filled. This should be remembered if access time is a critical factor.


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Structures and data processing algorithms.

Terms: Structures and data processing algorithms.