Performant das Objekt aus einer Liste suchen, dessen Zeitstempel am nächsten an Wunschzeit liegt

Hallo miteinander.
Da ich nach langjähriger Pause endlich mal wieder mit C# arbeite habe ich gleich eine Frage.
Ich habe einige tausend Objekte, in dem sich ein Zeit-Attribut befindet. Nun möchte ich mir gerne das Objekt rausholen, dessen Zeit-Attribut am nähesten an einem bestimmten Wert liegt.

Wie mache ich das am performantesten? Welche Datenstruktur sollte ich verwenden? Ich habe bereits an SortedList gedacht. Das Problem ist dass ich meine Objekte nicht nach Zeit sortieren sollte sondern nach Math.Abs(wunschzeit - o.Zeit).

Wie würdet ihr da vorgehen?

SortedList dürfte schon die richtige Struktur sein. Dann kannst du das suchen so gestallten:

x(n) ist das Element an Position n;

• Gehe die Liste durch (Anfang bei n = 1), und speichere immer das letzte Element.

Wenn |x(n) - wunschZeit| > |x(n-1) - wunschZeit|, dann ist x(n-1) das Element was am nächsten dranliegt.

Wenn man am Ende ankommt ist dann natürlich das letzte Element das nächste.

So würde ich das lösen. Das dürfte im Worst Case (Letztes Element ist das was am nöchsten dranliegt) O(n) sein.

LG pdelvo

Wäre es nicht schneller wenn man mit einer Teile-und-Herrsche-Strategie da rangehen würde?
Also ein Element in der Mitte schnappen->zu groß/klein -> Element zwischen aktueller Position und Anfang/Ende schnappen->usw.
Was ich eigendlich fragen wollte ist muss ich das alles selbst implementieren oder gibts irgendwas in Linq was mir die Sache vereinfacht und trotzdem performant ist?

SortedList möchte neben dem eigentlichen Datenwert noch einen Key haben. Soll ich da einfach den Zeitwert der Objekte übergeben? Die Wunschzeit hab ich ja zu dem Zeitpunkt noch nicht.

Hallo Lector,

Das Problem ist dass ich meine Objekte nicht nach Zeit sortieren sollte sondern nach Math.Abs(wunschzeit - o.Zeit).

Da die Wunschzeit wohl nicht gleich bleibt, wäre eine solche Sortierung nur 1x verwendbar. Wenn die Methode allgemeiner verwendet werden soll, so wäre eine Sortierung nach o.Zeit passender. Dann kannst du mittels binärer Suche (ist Teile-und-Herrsche, z.B. Array.Find Array.BinarySearch) das passende Elemente mit O(log n) finden.

Tipp: Stell dir die Zeit nicht als "Datum" vor, sondern einfach als Zahl der Sekunden, Minuten, was auch immer gerechnet von einem Beginn-Datum vor. Dann gehts "nur" um (sortierte) Liste von Zahlen in den das best passendsten Elemente gefunden werden soll. D.h. es geht nicht um die Suche von |wunsch - test| als Minimum, sondern um die Suche von test das ≤ wunsch ist. Dann noch das Folgeelemente betrachten und dann hast du den passendsten.

Wenn Zeiten hinzugefügt/entfernt werden sollen, so bieten such Suchbäume an. Für .net gibt es einige Implementierungen (Link hab ich jetzt keinen parat, aber das lässt sich schon finden).

gibts irgendwas in Linq was mir die Sache vereinfacht und trotzdem performant ist?

Mit Linq gibt es schon eine Möglichkeit, aber das ist eher "brute force" anstatt die Wahl einer geeignten Datenstruktur (sortierte Liste) und passendem Algorithmus (binäre Suche).

DateTime bestMach = dates.AsParallel()
        .Select(d => Math.Abs((wunsch - d.Date).TotalSeconds))
        .Min();

Woher kommen die Objekte? Wenns sie aus einer DB kommen, so kannst du dort ja die Suche durchführen lassen. Mit Index (~ balanzierter Suchbaum) ist das auch performant. Query von Linq ist dann analog anzuwenden.

Edit: Ich meinte gestern Array.BinarySearch, warum ich aber Array.Find geschrieben hatte weiß ich nicht mehr (vllt. die Uhrzeit). Jedenfalls wär die binäre Suche gemeint, so wäre es ja nicht effizient.

mfG Gü

Hallo zusammen,

