ArrayList排序方法

Question

一位朋友和我正在编写一些软件（作为一个侧面项目），并且在ArrayLists中遇到了问题。

我们将自定义对象（包含DateTime和两个字符串）的实例的集合存储在ArrayList中。一旦我们将所有条目存储在ArrayList中，我们就按照DateTime对它们进行排序。问题是，我们必须存储100,000个对象实例，这意味着内置的排序方法需要很长时间 - 我们在一个小时内为其定点了一次。

排序的速度并不是什么大问题，但我只是想知道是否有更好的方法来对ArrayList中的元素进行排序，而不是使用内置排序方法。虽然我猜不是，基于这样一个事实，即内置.net的东西将会被高度优化。

注意：由于我们选择用于生成PDF报告的中间件，因此基于ArrayList的内容，我们使用ArrayLists。我想，如果我们有机会转到名单<>那么排序方法会更好。或者他们会？

编辑：

根据对源代码的要求，我会发布一些。但我不确定我能提供多少不明显。

public class DataObject : ICompareable 
{ 
    private DateTime timeStamp; 
    private string description; 
    private string detail; 

    public DataObject (DataTime inTimeStamp, string inDescription, 
         string inDetail) 
    { 
     this.timeStamp = inTimeStamp; 
     this.description = inDescription; 
     this.detail = inDetail; 
    } 

    int IComparable.CompareTo(object that) 
    { 
     DataObject myThat = (DataObject)that; 
     return this._timestamp.CompareTo(myThat._timestamp); 
    } 
} 

// .... // 

ArrayList dataList = new ArrayList(); 
for (int i = 0; i < database.Packets.Count; i++) 
{ 
    dataList.Add(new DataObject(database.Packet(i).GetTimeStamp(), 
       database.Packet(i).GetDescription(), 
       database.Packet(i).GetDetail()); 
} 

// ... same as the above, but for other data 
// ... types (all parse to strings when pulled 
// ... from the database 

dataList.Sort(); 

就是这样，很大程度上。我们从SQLCEME3.5数据库（我们使用.net 3.5，因此我们不能使用LINQ）中的几个地方提取数据，将它们放在一个ArrayList对象中，并使用该对象ArrayList进一步放在管道中。

我们希望从数据库中的多个位置获取所有记录（一些是数据包，一些是字符串（提示），一些是其他类型，全部解析为字符串）并按时间戳排序。我们希望散布的所有数据 - 一个数据包后跟一些字符串值，然后是一些对象值，如果这是它们的存储/提升顺序。

我们对数据库拥有只读访问权限，所以我不会不认为使用数据库本身对它们进行排序将是一个好主意（甚至可能）。话虽如此，我对SQL很陌生 - 在此项目之前从未使用它。可以这样做吗？

Answer 1

您的问题可能在其他地方，或者您发布的代码不是准确表示运行的内容。或者，也许您的数据处于非常糟糕的状态，导致Sort发生最坏情况的行为。我发现最后几乎不可能。

这是我的测试程序，它将您的DataObject实例中的100,000个添加到ArrayList，然后调用Sort。它在我的机器上执行时间少于50毫秒。

请注意，这是.NET 4.5，而不是3.5。但是，我无法想象这种情况在早期版本中如此可怕。

public class DataObject : IComparable 
{ 
    private DateTime timeStamp; 
    private string description; 
    private string detail; 

    public DataObject(DateTime inTimeStamp, string inDescription, 
         string inDetail) 
    { 
     this.timeStamp = inTimeStamp; 
     this.description = inDescription; 
     this.detail = inDetail; 
    } 

    public int CompareTo(object that) 
    { 
     DataObject myThat = (DataObject)that; 
     return this.timeStamp.CompareTo(myThat.timeStamp); 
    } 
} 

public class Program 
{ 
    private static void Main(string[] args) 
    { 
     // Create an ArrayList with DataObject items. 
     const int NumItems = 100000; 

     // The items get random time stamps within the last year 
     DateTime endDate = DateTime.Now; 
     DateTime baseDate = endDate.AddYears(-1); 
     int secondsRange = (int)((endDate - baseDate).TotalSeconds); 
     Random rnd = new Random(); 

     Console.WriteLine("Adding {0} items to list.", NumItems); 
     ArrayList dataList = new ArrayList(); 
     for (int i = 0; i < NumItems; ++i) 
     { 
      DateTime ts = baseDate.AddSeconds(rnd.Next()); 
      DataObject item = new DataObject(ts, "Foo", "bar"); 
      dataList.Add(item); 
     } 
     Console.Write("Sorting list..."); 
     Stopwatch sw = Stopwatch.StartNew(); 
     dataList.Sort(); 
     sw.Stop(); 
     Console.WriteLine("done!"); 
     Console.WriteLine("Elapsed time {0} ms", sw.ElapsedMilliseconds); 
     Console.ReadLine(); 
    } 
} 

Answer 2

如果你的数据是TimeStamp那么这是一个实现。

在200毫秒内对100,000行进行排序。
它必须做很多排序。
你的代码有问题。

namespace TimeStamp 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      string connString = "data source=... size=4096"; 
      ArrayList al = new ArrayList(); 
      using (SqlConnection sqlCon = new SqlConnection(connString)) 
      {    
       sqlCon.Open(); 
       SqlCommand sqlCmd = sqlCon.CreateCommand(); 
       sqlCmd.CommandText = "SELECT [timestamp], [value] FROM [TimeStmp] Order By [timestamp] desc"; 
       SqlDataReader rdr = sqlCmd.ExecuteReader(); 
       while (rdr.Read()) 
       { 
        // al.Add(new ValueWithTimeStamp(rdr.GetSqlBinary(0), rdr.GetString(1))); 
        for (int i = 0; i < 10000; i++) al.Add(new ValueWithTimeStamp(rdr.GetSqlBinary(0), rdr.GetString(1))); 
        // table has 10 rows so this is 100,000 and the select is desc to is has to so a lot of sorting 
       } 
      } 
      for (int i = 0; i < 10; i++) Debug.WriteLine(((ValueWithTimeStamp)al[i]).TimeStampUInt64.ToString()); 
      System.Diagnostics.Stopwatch sw = new Stopwatch(); 
      sw.Start(); 
      al.Sort(); 
      sw.Stop(); 
      for (int i = 0; i < 10; i++) Debug.WriteLine(((ValueWithTimeStamp)al[i]).TimeStampUInt64.ToString()); 
      Debug.WriteLine(sw.ElapsedMilliseconds.ToString()); 
     } 
    } 
    public struct ValueWithTimeStamp: IComparable 
    { 
     private UInt64 timeStampUInt64; 
     private string value; 
     public int CompareTo(object obj) 
     { 
      if (obj == null) return -1; 
      if (!(obj is ValueWithTimeStamp)) return -1; 
      ValueWithTimeStamp comp = (ValueWithTimeStamp)obj; 
      return this.TimeStampUInt64.CompareTo(comp.TimeStampUInt64); 
     } 
     public UInt64 TimeStampUInt64 { get { return timeStampUInt64; } } 
     public string Value { get { return value; } } 
     public ValueWithTimeStamp(System.Data.SqlTypes.SqlBinary TimeStamp, string Value) 
     { 
      // using UInt64 for timeStampUInt64 as it implements CompareTo and is something you can read 
      timeStampUInt64 = BitConverter.ToUInt64(TimeStamp.Value,0); 
      value = Value; 
     } 
    } 
}