我有一個專案串列，我想選擇在給定日期有效的所有專案。每個專案都包含一個唯一識別符號、一些資訊以及一個開始和結束日期。這些專案的資料結構只需要創建一次，但它包含 100.000 個專案并且有很多請求。我在想資料結構按例如“endDate”降序排序，然后我搜索（使用二進制搜索）第一個不再有效的“endDate”，這意味著endDate在給定日期之前 - 例如我有一個給定日期 29.07.2022，那么我知道我可以丟棄：
endDate
-------------
30.07.2022
28.07.2022 <-
26.07.2022 <-
23.07.2022 <-
這將使計算作業量保持在較低水平。但隨后我必須再次對 startDate 的資料進行排序。有一個更好的方法嗎？你會在這里推薦什么資料結構？
var itemList = new List<Item>();
class Item
{
public string id {get; set;}
public string startDate { get; set; }
public string endDate { get; set; }
public string someInfo { get; set; }
}
謝謝！
uj5u.com熱心網友回復：
這個答案假設您有頻繁的插入和洗掉以及頻繁的查找。
如果您想使用兩種不同的排序（出于性能原因）查找內容，則需要維護兩個不同的排序容器。
為此，您可以使用SortedSet<T>. 這為您提供了O(Log(N))查找、插入和洗掉功能。
（對于你的類來說，這個特定的代碼示例實際上不需要實作IEquatable<Item>，因為它不會用于SortedSet<T>。但是，添加它是一種很好的做法。請注意，如果你使用record型別，IEquatable<Item>將自動為你實作。我已經從這個答案中省略了實作IEquatable<Item>，但請注意，如果您更改代碼以使用散列容器，您必須為該類實作IEquatable<Item>并正確實作。）GetHashCode()
您需要確保用于標識和排序的所有屬性都是不可變的 - 因為否則如果您更改當前存盤在已排序容器中的專案的這些屬性，它將損壞。
所以你的Item班級必須看起來像這樣：
public sealed class Item
{
public Item(string id, DateTime startDate, DateTime endDate, string someInfo)
{
Id = id;
StartDate = startDate;
EndDate = endDate;
SomeInfo = someInfo;
}
public string Id { get; } // Used for identity therefore must be immutable.
public DateTime StartDate { get; } // Used for sorting therefore must be immutable.
public DateTime EndDate { get; } // Used for sorting therefore must be immutable.
public string SomeInfo { get; set; } // Not used for sorting or identity, so can be mutable.
}
現在您需要一種Item按開始日期和結束日期比較物件的方法，以便與兩個不同排序的SortedSet<T>集合一起使用。我們可以通過撰寫一個小類來實作IComparer<Item>：
sealed class ItemComparer : IComparer<Item>
{
public ItemComparer(bool compareStart)
{
_compareStart = compareStart;
}
public int Compare(Item? x, Item? y)
{
int byDate = _compareStart
? x!.StartDate.CompareTo(y!.StartDate)
: x!.EndDate .CompareTo(y!.EndDate);
if (byDate != 0)
return byDate;
return x.Id.CompareTo(y.Id);
}
readonly bool _compareStart;
}
此類的建構式接受 a bool，它定義它是按StartDate還是按排序EndDate。
現在您可以撰寫一個類來封裝兩個不同排序的SortedSet<T>集合，并提供更高級別的方法來添加、洗掉和搜索專案。該類還將包含上述ItemComparer類的嵌套實作，因為這只是一個不需要公開的實作細節：
public sealed class ItemStore
{
public bool Add(Item item)
{
_byEnd.Add(item);
return _byStart.Add(item);
}
public bool Remove(Item item)
{
_byEnd.Remove(item);
return _byStart.Remove(item);
}
public void Clear()
{
_byStart.Clear();
_byEnd .Clear();
}
public IEnumerable<Item> ItemsAfterEndDate(DateTime date)
{
date = date.AddDays(1); // For AFTER the end date.
var start = new Item("", date, date, "");
var end = new Item("", DateTime.MaxValue, DateTime.MaxValue, "");
return _byEnd.GetViewBetween(start, end);
}
public IEnumerable<Item> ItemsBeforeEndDate(DateTime date)
{
date = date.AddDays(-1); // For BEFORE the start date.
var start = new Item("", DateTime.MinValue, DateTime.MinValue, "");
var end = new Item("", date, date, "");
return _byEnd.GetViewBetween(start, end);
}
public IEnumerable<Item> ItemsAfterStartDate(DateTime date)
{
date = date.AddDays(1); // For AFTER the start date.
var start = new Item("", date, date, "");
var end = new Item("", DateTime.MaxValue, DateTime.MaxValue, "");
return _byStart.GetViewBetween(start, end);
}
public IEnumerable<Item> ItemsBeforeStartDate(DateTime date)
{
date = date.AddDays(-1); // For BEFORE the start date.
var start = new Item("", DateTime.MinValue, DateTime.MinValue, "");
var end = new Item("", date, date, "");
return _byStart.GetViewBetween(start, end);
}
sealed class ItemComparer : IComparer<Item>
{
public ItemComparer(bool compareStart)
{
_compareStart = compareStart;
}
public int Compare(Item? x, Item? y)
{
int byDate = _compareStart
? x!.StartDate.CompareTo(y!.StartDate)
: x!.EndDate .CompareTo(y!.EndDate);
if (byDate != 0)
return byDate;
return x.Id.CompareTo(y.Id);
}
readonly bool _compareStart;
}
readonly SortedSet<Item> _byStart = new(_byStartComparer);
readonly SortedSet<Item> _byEnd = new(_byEndComparer);
static readonly IComparer<Item> _byStartComparer = new ItemComparer(compareStart: true);
static readonly IComparer<Item> _byEndComparer = new ItemComparer(compareStart: false);
}
如果您需要添加更多功能，您應該能夠看到如何向此類添加更多方法。
您可以使用如下代碼測驗此類：
static void Main()
{
var items = new ItemStore();
items.Add(new Item("1", DateTime.Parse("2022-07-01"), DateTime.Parse("2022-08-01"), "1"));
items.Add(new Item("2", DateTime.Parse("2022-08-01"), DateTime.Parse("2022-09-01"), "2"));
items.Add(new Item("3", DateTime.Parse("2022-09-01"), DateTime.Parse("2022-10-01"), "3"));
items.Add(new Item("4", DateTime.Parse("2022-10-01"), DateTime.Parse("2022-11-01"), "4"));
items.Add(new Item("1.1", DateTime.Parse("2022-07-01"), DateTime.Parse("2022-08-01"), "1.1"));
items.Add(new Item("2.1", DateTime.Parse("2022-08-01"), DateTime.Parse("2022-09-01"), "2.1"));
items.Add(new Item("3.1", DateTime.Parse("2022-09-01"), DateTime.Parse("2022-10-01"), "3.1"));
items.Add(new Item("4.1", DateTime.Parse("2022-10-01"), DateTime.Parse("2022-11-01"), "4.1"));
Console.WriteLine("Items with start date before 2022-09-01");
foreach (var item in items.ItemsBeforeStartDate(DateTime.Parse("2022-09-01")))
{
Console.WriteLine(item.Id);
}
Console.WriteLine("\nItems with end date after 2022-09-01");
foreach (var item in items.ItemsAfterEndDate(DateTime.Parse("2022-09-01")))
{
Console.WriteLine(item.Id);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/514356.html
標籤：C＃表现排序