Cơ sở hạ tầng "Tuổi-Kỷ lục"

Question

Tôi đã tìm kiếm một cơ sở dữ liệu hoạt động giống như danh sách agerecord. Bạn có một agerecord nếu không ai trẻ có một đánh dấu cao hơn.

Vì vậy, tôi muốn có một danh sách các cặp (a, b), cho tất cả cặp đôi (a1, b1) và (a2, b2) sau hàm ý giữ a1> a2 => b1> b2.

Cần chèn phương thức chèn (a_new, b_new) chèn (a_new, b_new) nếu không tồn tại cặp (a_k, b_k) sao cho a_k < a_new nhưng b_k> b_new. Nếu tiêu chí này được thỏa mãn thì cặp mới được chèn vào và tất cả các cặp từ danh sách sao cho a_k> a_new nhưng b_k < b_new sẽ bị xóa.

Cơ sở hạ tầng không cần hỗ trợ xóa.

Answer 1

Đây là giải pháp chung mà tôi nghĩ sẽ thực hiện công việc cho bạn. Nó không được tối ưu hóa cho hiệu suất, cũng không được kiểm tra đặc biệt tốt.

public class AgePair<T, Y> 
    where T : IComparable<T> 
    where Y : IComparable<Y> 
{ 
    public T A { get; set; } 

    public Y B { get; set; } 
} 

public class AgeRecordList<T, Y> : IEnumerable<AgePair<T,Y>> 
    where T : IComparable<T> 
    where Y : IComparable<Y> 
{ 
    private List<AgePair<T, Y>> m_List = new List<AgePair<T, Y>>(); 

    public void Add(T a, Y b) 
    { 
     AgePair<T, Y> newPair = new AgePair<T, Y> { A = a, B = b }; 

     // Get all elements that are younger 
     var younger = GetYounger(newPair.A); 

     // Find any of the younger with a higher score 
     // If found, return without inserting the element 
     foreach (var v in younger) 
     { 
      if (v.B.CompareTo(newPair.B) >= 0) 
      { 
       return; 
      } 
     } 

     // Cache elements to delete 
     List<AgePair<T, Y>> toDelete = new List<AgePair<T, Y>>(); 

     // Find all the elder elements  
     var elder = GetElder(newPair.A); 

     // Find all elder elements with a lower B 
     foreach (var v in elder) 
     { 
      if (v.B.CompareTo(newPair.B) <= 0) 
      { 
       // Mark for delete 
       toDelete.Add(v); 
      } 
     } 

     // Delete those elements found above 
     foreach (var v in toDelete) 
     { 
      m_List.Remove(v); 
     } 

     // Add the new element 
     m_List.Add(newPair); 

     // Sort the list (ascending by A) 
     m_List.Sort(CompareA); 
    } 

    private List<AgePair<T, Y>> GetElder(T t) 
    { 
     List<AgePair<T, Y>> result = new List<AgePair<T, Y>>(); 

     foreach (var current in m_List) 
     { 
      if (t.CompareTo(current.A) <= 0) 
      { 
       result.Add(current); 
      } 
     } 

     return result; 
    } 

    private List<AgePair<T, Y>> GetYounger(T t) 
    { 
     List<AgePair<T, Y>> result = new List<AgePair<T, Y>>(); 

     foreach (var current in m_List) 
     { 
      if (t.CompareTo(current.A) > 0) 
      { 
       result.Add(current); 
      } 
     } 

     return result; 
    } 

    private static int CompareA(AgePair<T,Y> item1, AgePair<T,Y> item2) 
    { 
     return item1.A.CompareTo(item2.A); 
    } 


    public IEnumerator<AgePair<T, Y>> GetEnumerator() 
    { 
     return m_List.GetEnumerator(); 
    } 

} 

Sửa 1: tổng quan cấp cao của thuật toán

1. Tìm tất cả yếu tố trẻ hoặc bằng,
2. Đối với tất cả yếu tố trẻ hoặc bằng, xem nếu bất kỳ có một B cao hơn
3. Nếu (2) trả lại
4. Tìm tất cả các thành phần cũ hơn
5. Nếu bất kỳ phần tử nào có điểm thấp hơn, hãy xóa
6. Sắp xếp danh sách theo thứ tự tăng dần (bởi A)

Chỉnh sửa 2: Tốc độ có thể dễ dàng được tăng thêm a) một khi bạn tìm thấy các yếu tố trẻ, bạn có thể tiếp tục từ thời điểm đó khi tìm kiếm các yếu tố trai thay vì lặp lại tất cả lần nữa, và b) thay vì sắp xếp nó bằng cách sử dụng phương pháp sắp xếp danh sách, bạn có thể sử dụng InsertAt (0 hoặc chỉ số của người cao tuổi đầu tiên)

Answer 2

Danh sách tuổi này theo dõi hồ sơ tốt nhất cho mỗi độ tuổi, sau đó bỏ qua lứa tuổi không có thanh ghi khi được yêu cầu cho người chiến thắng.

Trong khi không phải tất cả người thua cuộc đều bị xóa trên Chèn (không chắc chắn nếu đó là yêu cầu mạnh), thì nên tiết kiệm thời gian tổng thể bằng cách lười biếng. Điểm yếu lớn nhất là cuộc gọi tới OrderBy. Nếu loại đó quá đắt trong khi không gian có sẵn, người ta có thể sắp xếp cho một SortedList để giữ tất cả được chèn vào.

Nếu không gian ở mức cao trong khi thời gian khả dụng, thật đơn giản để viết phương pháp dọn dẹp tương tự với phương pháp GetWinners. Thậm chí có thể được gọi từ InsertMethod để làm sạch sau mỗi lần chèn.

public class AgeList<T, U> where T:IComparable<T> where U:IComparable<U> 
{ 
    Dictionary<T, U> store = new Dictionary<T, U>(); 

    public void Insert(T a, U b) 
    { 
     if (!store.ContainsKey(a) || store[a].CompareTo(b) < 0) 
     { 
      store[a] = b; 
     } 
     //else discard by doing nothing 
    } 

    public IEnumerable<KeyValuePair<T, U>> GetWinners() 
    { 
     bool first = true; 
     U record = default(U); 
     foreach(T key in store.Keys.OrderBy(t => t)) 
     { 
      U newValue = store[key]; 
      if (first) 
      { 
       first = false; 
       record = newValue; 
       yield return new KeyValuePair<T, U>(key, record); 
      } 
      else if (record.CompareTo(newValue) < 0) 
      { 
       record = newValue; 
       yield return new KeyValuePair<T, U>(key, record); 
      } 
     } 
    } 
}