wenn du, pdelvo, SortedList vorschlägst, warum schlägst du dann lineare Suche vor? SortedList<TKey, TValue>.TryGetValue verwendet automatisch binäre Suche, benötigt also O(log(n)) statt O(n) (*) und liefert direkt das gesuchte Element, falls der Zeitstempel exakt übereinstimmt. Falls er nicht exakt übereinstimmt, wird die Stelle zwischen den zwei (**) nächstliegenden Elementen geliefert, von denen man durch einfache Differenzbildung ermittelt, welches näher an der Wunschzeit liegt, wie du es auch beschrieben hast. [EDIT]Der ausgegraute Halbsatz gilt zwar nicht für SortedList<>.TryGetValue, aber für Array.BinarySearch und List<>.BinarySearch.[/EDIT]

Array.Find verwendet dagegen immer lineare Suche, selbst wenn das Array sortiert ist.

Teile und Herrsche ist für mich etwas anderes, ich würde das fragliche Verfahren immer binäre Suche nennen.

Der Key der SortedList wäre natürlich der Zeitstempel. Dafür muss man aber keinen Integer-Wert verwenden, sondern kann ganz normal DateTime verwenden. Auch von DateTimes kann man mit Minus (-) die Differenz bilden und das Ergebnis z.B. mit Größer (>) vergleichen.

Wichtig ist aber der Hinweis von gfoidl: Wenn sich die Zeitstempel der Objekte ändern können, ist ein neu sortieren (bzw. gar ein Neuaufbau der SortedList) erforderlich. Das bedeutet einen Aufwand von O(n*log(n)) oder sogar O(n^2). Wenn das öfter oder sogar jedes Mal nötig ist, kann man diesen Aufwand durch die Einsparung durch die binäre Suche nicht wieder herausholen. Dann sollte man wirklich besser eine lineare Suche verwenden, die bei einer nicht sortieren Liste aber immer bis zum Ende erfolgen muss, sofern kein Element gefunden wird, dessen Zeitstempel exakt übereinstimmt.

herbivore

() bei linearer Suche ist O(n) nicht nur der Aufwand im Worse Case sondern auch im Average Case, da man im Schnitt n/2 Elemente durchsuchen muss und konstante Faktoren (hier 0.5) wegfallen.
() bzw. die Stelle vor dem ersten oder nach dem letzten Element.

Hallo herbivore,

du schreibst zu SortedList<TKey, TValue>.TryGetValue:

Falls er nicht exakt übereinstimmt, wird die Stelle zwischen den zwei (**) nächstliegenden Elementen geliefert,

Wie bekommt man denn die Stelle? Der Rückgabewert von TryGetValue ist ja in dem Fall false und die out-Variable wird mit dem Standardwert für den Typ des value-Parameters gefüllt.

Hallo jbrand,

sorry, das ich mit Array.BinarySearch bzw. List.BinarySearch verwechselt. Da bekommt man die Einfügestelle als negierten Rückgabewert.

herbivore

Hallo herbivore,

danke für die Erklärung.

Dann könnte man die Suche statt direkt in der SortedList wie folgt durchführen

var l = liste.Keys.ToList();
var index = l.BinarySearch(wunschzeit);

und wäre immer noch mit einem Aufwand von O(log n) dabei.

Hallo jbrand,

ich gehe mal davon aus, dass liste eine SortedList<> ist. Dann werden (außer den Zuweisungen) die folgenden drei Operationen ausgeführt:

SortedList<>.Keys: O(1), also konstanter Aufwand, egal wie kurz oder lang die Liste ist.
Enumerable.ToList<>: O(n), also linearer Aufwand, weil alle Elemente in die neue Liste kopiert werden.
List<>.BinarySearch(): O(log(n))

Im Ergebnis haben beide Codezeilen zusammen lineare Laufzeit: O(1+n+log(n)) = O(n)

Am besten du vergisst SortedList<> und verwendest gleich Array oder List. Sofern deine Objekte eine Property (oder andere Möglichkeit) haben, um ihren Zeitstempel anzufragen, kannst du einen passenden IComparer<T> schreiben, um mit Array.Sort bzw. List<>.Sort nach dem Zeitstempel zu sortieren. Der Aufwand fürs Sortieren wird für praktische Fälle O(n*log(n)) sein. Anschließend kannst du mit BinarySearch direkt auf der sortieren Liste suchen und hast für die reine Suche eine Aufwand von O(log(n)).

herbivore