查找包含给定时间点的间隔的最快方法

Question

我需要创建基于时间的"计划结构",使用以下方法:

Void  addTask(DateTime startTime, int durationInMinutes, TaskObject myObj)
{
   // add TaskObject to calendar structure
}
List<TaskObject> getRunningTasks (DateTime startTime, DateTime endTime)
{
  //this procedure have to efficiently return list of running tasks in specified time frame
}
List<TaskObject> getRunningTasks (DateTime exactTime)
{
    return getRunningTaks(exactTime,exactTime);
}

我有大约60k个TaskObjects需要计算,需要在几小时和几分钟内重新计算(getRunningTasks将被调用大约400k次)

现在我使用:

public Dictionary<long, Dictionary<int, Dictionary<int, List< TaskObject>>>> scheduleTable;

scheduleTable [dayInTicks] [小时] [分钟]

我将所有匹配的任务添加到每个小时和分钟,在哪里安排它们.

来自DrKoch的想法

    public class TaskList
    {
        private SortedDictionary<DateTime, TaskObject> startTimes;
        private SortedDictionary<DateTime, TaskObject> endTimes;
        private SortedSet<DateTime> startTimeIndexes;
        private SortedSet<DateTime> endTimeIndexes;
        public TaskList()
        {
            reset();
        }
        public void addTask(TaskObject taskToAdd, DateTime startTime, int durationInMinutes)
        {
            // start time
            while (startTimes.ContainsKey(startTime))
            {
                startTime = startTime.AddTicks(1);
            }
            startTimes.Add(startTime, taskToAdd);
            startTimeIndexes.Add(startTime);
            //end time
            DateTime endTime = startTime.AddMinutes(durationInMinutes);
            while (endTimes.ContainsKey(endTime))
            {
                endTime = endTime.AddTicks(1);
            }
            endTimes.Add(endTime, taskToAdd);
            endTimeIndexes.Add(endTime);
        }
        public List<TaskObject> getRunningTasks(DateTime startTime, DateTime endTime)
        {
            DateTime fromBeginingOfDay = new DateTime(endTime.Year, endTime.Month, endTime.Day);
            SortedSet<DateTime> myEndTimeIndexes =  endTimeIndexes.GetViewBetween(fromBeginingOfDay, startTime); // tasks, that already finished during specified day
            SortedSet<DateTime> myStartTimeIndexes = endTimeIndexes.GetViewBetween(fromBeginingOfDay, endTime);  // tasks, that started from the beginig of the day
            List<TaskObject> result = new List<TaskObject>();
            // Fill result with all matching tasks
            foreach (DateTime myStartTimeIndex in myStartTimeIndexes)
            {
                result.Add(startTimes[myStartTimeIndex]);
            }
            // Remove finished tasks from result
            foreach (DateTime myEndTimeIndex in myEndTimeIndexes)
            {
                if (result.Contains(endTimes[myEndTimeIndex]))
                {
                    result.Remove(startTimes[myEndTimeIndex]);
                }
            }
            return result;
        }
        public List<TaskObject> getRunningTasks(DateTime exactTime)
        {
            return getRunningTasks(exactTime, exactTime.addSeconds(1));
        }
        public void reset()
        {
            startTimes = new SortedDictionary<DateTime, TaskObject>();
            endTimes = new SortedDictionary<DateTime, TaskObject>();
            startTimeIndexes = new SortedSet<DateTime>();
            endTimeIndexes = new SortedSet<DateTime>();
        }
    }
    public class TaskObject
    {
        public string Name;
        public TaskObject(string name)
        {
            Name = name;
        }
    }

Answer 1

假设您将任务存储在这样的类中:

public class MyTask
{
    public string name;
    public DateTime startDt;
    public DateTime endDt;
    // ...
}

基本思想是维护两个带有任务的集合,一个按startDtscond 排序endDt.

我们将使用SortedSet两个原因:

