ArrayList 정렬 방법

Question

친구와 내가 (부 프로젝트로) 일부 소프트웨어를 작성 중이며 ArrayLists에 문제가 있습니다.

우리는 사용자 지정 개체 (DateTime과 두 개의 문자열 포함)의 인스턴스 컬렉션을 ArrayList에 저장하고 있습니다. ArrayList에 모든 항목을 저장하고 나면 DateTime으로 정렬합니다. 문제는 객체의 인스턴스를 100,000 개 저장해야한다는 것입니다. 즉, 내장 된 정렬 방법이 매우 오랜 시간이 걸린다는 것을 의미합니다. 한 시간에 한 시간이 넘는 시간이 걸렸습니다.

정렬 속도가 그리 큰 문제는 아니지만 ArrayList에서 요소를 정렬하는 가장 좋은 방법은 내장 된 정렬 방법을 사용하는 것보다 더 많은지 궁금합니다. 내가 추측하지는 않지만, .net에 내장 된 것들이 고도로 최적화 될 것이라는 사실에 기초하고있다.

참고 : 우리는 ArrayList의 내용을 기반으로 PDF 보고서를 생성하기 위해 사용 된 미들웨어 때문에 ArrayList를 사용하고 있습니다. 우리가 List <리스트로 옮길 기회가 있다면 정렬 방법이 더 좋을 것 같습니다. 아니면 그들은?

편집 :

소스 코드 요청에 따라 일부 게시 할 예정입니다. 하지만 내가 얼마나 많이 제공 할 수 있는지 확실하지 않습니다.

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

문제가 다른 곳에서 또는 게시 한 코드가 실행중인 내용을 정확하게 표현하지 못했습니다. 또는 데이터가 정렬이 최악의 동작을 보일 수있는 잘못된 순서로되어 있습니다. 나는 마지막 가능성이 희박하다고 본다.

DataObject 인스턴스를 ArrayList에 100,000 개 추가 한 다음 Sort을 호출하는 테스트 프로그램입니다. 내 컴퓨터에서 50 밀리 초 미만으로 실행됩니다.

이것은 3.5가 아니라 .NET 4.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

데이터가 타임 스탬프이면 구현입니다.

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