Comment puis-je obtenir un sous-ensemble d'une liste basée sur une clé Datetime en C#?

Question

J'ai une liste d'éléments décrivant des événements qui ont eu lieu à un moment donné, l'heure étant représentée comme une propriété Datetime 'StartTime' sur les objets. Je souhaite maintenant extraire un sous-ensemble de ces événements contenant les éléments qui sont placés dans un intervalle/entre deux instances DateTime A, B telles que StartTime> = A & & StartTime < = B. Actuellement cela est accompli par une simple requête Linq, mais puisque je dois exécuter beaucoup de requêtes extrayant de petites fractions de la liste, c'est tout à fait inefficace.

Avait espéré que la classe standard SortedList avait une sorte de fonctionnalité de sous-ensemble sur la clé, mais cela ne semble pas être le cas. Des idées si cela peut être archivé relativement simple avec les classes de framework existantes, ou devrais-je faire une sorte de recherche binaire personnalisée basée sur une SortedList?

Answer 1

Si possible, je conserverais les instances dans un tableau, triées par le StartTime, puis appelez BinarySearch pour déterminer les index dans le tableau auquel les limites se terminent. Puis, étant donné que, vous pouvez facilement accéder à un sous-ensemble basé sur la plage de dates rapidement.

J'ai travaillé une classe générique qui peut vous aider à cela aussi:

public class BinarySearcher<T> 
{ 
    // Possibly passed to the call to BinarySort. 
    private class ComparisonComparer : Comparer<T> 
    { 
     Comparison<T> comparison; 

     internal static IComparer<T> Create(Comparison<T> comparison) 
     { 
      // If comparison is null, return the default comparer for T. 
      if (comparison == null) 
      { 
       // Return the default. 
       return Comparer<T>.Default; 
      } 

      // Return a new implementation. 
      return new ComparisonComparer(comparison); 
     } 

     private ComparisonComparer(Comparison<T> comparison) 
     { 
      this.comparison = comparison; 
     } 

     public override int Compare(T x, T y) 
     { 
      return comparison(x, y); 
     } 
    } 

    // The elements. 
    T[] elements; 

    // The IComparable implementation. 
    IComparer<T> comparer; 

    // Do not assume sorting. 
    public BinarySearcher(IEnumerable<T> elements) : 
     this(elements, false, (IComparer<T>) null) { } 

    // Use default comparer. 
    public BinarySearcher(IEnumerable<T> elements, bool sorted) : 
     this(elements, sorted, (IComparer<T>) null) { } 

    // Assume no sorting. 
    public BinarySearcher(IEnumerable<T> elements, 
     Comparison<T> comparer) : 
      this(elements, false, 
       ComparisonComparer.Create(comparer)) { } 

    // Convert to IComparable<T>. 
    public BinarySearcher(IEnumerable<T> elements, bool sorted, 
     Comparison<T> comparer) : 
      this(elements, sorted, 
       ComparisonComparer.Create(comparer)) { } 

    // No sorting. 
    public BinarySearcher(IEnumerable<T> elements, 
     IComparer<T> comparer) : 
      this(elements, false, comparer) { } 

    // Convert to array. 
    public BinarySearcher(IEnumerable<T> elements, bool sorted, 
     IComparer<T> comparer) : 
      this(elements.ToArray(), sorted, comparer) { } 

    // Assume no sorting. 
    public BinarySearcher(T[] elements) : this(elements, false) { } 

    // Pass null for default comparer. 
    public BinarySearcher(T[] elements, bool sorted) : 
     this(elements, sorted, (IComparer<T>) null) { } 

    // Assume not sorted. 
    public BinarySearcher(T[] elements, Comparison<T> comparer) : 
     this(elements, false, ComparisonComparer.Create(comparer)) { } 

    // Create IComparable<T> from Comparable<T>. 
    public BinarySearcher(T[] elements, bool sorted, 
     Comparison<T> comparer) : 
      this(elements, sorted, ComparisonComparer.Create(comparer)) { } 

    // Assume the elements are not sorted. 
    public BinarySearcher(T[] elements, IComparer<T> comparer) : 
     this(elements, false, comparer) { } 

