s_cm2.htm
来自「Data Structure Ebook」· HTM 代码 · 共 138 行
HTM
138 行
<html>
<body bgcolor="#ffffff">
<p align=right>
<a href="s_man.htm" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_man.htm" target="_top"><img src="c_man.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/c_man.gif" width=74 height=19 border=0></a>
</p>
<h1>Comparison</h1>
We have seen several ways to construct dictionaries: hash tables,
unbalanced binary search trees, red-black trees, and skip lists.
There are several factors that influence the choice of an algorithm:
<ul>
<li> <i>Sorted output</i>. If sorted output is required, then hash tables
are not a viable alternative. Entries are stored in the table
based on their hashed value, with no other ordering. For binary
trees, the story is different. An in-order tree walk will
produce a sorted list. For example:
<blockquote><b><pre>
void WalkTree(Node *P) {
if (P == NIL) return;
WalkTree(P->Left);
/* examine P->Data here */
WalkTree(P->Right);
}
WalkTree(Root);
</pre></b></blockquote>
To examine skip list nodes in order, simply chain through the
level-0 pointers. For example:
<blockquote><b><pre>
Node *P = List.Hdr->Forward[0];
while (P != NIL) {
/* examine P->Data here */
P = P->Forward[0];
}
</pre></b></blockquote>
<li> <i>Space</i>. The amount of memory required to store a value should
be minimized. This is especially true if many small nodes are to
be allocated.
<p>
<ul>
<li> For hash tables, only one forward pointer per node is
required. In addition, the hash table itself must be allocated.
<p>
<li> For red-black trees, each node has a left, right, and parent
pointer. In addition, the color of each node must be recorded.
Although this requires only one bit, more space may be allocated
to ensure that the size of the structure is properly aligned.
Therefore each node in a red-black tree requires enough space for 3-4
pointers.
<p>
<li> For skip lists, each node has a level-0 forward pointer. The
probability of having a level-1 pointer is 1/2. The probability
of having a level-2 pointer is 1/4. In general, the number of
forward pointers per node is
<center><p>
<i>n</i> = 1 + 1/2 + 1/4 + ... = 2.
</center><p>
</ul>
<li> <i>Time</i>. The algorithm should be efficient. This is especially
true if a large dataset is expected.
Table 3-2 compares the
search time for each algorithm. Note that worst-case behavior
for hash tables and skip lists is extremely unlikely. Actual
timing tests are described below.
<p>
<li> <i>Simplicity</i>. If the algorithm is short and easy to understand,
fewer mistakes may be made. This not only makes <em>your</em> life easy,
but the maintenance programmer entrusted with the task of making
repairs will appreciate any efforts you make in this area. The
number of statements required for each algorithm is listed in
Table 3-2.
</ul>
<center>
<p><a name="Tbl3-2"></a>
<table border cellspacing=0 cellpadding=3>
<caption align=bottom> <h3>Table 3-2: Comparison of Dictionaries</h3> </caption>
<tr align=center><th>method</th><th>statements</th><th>average time</th><th>worst-case time</th></tr>
<tr align=center> <td align=left>hash table</td><td>26</td> <td><b><i>O</i></b>(1)</td> <td><b><i>O</i></b>(<i>n</i>)</td>
<tr align=center> <td align=left>unbalanced tree</td><td>41</td> <td><b><i>O</i></b>(lg <i>n</i>)</td> <td><b><i>O</i></b>(<i>n</i>)</td>
<tr align=center> <td align=left>red-black tree</td><td>120</td> <td><b><i>O</i></b>(lg <i>n</i>)</td> <td><b><i>O</i></b>(lg <i>n</i>)</td>
<tr align=center> <td align=left>skip list</td><td>55</td> <td><b><i>O</i></b>(lg <i>n</i>)</td> <td><b><i>O</i></b>(<i>n</i>)</td>
</table>
</center>
Average time for insert, search, and delete operations on a
database of 65,536 (2<sup>16</sup>) randomly input items may be found in
Table 3-3.
For this test the hash table size was 10,009 and 16
index levels were allowed for the skip list. Although there is some
variation in the timings for the four methods, they are close
enough so that other considerations should come into play when
selecting an algorithm.
<center>
<p><a name="Tbl3-3"></a>
<table border cellspacing=0 cellpadding=3>
<caption align=bottom> <h3>Table 3-3: Average Time (µs), 65536 Items, Random Input</h3> </caption>
<tr align=center><th>method</th><th>insert</th><th>search</th><th>delete</th></tr>
<tr align=right> <td align=left>hash table</td> <td>18</td> <td>8</td> <td>10</td>
<tr align=right> <td align=left>unbalanced tree</td> <td>37</td> <td>17</td> <td>26</td>
<tr align=right> <td align=left>red-black tree</td> <td>40</td> <td>16</td> <td>37</td>
<tr align=right> <td align=left>skip list</td> <td>48</td> <td>31</td> <td>35</td>
</table>
</center>
Table 3-4 shows the average search time for two sets of data:
a random set, where all values are unique, and an ordered set,
where values are in ascending order. Ordered input creates a
worst-case scenario for unbalanced tree algorithms, as the tree
ends up being a simple linked list. The times shown are for a
single search operation. If we were to search for all items in a
database of 65,536 values, a red-black tree algorithm would take
.6 seconds, while an unbalanced tree algorithm would take 1 hour.
<center>
<p><a name="Tbl3-4"></a>
<table border cellspacing=0 cellpadding=3>
<caption align=bottom> <h3>Table 3-4: Average Search Time (µs)</h3> </caption>
<tr align=left><th rowspan=5>random<br>input</th><th>count</th><th>hash table</th><th>unbalanced tree</th><th>red-black tree</th><th>skip list</th></tr>
<tr align=right> <td>16</td> <td>4</td> <td>3</td> <td>2</td> <td>5</td>
<tr align=right> <td>256</td> <td>3</td> <td>4</td> <td>4</td> <td>9</td>
<tr align=right> <td>4,096</td> <td>3</td> <td>7</td> <td>6</td> <td>12</td>
<tr align=right> <td>65,536</td> <td>8</td> <td>17</td> <td>16</td> <td>31</td>
<tr align=right> <td rowspan=4><b>ordered<br>input</b></td> <td>16</td> <td>3</td> <td>4</td> <td>2</td> <td>4</td>
<tr align=right> <td>256</td> <td>3</td> <td>47</td> <td>4</td> <td>7</td>
<tr align=right> <td>4,096</td> <td>3</td> <td>1,033</td> <td>6</td> <td>11</td>
<tr align=right> <td>65,536</td> <td>7</td> <td>55,019</td> <td>9</td> <td>15</td>
</table>
</center>
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?