数据结构的深入研究(一)

作者：Scott Mitchell

时间：2003年11月

摘要：这篇文章是关注重要的数据结构及它们的应用的系列文章的开始。该系列文章一共分六部分。我们将研究.NET Framework中内建的数据结构和我们自己创建的数据结构。第一部分我们主要关注数据结构是什么，如何有效地分析数据结构和为什么这样的分析是重要的。在这篇文章中，我们将研究在.NET Framework中常用的两种数据结构：Array和ArrayList。

 

前言：

欢迎进入系列文章的第一部分：在.NET中使用数据结构。虽然在这个系列文章中，我们将研究不同的数据结构，一些包含在.NET Framework基础类库中，还有一些我们自己创建的数据结构。如果你不熟悉“数据结构”术语，我简单介绍一下。数据结构是抽象的结构或类，用于组织数据并提供在数据上的不同操作。最常用、或许是最有名的数据结构是数组，它包含通过索引访问的连续的数据集。

         在进入文章的内容之前，让我简单介绍一下共分六部分的文章系列，对它有个整体的了解。如果你认为有任何主题是错误的，请你发Mail给我:[email protected],共享你的想法。只要有空，我将非常高兴将你的建议增加到文章的适当部分，如果有必要，我可以在该系列中增加第七部分。

         在该系列文章的第一部分，我们将了解一下为什么数据结构是重要的，以及它对算法性能的影响。为了确定数据结构对性能的影响，我们需要仔细分析一个数据结构完成的不同操作。最后我们将关注.NET Framework中的两种数据结构：Array和ArrayList。也许你在做过的项目已经用过这两种数据结构。在这篇文章中，我们将研究它提供什么样的操作以及这些操作的效率。

         在第二部分，我们将更深入地研究ArrayList类以及和它类似的Queue和Stack类。和ArrayList一样，Queue和Stack类存储连续的数据集合并存在于.NET Framework基础类库中。然而，不像ArrayList可以随意地访问任何数据项，Queue和Stack只允许数据以预先确定的连续的顺序访问。我们将研究一些使用Queues和Stacks的应用程序，并通过扩展ArralyList类来实现这两个类。在研究Queues和Stacks之后，我们将了解一下HashTables，它允许像ArrayList一样直接访问，但通过字符串关键字进行索引。

         ArrayLists适合于直接访问与存储数据，但它并不适合存储需要被搜索的数据。在第三部分，我们将研究binary search tree数据结构，它提供比ArrayList更有效的搜索方法。.NET　Framework不提供内建的binary search tree数据结构，我们不得不自已创建。

         搜索一个binary search tree的效率与数据插入到树中的次序有关。如果数据按排序或就近排序的顺序插入，binary search tree将失去所有的与ArrayList相比效率上的优点。为了解决这个问题，在第四部分，我们将研究有趣的随机的数据结构－SkipList。SkipList可以高效地搜索一个binary search tree,而不受到数据插入顺序的影响。

         在第五部分，我们将关注表现图的数据结构。一个图是节点的集合，并带有连接不同节点的边线。例如，一个地图可以用图形象化地表示，城市用节点表示，高速公路用节点之间的边线表示。许多真实世界的问题都可以图来抽象地定义，所以图是一种常用的数据结构。

         最后，在第六部分我们将讨论表示集合和不相交集合的数据结构。一个集合是数据的无次序的聚集。不相交的集合是任何两个集合之间没有公共的元素的集合。这两种集合在程序经常使用，我们将在最后的部分详细介绍它们。

 