1. 它具有用于插入和搜索的O(log n)的计算复杂度.如果您遇到许多项目的问题,则非常希望具有比O(n)更好的复杂性.

2. 它允许返回某个"范围"内的所有项目.无需像在词典中那样知道用于检索的确切"键"

因为a SortedSet中的所有项都是唯一的,并且因为几个任务可能具有相同的startDt或者endDt我们无法直接在任务中存储任务,所以SortedSet我们在同一时间维护所有任务的"桶":

public class SameTimeTaskList
{
    public DateTime time; // common start or end time of all tasks in list
    public List<MyTask> taskList = new List<MyTask>();
}

对此的排序标准time当然是:

// Defines a comparer to create a sorted set 
// that is sorted by time. 
public class ByTime : IComparer<SameTimeTaskList>
{
    public int Compare(SameTimeTaskList x, SameTimeTaskList y)
    {
        return x.time.CompareTo(y.time);
    }
}

有了这个,我们可以构建我们的两个排序集:

SortedSet<SameTimeTaskList> startTimeSet = 
  new SortedSet<SameTimeTaskList>(new ByTime());
SortedSet<SameTimeTaskList> endTimeSet = 
  new SortedSet<SameTimeTaskList>(new ByTime());

两个集中都插入了一个新任务.如果没有此time存储桶,则会创建新存储桶.否则,只需将任务添加到正确的存储桶中:

    public void Add(MyTask task)
    {
        // startTimeSet
        refTime.time = task.startDt;
        var lst = startTimeSet.GetViewBetween(refTime,
            refTime).FirstOrDefault();
        if (lst == null) // no bucket found for time
        {
            lst = new SameTimeTaskList { time = task.startDt };
            startTimeSet.Add(lst);
        }
        lst.taskList.Add(task); // add task to bucket
        // endTimeSet
        refTime.time = task.endDt;
        lst = endTimeSet.GetViewBetween(refTime,
            refTime).FirstOrDefault();
        if (lst == null) // no bucket found for time
        {
            lst = new SameTimeTaskList { time = task.endDt };
            endTimeSet.Add(lst);
        }
        lst.taskList.Add(task); // add task to bucket
    }

现在很容易获得所有在某些活动中活跃的交互exactTime.每项任务必须满足两个条件:

task.startDt <= exactTime
&&
task.endDt >= exactTime

我们检查两者SortedSets以查看哪个返回一个条件的较小集合.然后,如果它与第二个条件匹配,我们检查较小集合中的所有任务:

    public IEnumerable<MyTask> Get(DateTime exactTime)
    {
        refTime.time = exactTime;
        // set of all tasks started before exactTime
        SortedSet<SameTimeTaskList> sSet =
           startTimeSet.GetViewBetween(minTime, refTime);
        // set of all tasks ended after exactTime
        SortedSet<SameTimeTaskList> eSet =
           endTimeSet.GetViewBetween(refTime, maxTime);

        List<MyTask> result = new List<MyTask>();
        if (sSet.Count < eSet.Count) // check smaller set for 2nd condition
        {
            foreach (var tl in sSet)
                foreach (MyTask tsk in tl.taskList)
                    if(tsk.endDt >= exactTime) result.Add(tsk);
        }
        else // eSet is smaller
        {
            foreach (var tl in eSet)
                foreach (MyTask tsk in tl.taskList)
                    if (tsk.startDt <= exactTime) result.Add(tsk);

        }
        return result;
    }