    public BinarySearcher(T[] elements, bool sorted, 
     IComparer<T> comparer) 
    { 
     // If the comparer is null, create the default one. 
     if (comparer == null) 
     { 
      // Set to the default one. 
      comparer = Comparer<T>.Default; 
     } 

     // Set the comparer. 
     this.comparer = comparer; 

     // Set the elements. If they are sorted already, don't bother, 
     // otherwise, sort. 
     if (!sorted) 
     { 
      // Sort. 
      Array.Sort(elements, this.comparer); 
     } 

     // Set the elements. 
     this.elements = elements; 
    } 

    public IEnumerable<T> Between(T from, T to) 
    { 
     // Find the index for the beginning. 
     int index = Array.BinarySearch(this.elements, from, comparer); 

     // Was the item found? 
     bool found = (index >= 0); 

     // If the item was not found, take the bitwise 
     // compliment to find out where it would be. 
     if (!found) 
     { 
      // Take the bitwise compliment. 
      index = ~index; 
     } 

     // If the item was found, cycle backwards from 
     // the index while there are elements that are the same. 
     if (found) 
     { 
      // Cycle backwards. 
      for (; index >= 0 && 
       comparer.Compare(from, elements[index]) == 0; 
       --index) ; 

      // Add one to the index, since this is on the element 
      // that didn't match the comparison. 
      index++; 
     } 

     // Go forward now. 
     for (; index < elements.Length; index++) 
     { 
      // Return while the comparison is true. 
      if (comparer.Compare(elements[index], to) <= 0) 
      { 
       // Return the element. 
       yield return elements[index]; 
      } 
      else 
      { 
       // Break 
       yield break; 
      } 
     } 
    } 
} 

La plupart de ce qui est ici sont des aides pour initialiser la classe, qui aura besoin d'une méthode de comparaison entre deux éléments (IComparer<T> et Comparable<T> sont prises ici). La classe vous permet également de prendre un tableau brut qui est déjà trié, au cas où vous voudriez ajouter/supprimer/mettre à jour des éléments dans les positions correctes vous-même plus tard (sans avoir à utiliser le tableau tout le temps).

La viande de la classe est dans l'appel à Between. Il prend une valeur from, qui sera transmise à la méthode BinarySearch statique de la classe Array, en passant l'implémentation IComparer utilisée par cette instance (elle suppose des valeurs par défaut si aucune n'est passée).

Si la valeur n'existe pas, il trouve dans le tableau, puis recule dans le cas où il y a plusieurs éléments avec la même valeur dans le tableau.

Ensuite, il effectue un cycle en avant, renvoyant les éléments de l'énumération alors que l'élément en cours est inférieur ou égal à la valeur to.

Dans votre situation particulière, en supposant que vous aviez une classe comme ceci:

public class Task 
{ 
    public string Name; 
    public DateTime StartTime; 
} 

Vous pouvez effectuer les opérations suivantes:

// Create tasks. 
Task[] tasks = 
{ 
    new Task() { Name = "Task 1", StartTime = new DateTime(2009, 02, 18) }, 
    new Task() { Name = "Task 2", StartTime = new DateTime(2009, 02, 16) }, 
    new Task() { Name = "Task 3", StartTime = new DateTime(2009, 02, 12) }, 
    new Task() { Name = "Task 4", StartTime = new DateTime(2009, 02, 11) }, 
    new Task() { Name = "Task 5", StartTime = new DateTime(2009, 02, 10) }, 
    new Task() { Name = "Task 6", StartTime = new DateTime(2009, 02, 01) }, 
    new Task() { Name = "Task 7", StartTime = new DateTime(2009, 02, 09) } 
}; 

// Now create the indexer. 
BinarySearcher<Task> searcher = new BinarySearcher<Task>(tasks, 
    (x, y) => Comparer<DateTime>.Default.Compare(x.StartTime, y.StartTime)); 

foreach (Task t in searcher.Between(
    new Task() { StartTime = new DateTime(2009, 02, 13) }, 
    new Task() { StartTime = new DateTime(2009, 02, 10) })) 
{ 
    // Write. 
    Console.WriteLine(t); 
} 

Answer 2

Avez-vous vérifié Array.Find en utilisant un prédicat personnalisé?