分析数据结构的性能

         当考虑一个特定的应用程序或编程问题时，许多开发者(包含我)的乐趣在于通过自己编写算法解决遇到的问题，或者通过为应用程序增加cool的特性来增强用户体验。你很少听说有人因为他们使用的数据结构而兴奋。然而，对于一定特定的算法来说，不同的数据结构会对性能产生很大的影响。一个通常的例子是在一个数据结构中寻找一个元素。对于数组来说，这个查找需要的时间与查找元素的数量成正比。对于binary search trees或SkipLists来说，当搜索大量数据时，花费的时间是次线性的。数据结构的选择会影响到应用程序性能的好坏。

         既然算法使用的数据结构会对算法的性能产生很大的影响，那么关键的是要有一种严格的方法来比较不同数据结构的效率。对于使用数据结构的开发者来说，主要感兴趣的是当存储的数据数量增加时数据结构的性能如何变化。也就是说，在数据结构中每增加一个新的元素，会对数据结构的操作运行时间产生多大的影响？

         考虑这样一个情况，你有一个程序，用System.IO.Directory.GetFiles(path)方法返回用字符串数组存储的一个特定目录中的文件列表。现在，假如你想通过搜索这个数组去发现文件列表中存在的XML文件(即扩展名是.xml的文件)。一种方法是检查整个数组，在遇到XML文件时设置一些标志。程序代码如下：

using System;

using System.Collections;

using System.IO;

 

public class MyClass

{

   public static void Main()

   {

      string [] fs = Directory.GetFiles(@"C:\Inetpub\wwwroot");

      bool foundXML = false;

      int i = 0;

      for (i = 0; i < fs.Length; i++)

         if (String.Compare(Path.GetExtension(fs[i]), ".xml", true) == 0)

         {

            foundXML = true;

            break;

         }

  

     if (foundXML)

        Console.WriteLine("XML file found - " + fs[i]);

     else

        Console.WriteLine("No XML files found.");

     

   }

}

 

         我们先看一下最坏的情况，当文件列表中没有XML文件或XML文件是最后一个文件，我们不得不搜索整个数组的每个元素。为了按一定的顺序分析数组的效率，我们必须问自己“假设有一个n个元素的数组。如果增加另外一个元素，这个数组就有n+1元素，那增加元素后的新的运行时间是多少？”(术语“运行时间”，并不是度量程序运行的绝对时间，而是表示程序完成指定任务的步骤数。当使用数组时，典型的步骤数是需要完成多少次数组访问。)为了在数组中搜索一个值，我们需要访问每一个数组值，所以如果我们有n+1个数组元素，我们必须检查n+1个元素。也就是说，搜索一个数组的花费的时间与数组中的元素数量成正比。

         这种分析方法被称为渐近分析，即当数据结构中的数据数量接近无穷大时，数据结构的效率如何变化。在渐近分析中常用的符号表示法是big-Oh。在big-Oh中用O(n)表示搜索一个数组的性能。大写字母O是big-Oh符号中的专用符号。n表示搜索数组的操作步骤数，它随着数组的增大而线性地增加。

         计算一个代码段的渐近运行时间，更系统的方法请遵循下面的步骤：

1.          确定组成算法运行时间的步骤。如前所述的数组，被考虑的步骤应该是对数组的读写访问。其他的数据结构也许不同。你不能简单地认为数据结构中包含的操作步骤就是计算机完成的原子操作。也就是说，对于上面的代码段，我分析它的运行时间时，只计算访问数组的操作的次数，而不关心创建和初始化变量以及比较字符所用的时间。

2.          找到你用于计算运行时间的代码行。在那些代码行后标一个1。

3.          对于那些标了1的代码行，看看是否处在一个循环中。如果是这样，将1改为循环的最高计数。如果有两个或更多的嵌套循环，则将每个循环的计数相乘。

4.          找到你写下的最大的一个值，这就是运行时间。

让我们在上面的代码段中使用这些步骤。我们已经标出我们感兴趣的步骤，也就是数组访问操作，第一步工作已经完成。进入第二步，注意访问数组fs的两行代码：在String.Compare()和Console.WriteLine()方法中fs数组被作为参数，所以在每行标上一个1。现在，进入第3步，在循环中，String.Compare()访问fs的次数最高为n次(n是数组的大小)。因此，擦掉循环中的1并改为n。最后，我们发现最大值是n,所以运行时间用O(n)表示。

