Метод сортировки ArrayList

Question

Друг и я пишем некоторое программное обеспечение (как побочный проект) и испытываем проблемы с ArrayLists.

Мы храним коллекцию экземпляров пользовательского объекта (содержащего DateTime и две строки) в ArrayList. После того, как мы сохранили все записи в ArrayList, мы сортируем их по DateTime. Проблема в том, что нам нужно хранить 100 000 экземпляров объекта, что означает, что встроенный метод сортировки занимает очень много времени - мы набрали его в течение часа, в какой-то момент.

Скорость сортировки не такая уж большая проблема, но мне было просто интересно, был ли лучший способ сортировать элементы в ArrayList, чем использовать встроенный метод сортировки. Хотя, я думаю, нет, основываясь на том, что встроенный .net-материал будет сильно оптимизирован.

Примечание. Мы используем ArrayLists из-за промежуточного программного обеспечения, которое мы выбрали для создания отчетов в формате PDF, на основе содержимого ArrayList. Думаю, если бы у нас была возможность перейти к списку <>, тогда методы сортировки были бы лучше. Или они?

Edit:

на основе запросов для исходного кода, я выложу некоторые. Но я не уверен, сколько я могу предоставить, что не очевидно.

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 демонстрирует худшее поведение. Я нахожу последнее довольно маловероятным.

Вот моя тестовая программа, которая добавляет 100 000 из ваших DataObject экземпляров в 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, то это реализация.

Сортировка по 100 000 строк в 200 миллисекунд.
И он должен сделать много сортировки.
Что-то не так в вашем коде.

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; 
     } 
    } 
}