Chapter 15
One of the key elements in software design is to determine which data-structures are most appropriate for the problem at hand. Data-structures determine how information is stored and exchanged, and have a significant e ect on the overall cohesiveness, clarity, and e ciency of the program.
The C language provides pointers, arrays and structs as the basic facilities upon which powerful high-level data-structures may be created. (However, these data-structures are not specific to C, and may be implemented similarly in other programming languages.) In this chapter we examine several of the more common constructions, but we only scratch the surface of the great ensemble of existing data-structures. For more information, the interested reader is directed to a good algorithms and data-structures textbook.1 For simplicity, the implementations presented below are written for specific data-types; converting them to generic code is left as an exercise.
E ciency, in terms of execution speed, can be approached at two levels. One is to optimise the execution of a set of loops and expressions in a process of code tuning. These are small-scale optimisations, which attempt to replace expensive operations with faster ones. The following are common examples.
• Replace array indexing with pointer operations.
• Replace power-of-two integer multiplication and division with bitwise shift operations.
• Manually unroll loops to avoid the overhead of branching and conditional expression evaluation for each iteration.
• Move non-changing expressions outside of loops to avoid unnecessary re-evaluation.
• Replace functions with macros to avoid function-call overhead.
The gains for such adjustments are typically small, and often come at the price of considerable loss of code clarity. Also, many of these optimisations are performed automatically by modern compilers. In fact, manual code tuning may actually result in slower execution than the original (simpler) code as the more obscure operations might be less amenable to compiler optimisation. In general, small-scale code optimisation should be avoided until proven necessary. That is, the program should be written with a focus on correctness and clarity, and subsequently tested for bottlenecks using a
1 The texts [CLRS01] and [Sed98] are highly recommended. They give thorough coverage of the fundamental data-structures, and provide an entry point into the vast literature on more advanced and specialised data-structures. For those desiring a rigorous exposition, the seminal three-volume work of Knuth [Knu98a, Knu98b, Knu98c] is the standard reference.
profiler. A profiler is a software tool that measures where a program spends most of its time, and enables code tuning to be focused where it is actually needed. Finally, to ensure that tuning actually has the desired e ect, it is essential to measure the code segment execution time both before and after applying optimisations.
Some programmers pay too much attention to e ciency; by worrying too soon about little “optimizations” they create ruthlessly clever programs that are insidiously di cult to maintain. Others pay too little attention; they end up with beautifully structured programs that are utterly ine cient and therefore useless. Good programmers keep e ciency in context: it is just one of many problems in software, but it is sometimes very important [Ben00, page 87].
The second approach to e ciency concerns code organisation on a larger scale; it concerns the choice of algorithms and data-structures. These decisions tend to have a much greater e ect on program speed, often by orders-of-magnitude. The central concept in this approach is the property of time complexity, which is a measure of how long an algorithm will take to complete given a certain size input. Time complexity is usually expressed in terms of O-notation which, in essence, states an upper-bound on computation to within a constant factor. For example, to search for a particular item in an unordered array of n elements is a linear operation; it takes on average O(n) iterations to find the item (or to show that the item is missing). Informally, O(n) may be understood as meaning “to the order n” or “linear with respect to n”. Common time complexities encountered for collections of n items include constant time O(1), logarithmic time O(log n), linear time O(n), and quadratic time O(n2).
Aside. A third important factor with regard to e ciency is the e ect of the memory hierarchy on computation speed. Registers, caches, RAM, and virtual memory all incur di erent access penalties, with each lower level in the hierarchy often costing several orders-of-magnitude greater runtime than its predecessor. Di erent algorithms and data-structures have di erent memory interaction behaviours, and an algorithm that involves less instructions on paper may actually run significantly slower than another. Algorithms that exploit space optimisation, locality of reference, and other memory-friendly techniques are usually much faster than those that don’t. A thorough discussion of memory hierarchy issues is well beyond the scope of this text.
The simplest of all data-structures is the array. It is directly supported by the C language and defines a contiguous sequence of elements in memory. It groups together a set of variables of the same type, and permits iteration over the set. If an array is of fixed size, known at compile-time, it can be allocated on the stack, otherwise, its size may be determined at run-time and allocated on the heap via malloc(). The expandable vector (see Sections 9.5, 11.7, and 14.2.1) is a good example of an array whose size may be grown dynamically at run-time.
For an array of size n, to access or change the value of an array element is an O(1) operation. However, to insert or remove an element from the middle of an array is O(n), as the elements following that point must be shu ed along by one. A linear search of an array is O(n); a binary search of a sorted array is O(log n).
A linked-list is a set of nodes, where each node contains an item of data and a pointer to the next node in the list. Linked-lists come in two basic varieties: singly linked and doubly linked. The implementation of singly linked-lists is covered in Section 11.4, and so here we will present code for a doubly linked-list.
For simplicity, let the contained item be an integer. A list node is defined as
typedef struct List List;
struct List {
int item; /* Contained item. */
List *next; /* Pointer to next node in list. */
List *prev; /* Pointer to previous node in list. */
};
The following functions perform node insertion and deletion operations, which may be applied at any point along the list.
1 struct List *insert after(List *node, int item)
2 /* Add new item to the next position in the list after ’node’. Return pointer to new node. */
3 {
4/* Allocate memory for new node. */
5List *newnode = (List *) malloc(sizeof (List));
6if (newnode == NULL)
7 return NULL; /* allocation failed */
8
9 /* If list is not empty, splice new node into list. */
10 if (node) {
11 newnode->next = node->next;
12 newnode->prev = node;
13 node->next = newnode;
14 newnode->next->prev = newnode;
15 }
16 else { /* empty list, make new head node. */
17 newnode->next = NULL;
18 newnode->prev = NULL;
19 }
20
21 newnode->item = item;
22 return newnode;
23 }
24
25 void delete node(List *node)
26 /* Remove node and reconnect links on either side. */
27 {
28 if (node->prev) node->prev->next = node->next;
29 if (node->next) node->next->prev = node->prev;
30 free(node);
31 }
10–15 Given a pointer to a node already in the list, the new node is inserted in the position immediately following. Existing links are connected to the new node to e ectively splice it into the list.
16–19 However, if the node pointer passed to this function is NULL, it simply creates a new node with links in both directions pointing to NULL. That is, it creates a new list of length one.
28–30 To remove a node from a list, the nodes on either side are first connected together, and then the selected node is deleted. The if-statements check that the adjacent links were not NULL.
Insertion and removal of nodes from anywhere along a list is O(1), provided a pointer to the specified location is already available. Thus, linked-lists are a good choice if insertion/removal operations are frequent into the middle of a sequence. However, search along a list of size n is O(n), and so other data-structures (such as a sorted array) are preferred if the sequence is very long and searching is a common operation.
For simplicity, let the contained item be an integer. A list node is defined as
typedef struct List List;
struct List {
int item; /* Contained item. */
List *next; /* Pointer to next node in list. */
List *prev; /* Pointer to previous node in list. */
};
The following functions perform node insertion and deletion operations, which may be applied at any point along the list.
1 struct List *insert after(List *node, int item)
2 /* Add new item to the next position in the list after ’node’. Return pointer to new node. */
3 {
4/* Allocate memory for new node. */
5List *newnode = (List *) malloc(sizeof (List));
6if (newnode == NULL)
7 return NULL; /* allocation failed */
8
9 /* If list is not empty, splice new node into list. */
10 if (node) {
11 newnode->next = node->next;
12 newnode->prev = node;
13 node->next = newnode;
14 newnode->next->prev = newnode;
15 }
16 else { /* empty list, make new head node. */
17 newnode->next = NULL;
18 newnode->prev = NULL;
19 }
20
21 newnode->item = item;
22 return newnode;
23 }
24
25 void delete node(List *node)
26 /* Remove node and reconnect links on either side. */
27 {
28 if (node->prev) node->prev->next = node->next;
29 if (node->next) node->next->prev = node->prev;
30 free(node);
31 }
10–15 Given a pointer to a node already in the list, the new node is inserted in the position immediately following. Existing links are connected to the new node to e ectively splice it into the list.
16–19 However, if the node pointer passed to this function is NULL, it simply creates a new node with links in both directions pointing to NULL. That is, it creates a new list of length one.
28–30 To remove a node from a list, the nodes on either side are first connected together, and then the selected node is deleted. The if-statements check that the adjacent links were not NULL.
Insertion and removal of nodes from anywhere along a list is O(1), provided a pointer to the specified location is already available. Thus, linked-lists are a good choice if insertion/removal operations are frequent into the middle of a sequence. However, search along a list of size n is O(n), and so other data-structures (such as a sorted array) are preferred if the sequence is very long and searching is a common operation.
Data Structures
One of the key elements in software design is to determine which data-structures are most appropriate for the problem at hand. Data-structures determine how information is stored and exchanged, and have a significant e ect on the overall cohesiveness, clarity, and e ciency of the program.
The C language provides pointers, arrays and structs as the basic facilities upon which powerful high-level data-structures may be created. (However, these data-structures are not specific to C, and may be implemented similarly in other programming languages.) In this chapter we examine several of the more common constructions, but we only scratch the surface of the great ensemble of existing data-structures. For more information, the interested reader is directed to a good algorithms and data-structures textbook.1 For simplicity, the implementations presented below are written for specific data-types; converting them to generic code is left as an exercise.
15.1 E ciency and Time Complexity
E ciency, in terms of execution speed, can be approached at two levels. One is to optimise the execution of a set of loops and expressions in a process of code tuning. These are small-scale optimisations, which attempt to replace expensive operations with faster ones. The following are common examples.
• Replace array indexing with pointer operations.
• Replace power-of-two integer multiplication and division with bitwise shift operations.
• Manually unroll loops to avoid the overhead of branching and conditional expression evaluation for each iteration.
• Move non-changing expressions outside of loops to avoid unnecessary re-evaluation.
• Replace functions with macros to avoid function-call overhead.
The gains for such adjustments are typically small, and often come at the price of considerable loss of code clarity. Also, many of these optimisations are performed automatically by modern compilers. In fact, manual code tuning may actually result in slower execution than the original (simpler) code as the more obscure operations might be less amenable to compiler optimisation. In general, small-scale code optimisation should be avoided until proven necessary. That is, the program should be written with a focus on correctness and clarity, and subsequently tested for bottlenecks using a
1 The texts [CLRS01] and [Sed98] are highly recommended. They give thorough coverage of the fundamental data-structures, and provide an entry point into the vast literature on more advanced and specialised data-structures. For those desiring a rigorous exposition, the seminal three-volume work of Knuth [Knu98a, Knu98b, Knu98c] is the standard reference.
profiler. A profiler is a software tool that measures where a program spends most of its time, and enables code tuning to be focused where it is actually needed. Finally, to ensure that tuning actually has the desired e ect, it is essential to measure the code segment execution time both before and after applying optimisations.
Some programmers pay too much attention to e ciency; by worrying too soon about little “optimizations” they create ruthlessly clever programs that are insidiously di cult to maintain. Others pay too little attention; they end up with beautifully structured programs that are utterly ine cient and therefore useless. Good programmers keep e ciency in context: it is just one of many problems in software, but it is sometimes very important [Ben00, page 87].
The second approach to e ciency concerns code organisation on a larger scale; it concerns the choice of algorithms and data-structures. These decisions tend to have a much greater e ect on program speed, often by orders-of-magnitude. The central concept in this approach is the property of time complexity, which is a measure of how long an algorithm will take to complete given a certain size input. Time complexity is usually expressed in terms of O-notation which, in essence, states an upper-bound on computation to within a constant factor. For example, to search for a particular item in an unordered array of n elements is a linear operation; it takes on average O(n) iterations to find the item (or to show that the item is missing). Informally, O(n) may be understood as meaning “to the order n” or “linear with respect to n”. Common time complexities encountered for collections of n items include constant time O(1), logarithmic time O(log n), linear time O(n), and quadratic time O(n2).
Aside. A third important factor with regard to e ciency is the e ect of the memory hierarchy on computation speed. Registers, caches, RAM, and virtual memory all incur di erent access penalties, with each lower level in the hierarchy often costing several orders-of-magnitude greater runtime than its predecessor. Di erent algorithms and data-structures have di erent memory interaction behaviours, and an algorithm that involves less instructions on paper may actually run significantly slower than another. Algorithms that exploit space optimisation, locality of reference, and other memory-friendly techniques are usually much faster than those that don’t. A thorough discussion of memory hierarchy issues is well beyond the scope of this text.
15.2 Arrays
The simplest of all data-structures is the array. It is directly supported by the C language and defines a contiguous sequence of elements in memory. It groups together a set of variables of the same type, and permits iteration over the set. If an array is of fixed size, known at compile-time, it can be allocated on the stack, otherwise, its size may be determined at run-time and allocated on the heap via malloc(). The expandable vector (see Sections 9.5, 11.7, and 14.2.1) is a good example of an array whose size may be grown dynamically at run-time.
For an array of size n, to access or change the value of an array element is an O(1) operation. However, to insert or remove an element from the middle of an array is O(n), as the elements following that point must be shu ed along by one. A linear search of an array is O(n); a binary search of a sorted array is O(log n).
15.3 Linked Lists
A linked-list is a set of nodes, where each node contains an item of data and a pointer to the next node in the list. Linked-lists come in two basic varieties: singly linked and doubly linked. The implementation of singly linked-lists is covered in Section 11.4, and so here we will present code for a doubly linked-list.
For simplicity, let the contained item be an integer. A list node is defined as
typedef struct List List;
struct List {
int item; /* Contained item. */
List *next; /* Pointer to next node in list. */
List *prev; /* Pointer to previous node in list. */
};
The following functions perform node insertion and deletion operations, which may be applied at any point along the list.
1 struct List *insert after(List *node, int item)
2 /* Add new item to the next position in the list after ’node’. Return pointer to new node. */
3 {
4/* Allocate memory for new node. */
5List *newnode = (List *) malloc(sizeof (List));
6if (newnode == NULL)
7 return NULL; /* allocation failed */
8
9 /* If list is not empty, splice new node into list. */
10 if (node) {
11 newnode->next = node->next;
12 newnode->prev = node;
13 node->next = newnode;
14 newnode->next->prev = newnode;
15 }
16 else { /* empty list, make new head node. */
17 newnode->next = NULL;
18 newnode->prev = NULL;
19 }
20
21 newnode->item = item;
22 return newnode;
23 }
24
25 void delete node(List *node)
26 /* Remove node and reconnect links on either side. */
27 {
28 if (node->prev) node->prev->next = node->next;
29 if (node->next) node->next->prev = node->prev;
30 free(node);
31 }
10–15 Given a pointer to a node already in the list, the new node is inserted in the position immediately following. Existing links are connected to the new node to e ectively splice it into the list.
16–19 However, if the node pointer passed to this function is NULL, it simply creates a new node with links in both directions pointing to NULL. That is, it creates a new list of length one.
28–30 To remove a node from a list, the nodes on either side are first connected together, and then the selected node is deleted. The if-statements check that the adjacent links were not NULL.
Insertion and removal of nodes from anywhere along a list is O(1), provided a pointer to the specified location is already available. Thus, linked-lists are a good choice if insertion/removal operations are frequent into the middle of a sequence. However, search along a list of size n is O(n), and so other data-structures (such as a sorted array) are preferred if the sequence is very long and searching is a common operation.
For simplicity, let the contained item be an integer. A list node is defined as
typedef struct List List;
struct List {
int item; /* Contained item. */
List *next; /* Pointer to next node in list. */
List *prev; /* Pointer to previous node in list. */
};
The following functions perform node insertion and deletion operations, which may be applied at any point along the list.
1 struct List *insert after(List *node, int item)
2 /* Add new item to the next position in the list after ’node’. Return pointer to new node. */
3 {
4/* Allocate memory for new node. */
5List *newnode = (List *) malloc(sizeof (List));
6if (newnode == NULL)
7 return NULL; /* allocation failed */
8
9 /* If list is not empty, splice new node into list. */
10 if (node) {
11 newnode->next = node->next;
12 newnode->prev = node;
13 node->next = newnode;
14 newnode->next->prev = newnode;
15 }
16 else { /* empty list, make new head node. */
17 newnode->next = NULL;
18 newnode->prev = NULL;
19 }
20
21 newnode->item = item;
22 return newnode;
23 }
24
25 void delete node(List *node)
26 /* Remove node and reconnect links on either side. */
27 {
28 if (node->prev) node->prev->next = node->next;
29 if (node->next) node->next->prev = node->prev;
30 free(node);
31 }
10–15 Given a pointer to a node already in the list, the new node is inserted in the position immediately following. Existing links are connected to the new node to e ectively splice it into the list.
16–19 However, if the node pointer passed to this function is NULL, it simply creates a new node with links in both directions pointing to NULL. That is, it creates a new list of length one.
28–30 To remove a node from a list, the nodes on either side are first connected together, and then the selected node is deleted. The if-statements check that the adjacent links were not NULL.
Insertion and removal of nodes from anywhere along a list is O(1), provided a pointer to the specified location is already available. Thus, linked-lists are a good choice if insertion/removal operations are frequent into the middle of a sequence. However, search along a list of size n is O(n), and so other data-structures (such as a sorted array) are preferred if the sequence is very long and searching is a common operation.
No comments:
Post a Comment