O(n)或者叫线性时间，表现了无数种渐近运行时间中的一种。其他的包含O(log2 n), O(n log2 n), O(n2), O(2n)等等。当n值增大时，括号中表达式的值越小，则数据结构的性能越好。例如:运行在O(log n)上的操作的效率比运行在O(n)上的高，因为log n<n。

 

注意：在这里，你需要复习一下数学知识。Loga b=y的另一种表示方法是a^y=b。所以，Log₂ 4=2，因为2²=4。同样地，Log₂ 8=3，因为2³=8。很明显，Log₂ n的增长速度比单独的n慢得多，因为当n=8, Log₂ n=3。在第三部分我们将研究binary search trees，它的搜索操作只花费O(Log₂ n)的运行时间。

 

通过该系列文章，我们将计算每个新的数据结构的操作的渐近运行时间，并比较不同数据结构中类似操作的运行时间。

 

大家熟悉的、线性的、直接访问的、存储同类型数据的数据结构－数组

数组是计算机程序中最简单和最广泛使用的数据结构。在任何编程语言中，数组都拥有一些共同特性：

l          数组中的数据内容存储在连续的内存空间中

l          数组中的所有元素都是相同的类型；所以数组被称为同类数据结构。

l          数组元素可以被直接访问。(许多其他的数据结构不是这样的。例如：在这个系列文章的第四部分，我们将研究SkipList数据结构。为了访问SkipList的每个元素，你必须通过其他元素去搜索你要找的元素。对于数组来说，无论何时，如果你想要访问数组中的一个元素，你只要简单地使用这样的代码：arrayName[i]。)

在数组上进行的常用操作：

l          分配空间

l          访问元素

l          改变大小

在C#中，当你初次申明一个数组时，它被赋与一个null值。例如，下面的代码简单地创建一个变量booleanArrary,它的值等于null:

bool [] booleanArray;

在我们使用数组之前，我们必须分配一定数目的元素。通过下面的语法实现：

booleanArray = new bool[10];

或都更通用的表示：

ArrayName = new arrayType[allocationSize];

