Nächste/nächste Übereinstimmung in .NET Hashtable (oder einer anderen Struktur) abrufen

Question

Ich habe ein Szenario bei der Arbeit, in dem wir mehrere verschiedene Datentabellen in einem ähnlichen Format wie dem folgenden haben:

Table Name: HingeArms
Hght   Part #1       Part #2
33     S-HG-088-00   S-HG-089-00
41     S-HG-084-00   S-HG-085-00
49     S-HG-033-00   S-HG-036-00
57     S-HG-034-00   S-HG-037-00

Die erste Spalte (und möglicherweise weitere) enthält numerische Daten, die aufsteigend sortiert sind und einen Bereich darstellen, um den richtigen Datensatz zu ermitteln (z. B. Höhe <= 33, dann ist Teil 1 = S-HG-088-00, Höhe <= 41, dann ist Teil 1 = S-HG-084-00, usw.)

Ich muss die nächstgelegene Übereinstimmung mit einem bestimmten Wert suchen und auswählen. Beispiel: Bei einer Höhe von 34,25 muss ich den zweiten Datensatz im obigen Satz finden:

41     S-HG-084-00   S-HG-085-00

Diese Tabellen werden derzeit in einem VB.NET-Hashtable-"Cache" von Daten gespeichert, die aus einer CSV-Datei geladen werden, wobei der Schlüssel für die Hashtable eine Zusammensetzung aus dem Tabellennamen und einer oder mehreren Spalten aus der Tabelle ist, die den "Schlüssel" für den Datensatz darstellen. Für die obige Tabelle würde die Hashtable Add für den ersten Datensatz beispielsweise lauten:

ht.Add("HingeArms,33","S-HG-088-00,S-HG-089-00")

Dies scheint nicht optimal zu sein, und ich habe eine gewisse Flexibilität, um die Struktur bei Bedarf zu ändern (der Cache enthält Daten aus anderen Tabellen, in denen ein direktes Nachschlagen möglich ist... diese "Bereichstabellen" wurden einfach eingefügt, weil es "einfach" war). Ich war auf der Suche nach einer "Next"-Methode für eine Hashtable/Dictionary, die mir den nächstgelegenen passenden Datensatz im Bereich liefert, aber das ist bei den Standardklassen in VB.NET offensichtlich nicht möglich.

Irgendwelche Ideen für einen Weg zu tun, was ich mit einer Hashtable oder in einer anderen Struktur suche? Es muss performant sein, wie der Lookup wird oft in verschiedenen Abschnitten des Codes aufgerufen werden. Jeder Gedanke würde sehr geschätzt werden. Danke!

Answer 1

Eine Hashtabelle ist hierfür keine gute Datenstruktur, da die Elemente im internen Array entsprechend ihrem Hash-Code und nicht entsprechend ihren Werten verteilt sind.

Verwenden Sie eine sortierte Array o Liste<T> und führen eine binäre Suche durch, z. B.

セットアップ

var values = new List<HingeArm>
{
    new HingeArm(33, "S-HG-088-00", "S-HG-089-00"),
    new HingeArm(41, "S-HG-084-00", "S-HG-085-00"),
    new HingeArm(49, "S-HG-033-00", "S-HG-036-00"),
    new HingeArm(57, "S-HG-034-00", "S-HG-037-00"),
};

values.Sort((x, y) => x.Height.CompareTo(y.Height));

var keys = values.Select(x => x.Height).ToList();

Nachschlagen:

var index = keys.BinarySearch(34.25);
if (index < 0)
{
    index = ~index;
}

var result = values[index];
// result == { Height = 41, Part1 = "S-HG-084-00", Part2 = "S-HG-085-00" }

Answer 2

Wie wäre es mit LINQ-to-Objects (dies ist übrigens keineswegs als performante Lösung gedacht).

    var ht = new Dictionary<string, string>();
    ht.Add("HingeArms,33", "S-HG-088-00,S-HG-089-00");
    decimal wantedHeight = 34.25m;

    var foundIt =
        ht.Select(x => new { Height = decimal.Parse(x.Key.Split(',')[1]), x.Key, x.Value }).Where(
            x => x.Height < wantedHeight).OrderBy(x => x.Height).SingleOrDefault();

    if (foundIt != null)
    {
        // Do Something with your item in foundIt
    }

Answer 3

Sie können ein sortiertes .NET-Array in Kombination mit Array.BinarySearch() verwenden. Wenn Sie einen nicht negativen Wert erhalten, ist dies der Index der exakten Übereinstimmung. Andernfalls, wenn das Ergebnis negativ ist, verwenden Sie die Formel

int index = ~Array.BinarySearch(sortedArray, value) - 1

um den Index der vorherigen "nächstgelegenen" Übereinstimmung zu erhalten.

Die Bedeutung von "am nächsten" wird durch den von Ihnen verwendeten Vergleicher definiert. Es muss derselbe sein, den Sie beim Sortieren des Arrays verwendet haben. Siehe:

http://gmamaladze.wordpress.com/2011/07/22/back-to-the-roots-net-binary-search-and-the-meaning-of-the-negative-number-of-the-array-binarysearch-return-value/