Der effizienteste Weg, um alle Elemente eines Dictionary aus einer Liste von Schlüsseln abzurufen?

Question

Ich habe eine C# Dictionary<DateTime,SomeObject> Instanz.

Ich habe den folgenden Code:

private Dictionary<DateTime, SomeObject> _containedObjects = ...;//Let's imagine you have ~4000 items in it 

public IEnumerable<SomeObject> GetItemsList(HashSet<DateTime> requiredTimestamps){ 
    //How to return the list of SomeObject contained in _containedObjects 
    //Knowing that rarely(~<5% of the call), one or several DateTime of "requiredTimestamps" may not be in _containedObjects 
} 

Ich bin auf der Suche, wie ein IEnumerable<SomeObject> zurückzukehren alle Elemente enthalten, die durch einen der mitgelieferten Schlüssel verwiesen wurde. Das einzige Problem ist, dass diese Methode sehr oft aufgerufen wird und wir nicht immer alle Parameter haben.

So gibt es etwas effizienter als dies:

private Dictionary<DateTime, SomeObject> _containedObjects = ...;//Let's imagine you have ~4000 items in it 

public IEnumerable<SomeObject> GetItemsList(HashSet<DateTime> requiredTimestamps){ 
    List<SomeObject> toReturn = new List<SomeObject>(); 
    foreach(DateTime dateTime in requiredTimestamps){ 
     SomeObject found; 
     if(_containedObjects.TryGetValue(dateTime, out found)){ 
      toReturn.Add(found); 
     } 
    } 
    return toReturn; 
} 

Answer 1

Methode 1: Um dies deutlich schneller zu machen - das ist nicht durch den Algorithmus zu ändern, sondern durch eine lokale Kopie _containedObjects in Ihrer Methode zu machen und die lokale Kopie für die Suche verweisen.

Beispiel:

public static IEnumerable<int> GetItemsList3(HashSet<DateTime> requiredTimestamps) 
{ 
    var tmp = _containedObjects; 

    List<int> toReturn = new List<int>(); 
    foreach (DateTime dateTime in requiredTimestamps) 
    { 
     int found; 

     if (tmp.TryGetValue(dateTime, out found)) 
     { 
      toReturn.Add(found); 
     } 
    } 
    return toReturn; 
} 

Testdaten und Zeiten (auf Satz von 5000 Einzelteilen mit 125 Tasten gefunden):
Ihrer ursprünglichen Methode (Millisekunden): 2,06032186895335
Methode 1 (Millisekunden) : 0,53549626223609

Methode 2: Eine Möglichkeit, dies geringfügig schneller zu machen, ist durch die iterieren kleinerer Satz und die Suche auf dem größeren Set. Je nach Größenunterschied werden Sie etwas schneller.

Sie verwenden ein Dictionary und HashSet, so dass Ihre Suche nach einer dieser beiden Variablen O (1) ist.

Beispiel: Wenn _containedObjects weniger Einzelteile als requiredTimestamps wir Schleife durch _containedObjects (sonst Ihre Methode zur Umkehrung verwenden)

public static IEnumerable<int> GetItemsList2(HashSet<DateTime> requiredTimestamps) 
{ 
    List<int> toReturn = new List<int>(); 
    foreach (var dateTime in _containedObjects) 
    { 
     int found; 

     if (requiredTimestamps.Contains(dateTime.Key)) 
     { 
      toReturn.Add(dateTime.Value); 
     } 
    } 
    return toReturn; 
} 

Testdaten und -zeiten (am Set von 5000 für _containedObjects und eine Reihe von 10000 Artikeln für requiredTimestamps mit 125 Tasten gefunden):
Ihre ursprüngliche Methode (Millisekunden): 3,88056291367086
Methode 2 (Millisekunden): 3,31025939438943

Answer 2

Sie können LINQ verwenden, aber ich zweifle, ob es irgendeine Leistung erhöhen wird, auch wenn es ein Unterschied ist es unerheblich wäre.

Ihre Methode könnte sein:

public IEnumerable<SomeObject> GetItemsList(HashSet<DateTime> requiredTimestamps) 
{ 
    return _containedObjects.Where(r => requiredTimestamps.Contains(r.Key)) 
          .Select(d => d.Value); 
} 

Positiv dabei ist, lazy evaluation, da Sie nicht eine Liste bevölkern und es zurück.

Answer 3

Im Allgemeinen gibt es zwei Möglichkeiten, wie Sie dies tun können:

1. Gehen Sie durch requiredTimestamps sequenziell und jedes Datum/Zeit-Stempel im Wörterbuch nachschlagen. Dictionary Lookup ist O (1), wenn also k Elemente zu suchen sind, dauert es O (k) Zeit.
2. Gehen Sie das Wörterbuch sequenziell durch und extrahieren Sie diejenigen mit übereinstimmenden Schlüsseln im requiredTimestamps Hash-Satz. Dies dauert O (n) Zeit, wobei n die Anzahl der Elemente im Wörterbuch ist.

Theoretisch, die erste Option - das ist, was Sie im Moment haben - wird der schnellste Weg, es zu tun.

In der Praxis ist es wahrscheinlich, dass die erste effizienter ist, wenn die Anzahl der Elemente, die Sie suchen, weniger als einige Prozent der Gesamtzahl der Elemente im Wörterbuch beträgt. Das heißt, wenn Sie 100 Schlüssel in einem Wörterbuch von einer Million nachschlagen, wird die erste Option mit ziemlicher Sicherheit schneller sein. Wenn Sie 500.000 Schlüssel in einem Wörterbuch von einer Million nachschlagen, ist die zweite Methode möglicherweise schneller, weil es viel schneller ist, zum nächsten Schlüssel zu springen, als eine Suche durchzuführen.

Sie möchten wahrscheinlich für den häufigsten Fall optimieren, die vermutlich einen relativ kleinen Prozentsatz von Schlüsseln nachschlagen. In diesem Fall ist die Methode, die Sie beschreiben, mit ziemlicher Sicherheit der beste Ansatz. Aber der einzige Weg, um sicher zu sein, ist zu messen.

Eine Optimierung, die Sie in Betracht ziehen könnten, ist die Größenanpassung der Ausgabeliste. Das vermeidet Neuzuteilungen. Also, wenn Sie Ihre toReturn Liste erstellen:

List<SomeObject> toReturn = new List<SomeObject>(requiredTimestamps.Count); 

Answer 4

Hier sind einige verschiedene Möglichkeiten, es zu tun - Leistung alle ziemlich gleich ist, so dass Sie basierend auf Lesbarkeit wählen können.

Fügen Sie dies in LinqPad ein, wenn Sie es testen möchten - andernfalls ernten Sie einfach den Code, den Sie benötigen.

Ich denke, mein persönlicher Favorit aus Sicht der Lesbarkeit ist Methode 3. Methode 4 ist sicherlich lesbar, hat aber die unangenehme Eigenschaft, dass es für jeden erforderlichen Zeitstempel zwei Nachschlagewerke in das Wörterbuch tut.

void Main() 
{ 
    var obj = new TestClass<string>(i => string.Format("Element {0}", i)); 

    var sampleDateTimes = new HashSet<DateTime>(); 
    for(int i = 0; i < 4000/20; i++) 
    { 
     sampleDateTimes.Add(DateTime.Today.AddDays(i * -5)); 
    } 
    var result = obj.GetItemsList_3(sampleDateTimes); 
    foreach (var item in result) 
    { 
     Console.WriteLine(item); 
    } 
} 

class TestClass<SomeObject> 
{ 
    private Dictionary<DateTime, SomeObject> _containedObjects; 

    public TestClass(Func<int, SomeObject> converter) 
    { 
     _containedObjects = new Dictionary<DateTime, SomeObject>(); 
     for(int i = 0; i < 4000; i++) 
     { 
      _containedObjects.Add(DateTime.Today.AddDays(-i), converter(i)); 
     } 
    } 

    public IEnumerable<SomeObject> GetItemsList_1(HashSet<DateTime> requiredTimestamps) 
    { 
     List<SomeObject> toReturn = new List<SomeObject>(); 
     foreach(DateTime dateTime in requiredTimestamps) 
     { 
      SomeObject found; 
      if(_containedObjects.TryGetValue(dateTime, out found)) 
      { 
       toReturn.Add(found); 
      } 
     } 
     return toReturn; 
    } 

    public IEnumerable<SomeObject> GetItemsList_2(HashSet<DateTime> requiredTimestamps) 
    { 
     foreach(DateTime dateTime in requiredTimestamps) 
     { 
      SomeObject found; 
      if(_containedObjects.TryGetValue(dateTime, out found)) 
      { 
       yield return found; 
      } 
     } 
    }  

    public IEnumerable<SomeObject> GetItemsList_3(HashSet<DateTime> requiredTimestamps) 
    { 
     return requiredTimestamps 
      .Intersect(_containedObjects.Keys) 
      .Select (k => _containedObjects[k]); 
    } 

    public IEnumerable<SomeObject> GetItemsList_4(HashSet<DateTime> requiredTimestamps) 
    { 
     return requiredTimestamps 
      .Where(dt => _containedObjects.ContainsKey(dt)) 
      .Select (dt => _containedObjects[dt]); 
    } 
}