How can I get a subset of a list based on a Datetime key in C #?

Question

I have a list of elements that describe events that occurred at some time, the time represented as a Datetime 'StartTime' property for objects. Now I want to extract a subset of these events containing those elements that are placed in the interval / between two instances of DateTime A, B, such as StartTime> = A && StartTime <= B. This is currently done by a simple Linq query, but since I have to run a lot of queries that extract small parts of this list, its quite inefficient.

I would like the standard SortedList class to have some subset function over the key, but that doesn't seem to be the case. Any ideas if this can be archived relatively simply with existing framework classes, or will I have to do some sort of custom binary search based on SortedList?

Answer 1

If possible, I would save the instances in the array, sorted by StartTime, and then call BinarySearch to determine the indices in the array whose boundaries end in.

Then, with this in mind, you can easily quickly access a subset based on a date range.

I developed a general class that can also help you with this:

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;
            }
        }
    }
}

, (IComparer<T> Comparable<T>). , , // ( ).

. , BinarySearch Array, IComparer, ( , ).

, , , , .

, , .

, :

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

:

// 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

Array.Find ?