A fast way to search any kind of collection until a value is found which is higher (in a sorted list)

Question

I am looking for a way to quickly retrieve all items out of a list. This list contains time values, and i need everything before a specific time. Obviously a list which is ordered should be easy, once you find 1 item in the list with a higher value than what you've defined it can stop.

I found this ordered queue online which claims to be fast but it does not have a good method for finding all times up to a certain point.

If i knew of a way to make this method (a good and fast one) i would, but I have no idea what the best possible way would be.

I am currently using this queue as follows, which isn't the best way to use it (I would think):

while (mDisposing == false)
{
    if (this.mIdleChoresRunning == true)
    {
        try
        {
            if ((mIdleChoreQueue.First != null) && (Timing.IsTimeOutByTicksNow(mIdleChoreQueue.First.AddTime, mIdleChoreQueue.First.WaitTime)))
            {
                //var item = mIdleChoreQueue.Dequeue();
                var chore = mIdleChores[mIdleChoreQueue.First.IdleChoreIdentification];
                mIdleChoreQueue.First.AddTime = Environment.TickCount;
                mIdleChoreQueue.First.WaitTime = chore.IdleMiliSeconds;

                mTaskQueue.EnqueueTask(() =>
                //Task.Factory.StartNew(() =>
                {
                    chore.Execute(mIdleChoreQueue.First.Context);
                });

                mIdleChoreQueue.UpdatePriority(mIdleChoreQueue.First, mIdleChoreQueue.First.AddTime + mIdleChoreQueue.First.WaitTime);
            }
            else
            {
                Thread.Sleep(10);
            }
        }
        catch (Exception exception)
        {
            mLogger.Error("ExecuteIdleChores() EXCEPTION", exception);
        }
    }
    else
    {
        Thread.Sleep(100);
    }
}

To clarify I do not care about the type of collection, all I want is a faster way for getting my items (and executing them) than:

mIdleChoreList.Where(x => Timing.IsTimeOutByTicksNow(x.AddTime, x.WaitTime));

Because a .Where() operation is really slow.

Answer 1

Consider the doubly linked list (sorted list in c#), where you would insert items based off the timevalues. The items to process will be the first item in the list. Simplify remove the item if you need to process it, process it, increment the time value and add the new time value back to the list. Since the list is sorted, the item will be placed into the proper spot. The most overhead will occur on inserts.

Here's more info on linked lists in c# https://msdn.microsoft.com/en-us/library/ms132319(v=vs.110).aspx You can utilize custom comparers if you want to add custom classes to the list. e.g. Create a class with properties, TimeToExecute and IncrementValue, and insert based on TimeToExecute.

You can also explore the binary search tree (sorted dictionary in c#). The difference between the sorted dictionary and sorted list is that inserts are faster in the sorted dictionary. However, tracking/finding items to process will be slower. (you can use linq's where clause, but performance will not be the fastest).

A hashmap will have the benefit of faster inserts, but like the sorted dictionary, you will need to look for the values to process.

Please remember, dictionaries/hashmaps work best if you know exactly what you are looking for, i.e. a specific time. If you are looking for a range, you'll still need to scan the entire dictionary.

Answer 2

For sorted list the fastest way to find any item is binary search (O(log n)).

Note: it sounds like you need list of items prior particular point (which is O(n) by itself) in theory any algorithm would do, including basic Where(x => ChekcTime(x)).