这样会在CLR－managed堆中分配足够大的连续的内存块用于保存allocationSize数目的arrayTypes。如果arrayType是值类型，allocationSize数目的unboxed arrayType值被创建。如果arrayType是引用类型，allocationSize数目的arrayType引用被创建。(如果你不熟悉引用类型与值类型，以及managed heap与stack之间的区别，你参考Understanding .NET's Common Type System)

为了帮助理解.NET Framework如何存储数组的内部数据,请考虑下面的例子:

         bool [] booleanArray;

         FileInfo [] files;

         booleanArray = new bool[10];

         files = new FileInfo[10];

         这里,booleanArray是一个值类型System.Boolean的数组,而fies数组是引用类型数组.。图1显示了在这四行代码执行后CLR-managed堆的分配情况。

 

图1在managed heap中数组内容在内存中的连续分布

 

值得注意的是在files数组中10个元素是对FileInfo实例的引用。图2显示了如果我们将FileInfo实例分配给files数组中的一些元素后内存的分布情况：

 

图2在managed heap中数组内容在内存中的连续分布

 

在.NET中所有的数组都允许读和写。访问数组元素的语法是：

// Read an array element

bool b = booleanArray[7];

 

// Write to an array element

booleanArray[0] = false;

 

一个数组访问的运行时间用O(1)表示，因为它是一个常量。也就是说，无论在数组中存储了多少元素，寻找一个元素都是花费同样的时间。数组运行时间之所以不变，是因为数组元素是连续地存储的，因而寻找一个元素仅需要知道数组在内存中的开始位置、每个数组元素占用的内存大小、和元素的索引。

在managed code中，数组的查找比这稍微复杂点，因为对于每次数组访问，CLR都进行检查，以保证请求的索引都在数据的范围之内。如果指定的数组索引超出范围，将产生一个IndexOutOfRangeException异常。这个检查保证当我们遍历数组时不超过数组的最大索引而进入其他的内存区。但是，这个检查并不会影响数组的运行时间，因为完成检查所需的时间不会随着数组增大而增加。

 

注意：在进行一些大量的数组访问，索引绑定检查带来少量的性能消耗。对于一些unmanaged code，索引越界检查能被跳过。想了解更多的信息，请参考第14章Applied Microsoft .NET Framework Programming by Jeffrey Richter.

 

使用数组时，你也许需要改变数组的大小。为了这样做，你将需要创建新的数组实例并将旧的数组的内容复制到新的数组中。这个过程被称redimensioning，通过下面的代码实现：

using System;

using System.Collections;

public class MyClass

{

   public static void Main()

   {

      // Create an integer array with three elements

      int [] fib = new int[3];

      fib[0] = 1;

      fib[1] = 1;

      fib[2] = 2;

      // Redimension message to a 10 element array

      int [] temp = new int[10];

// Copy the fib array to temp

      fib.CopyTo(temp, 0);

      // Assign temp to fib

      fib = temp;  

   }

}

在执行完最后一行代码后，fib引用了一个包含10个Int32数据的数组。第3至第9个元素的值是缺省的int32值0。

 

数组适合于存储同类型的仅需要直接访问的数据集合。搜索一个没有排序的数组会花费线性的运行时间。当使用小的数组或进行很少的搜索时，这是可接受的。如果你的应用程序存储经常需要搜索的很大的数组，有一些其他的数据结构会更好的满足你的要求。我们将在该系列文章的以后的部分讨论这样的数据结构。(如果你通过一些属性搜索一个数组并且数据通过属性排序，你可以使用一个被称为binary search的算法，它搜索一个数组只要花费O(log n)运行时间，这和搜索binary search trees时间是一样的。事实上，Array类包含一个静态的BinarytSearch()方法。想了解这个方法的更多信息，请参考我以前的文章,Efficiently Searching a Sorted Array。

注意：.NET framework也支持多维数组。多维数组和一维数组一样，访问元素花费一个不变的运行时间。搜索一个n个元素的一维数组所需的时间用O(n)表示。对于nxn个元素的二维数组，运行时间用O(n²)表示，因为搜索必须检查n²个元素。一般情况下，一个k维数组有一个O(n^k)搜索时间。

 

ArrayList:存储异类数据的、Self-Redimensioning的数组

 

数组在设计上有一些限制，因为数组只能存储同一种类型的元素，使用数组时你必须指定元素的数目。然而很多时候，开发者希望能灵活方便地管理不同类型的对象的简单集合，而不用担心内存分配问题。.NET Framework提供了这样的数据结构，即System.Collections.ArrayList。下面的代码片断说明了任何类型的元素都可以被加入ArrayList。而且，我们不必关心ArrayList大小的改变。所有的处理都在后台自动完成。

ArrayList countDown = new ArrayList();

countDown.Add(5);

countDown.Add(4);

countDown.Add(3);

countDown.Add(2);

countDown.Add(1);

countDown.Add("blast off!");

countDown.Add(new ArrayList());

 

在后台ArrayList使用object类型的System.Array。既然所有的类型都直接地或者间接地从object继承，一个object数组就能保存任何类型的元素。缺省情况下，ArrayList创建一个16个元素的object数组，通过ArrayList构造函数的一个参数或Capacity属性，可以指定ArrayList的大小。当通过Add()方法增加一个元素时，内部数组元素的个数应该符合数组的容量。如果增加一个新的元素而超过数组的容量,它的容量会自动增加一倍,数组的大小就会被改变。

ArrayList，和数组一样，用同样的语法直接进行索引：

// Read access

int x = (int) countDown[0];

string y = (string) countDown[5];

 

// Write access

countDown[1] = 5;

 

// ** WILL GENERATE AN ArgumentOutOfRange EXCEPTION **

countDown[7] = 5;

 

既然ArrayList是存储对象的数组，当从ArrayList读取值时，需要显式地转换为在指定位置的存储时的数据类型。而且，如果你引用一个元素超出了ArrayList的范围，会产生System.ArgumentOutOfRange异常。

ArrayList比标准的数组提供了更大的灵活,但也带来了性能上的牺牲。特别是在ArrayList中存储值类型。我们记得一个值类型(比如System.Int32, System.Double, System.Boolean等等)的数组在managed堆中以拆箱的方式连续地存储。ArrayList是一个存储对象引用的数组。所以,即使你用ArrayList只存储值类型,每个ArrayList元素也是一个装箱的值类型的引用,如图3

图3 ArrayList包含一个对象引用的连续内存存储块

当你在应用程序中使用数据量大的ArrayList并频繁进行读写操作时，装箱与拆箱操作会影响程序的性能。图3说明了ArrayList与数组在使用引用类型时，内存布局是相同的。

和数组相比，ArrayList不会因为它的self-redimensioning而引起任何性能上的影响。如果你知道被存储在ArrayList中的元素的准确数量，你可以通过在ArrayList的构造函数中指定初始容量而关闭self-redimensioning。对于数组，如果你不知道数组准确的大小，当插入的元素数量超过数组的大小时，你不得不手动改变数组的大小。

一个经典的计算机科学问题是如果程序运行时超出了缓存中的空间，应该分配多少新的空间。一个选择就是改变数组的大小，以便在新的数组中存储更多的元素。也就是说，如果数组在初始时分配了5个元素，在第六个元素插入之前，将数组的大小改变为能存储六个元素。很明显，这种方法能节省很多内存，但是在第一次改变数组大小(redimensioning)后，以后每次插入元素都需要改变数组大小，这对性能的影响很大。

另一种选择就是在改变数组大小时，将数组的大小变为原来的100倍。也就是说，如果数组在初始时分配了5个元素，在第六个元素插入之前，将数组的大小改变为500个元素。很明显，这种方法减少了改变数组大小的次数，但如果只有少量的元素需要插入，这样做会产生几百个无用的元素，浪费了空间。

解决这个问题有一个可靠的、正确的折衷方法，就是当空余空间被耗尽时，将数组的大小增加为原来的两倍。所以，对于一个初始分配了5个元素的数组，增加第6个元素将导致数组大小变为10。这正是ArrayList使用的方法。这是一种最佳的方案，它为你做了一切。

ArrayList的渐近运行时间与标准数组是相同的。即使ArrayList工作在高开销的情况下，特别是存储值类型时，元素数量与每个操作所耗费的时间之间的关系与标准数组也是相同的。

 

小结：

    这篇文章通过说明为什么研究数据结构是重要的来开始我们关于数据结构的讨论，并提供了一些方法来分析数据结构的性能。这篇文章也告诉你，当你在编程时，遇到应该采用哪种数据结构的问题时，分析在不同数据结构上进行操作的运行时间是一种有效的方法。在研究了如何分析数据结构后，我们研究了.NET Framework基础类库中最普通的两个数据结构－System.Array类和System.Collections.ArrayList类。数组在内存中以连续的空间存储同类型的数据。它们主要的优点是快速地读写数组元素。它们的缺点是在搜索数组时，每个数组元素都要被访问(在不排序的数组中)。

     ArrayList提供了一种更灵活的类似数组的数据结构。与普通数组只能存储同类型数据相比，ArrayList通过使用对象数组可以存储不同类型的数据。而且，ArrayList在增加更多的元素时，不需要显式地进行内存分配，它的大小会自动地随着元素的增加而增加。

     在该系列文章的下一篇，我们将探讨Stack和Queue类。我们也将讨论associative arrays,该数组通过字符串关键字进行索引而不是整数。associative arrays在.NET Framework基础类库中的Hashtable类中实现。

本文地址：http://com.8s8s.com/it/it45272.htm