Ausgabe
Ich habe eine Artikelliste und möchte alle Artikel auswählen, die für ein bestimmtes Datum gültig sind. Jedes Element enthält eine eindeutige Kennung, einige Informationen sowie ein Start- und Enddatum. Die Datenstruktur dieser Artikel muss nur einmal erstellt werden, aber sie enthält 100.000 Artikel und es gibt viele Anfragen. Ich dachte, dass die Datenstruktur absteigend nach zB “endDate” sortiert ist und dann suche ich (mit binärer Suche) nach dem ersten “endDate”, das nicht mehr gültig ist, was bedeutet, dass das endDate vor dem angegebenen Datum liegt – zum Beispiel habe ich a gegebenes Datum vom 29.07.2022, dann wüsste ich, dass ich verwerfen könnte:
endDate
-------------
30.07.2022
28.07.2022 <-
26.07.2022 <-
23.07.2022 <-
Das würde den Rechenaufwand gering halten. Aber dann muss ich die Daten für startDate neu sortieren. Gibt es einen besseren Weg, dies zu tun? Welche Datenstruktur würden Sie hier empfehlen?
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; }
}
Vielen Dank!
Lösung
Diese Antwort geht davon aus, dass Sie häufig Einfügungen und Löschungen sowie häufige Suchen haben.
Wenn Sie Dinge mit zwei verschiedenen Sortierungen nachschlagen möchten (aus Leistungsgründen), müssen Sie zwei verschiedene sortierte Container verwalten.
Dazu können Sie verwenden SortedSet<T>. Dadurch erhalten Sie O(Log(N))Lookups, Einfügungen und Löschungen.
Um sie SortedSet<T>mit Ihrer ItemKlasse zu verwenden, müssen Sie eine Implementierung von hinzufügen Equals(), da sie verwendet wird, wenn Elemente zu einem Container hinzugefügt werden, der SortedSet<T>beispielsweise Vergleiche verwendet.
Sie müssen auch sicherstellen, dass alle Eigenschaften, die für Identität und Sortierung verwendet werden, unveränderlich sind – denn wenn Sie diese Eigenschaften eines Elements ändern, das derzeit in einem sortierten Container gespeichert ist, wird es andernfalls beschädigt.
Ihre ItemKlasse müsste also ungefähr so aussehen:
public sealed class Item: IEquatable<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.
public bool Equals(Item? other)
{
if (other is null)
return false;
if (ReferenceEquals(this, other))
return true;
return Id == other.Id;
}
public override bool Equals(object? obj)
{
return ReferenceEquals(this, obj) || obj is Item other && Equals(other);
}
public override int GetHashCode()
{
return Id.GetHashCode();
}
}
Jetzt brauchen Sie eine Möglichkeit, ItemObjekte nach Start- und Enddatum zu vergleichen, um sie mit den zwei unterschiedlich sortierten SortedSet<T>Sammlungen zu verwenden. Wir können dies tun, indem wir eine kleine Klasse schreiben, die Folgendes implementiert 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;
}
Der Konstruktor für diese Klasse akzeptiert ein , das definiert, ob nach oder nach boolsortiert wird .StartDateEndDate
Jetzt können Sie eine Klasse schreiben, die die beiden unterschiedlich sortierten SortedSet<T>Sammlungen kapselt und übergeordnete Methoden zum Hinzufügen, Entfernen und Suchen von Elementen bereitstellt. Diese Klasse enthält auch eine verschachtelte Implementierung der ItemComparerobigen Klasse, da dies lediglich ein Implementierungsdetail ist, das nicht offengelegt werden muss:
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);
}
Sie sollten sehen können, wie Sie dieser Klasse weitere Methoden hinzufügen, wenn Sie weitere Funktionen hinzufügen müssen.
Sie können diese Klasse mit folgendem Code testen:
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);
}
}
Beantwortet von – Matthew Watson
Antwort geprüft von – Senaida (FixError Volunteer)