以下是作为工作程序的完整代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace IntervallsTest
{
    class Program
    {
        static void Main(string[] args)
        {
            DateTime exactDate = DateTime.Parse("2015-6-1");

            var tc = new TaskCollection();
            tc.Add(new MyTask { name = "T1", startDt = DateTime.Parse("2015-1-1"), endDt = DateTime.Parse("2015-02-01") });
            tc.Add(new MyTask { name = "T2", startDt = DateTime.Parse("2015-1-1"), endDt = DateTime.Parse("2015-07-01") });
            tc.Add(new MyTask { name = "T2a", startDt = DateTime.Parse("2015-1-1"), endDt = DateTime.Parse("2015-07-02") });
            tc.Add(new MyTask { name = "T3", startDt = DateTime.Parse("2015-05-1"), endDt = DateTime.Parse("2015-12-31") });
            tc.Add(new MyTask { name = "T3a", startDt = DateTime.Parse("2015-04-1"), endDt = DateTime.Parse("2015-12-31") });
            tc.Add(new MyTask { name = "T4", startDt = DateTime.Parse("2015-12-1"), endDt = DateTime.Parse("2015-12-31") });

            var result = tc.Get(exactDate);

            Console.WriteLine("These tasks are active at " + exactDate);
            foreach (var tsk in result)
            {
                Console.WriteLine(tsk.name);
            }
            Console.WriteLine("press any key");
            Console.ReadKey();
        }
    }

    public class TaskCollection
    {
        SortedSet<SameTimeTaskList> startTimeSet = new SortedSet<SameTimeTaskList>(new ByTime());
        SortedSet<SameTimeTaskList> endTimeSet = new SortedSet<SameTimeTaskList>(new ByTime());

        static SameTimeTaskList refTime = new SameTimeTaskList();
        static SameTimeTaskList minTime = new SameTimeTaskList { time = DateTime.MinValue };
        static SameTimeTaskList maxTime = new SameTimeTaskList { time = DateTime.MaxValue };

        public void Add(MyTask task)
        {
            // startTimeSet
            refTime.time = task.startDt;
            var lst = startTimeSet.GetViewBetween(refTime, refTime).FirstOrDefault();
            if (lst == null) // no bucket found for time
            {
                lst = new SameTimeTaskList { time = task.startDt };
                startTimeSet.Add(lst);
            }
            lst.taskList.Add(task); // add task to bucket
            // endTimeSet
            refTime.time = task.endDt;
            lst = endTimeSet.GetViewBetween(refTime, refTime).FirstOrDefault();
            if (lst == null) // no bucket found for time
            {
                lst = new SameTimeTaskList { time = task.endDt };
                endTimeSet.Add(lst);
            }
            lst.taskList.Add(task); // add task to bucket
        }

        public IEnumerable<MyTask> Get(DateTime exactTime)
        {
            refTime.time = exactTime;
            // set of all tasks started before exactTime
            SortedSet<SameTimeTaskList> sSet = startTimeSet.GetViewBetween(minTime, refTime);
            // set of all tasks ended after exactTime
            SortedSet<SameTimeTaskList> eSet = endTimeSet.GetViewBetween(refTime, maxTime);

            List<MyTask> result = new List<MyTask>();
            if (sSet.Count < eSet.Count) // check smaller set for 2nd condition
            {
                foreach (var tl in sSet)
                    foreach (MyTask tsk in tl.taskList)
                        if(tsk.endDt >= exactTime) result.Add(tsk);
            }
            else // eSet is smaller
            {
                foreach (var tl in eSet)
                    foreach (MyTask tsk in tl.taskList)
                        if (tsk.startDt <= exactTime) result.Add(tsk);

            }
            return result;
        }
    }

    public class MyTask
    {
        public string name;
        public DateTime startDt;
        public DateTime endDt;
        // ...
    }

    public class SameTimeTaskList
    {
        public DateTime time; // common start or end time of all tasks in list
        public List<MyTask> taskList = new List<MyTask>();
    }

    // Defines a comparer to create a sorted set 
    // that is sorted by time. 
    public class ByTime : IComparer<SameTimeTaskList>
    {
        public int Compare(SameTimeTaskList x, SameTimeTaskList y)
        {
            return x.time.CompareTo(y.time);
        }
    }
}

当您将此与您尝试过的所有其他版本进行比较时,我会非常有兴趣看到基准测试结果.