4

I have a problem I'm trying to solve, but i feel I'm not solving it in the most efficient way. Any new light on this is appreciated.

This is the time span i want to look at

start = '2013-01-01';
end = '2013-01-08';

There is a list of assignments with start and end dates

assignments = [{start: '2013-01-01', end: '2013-01-01'},
               {start: '2013-01-01', end: '2013-01-02'},
               {start: '2013-01-01', end: '2013-01-03'},
               {start: '2013-01-01', end: '2013-01-04'}];

I want to end up with a result, each date in the time span with a value that represents how many assignments were active that day. This is what i want the result to look like:

result = [{date: '2013-01-01', value: 4},
          {date: '2013-01-02', value: 3},
          {date: '2013-01-03', value: 2},
          {date: '2013-01-04', value: 1},
          {date: '2013-01-05', value: 0},
          {date: '2013-01-06', value: 0},
          {date: '2013-01-07', value: 0},
          {date: '2013-01-08', value: 0}];

My attempts include iterating through each date in daterange and checking how many assignments fall on that day. I have also tried going the other way, iterating through assignments and then its start and end dates, pushing a value into an array for each date.

Are either of those ways on the right path or is there a smarter more efficient way?

Note: I'm doing this using javascript with underscore and moment js for dates.

4

1 回答 1

0

遍历分配，然后是它的开始和结束日期，将每个日期的值推送到数组中

不知道你的意思是否正确。将日期（作为字符串键）映射到它们各自的计数（整数）的对象应该足够了，而不是推送到数组。这里的基本方面是您可以直接按日期处理计数（无循环）。

这些方法中的任何一种都在正确的道路上，还是有更聪明更有效的方法？

两者都在正确的道路上。它们中的哪一个更有效取决于您的数据，基本上，分配在您的日期范围内（甚至可能在外部？）内分布的稀疏程度。

Having
 a := number of assignments
 d := average duration of assignments (number of days per assignment)
 n := number of days in your range
then the runtimes would be
 O(a*d)    for iterating assignments and their duration
 O(a*d+n)  for that and building a result with all days
 O(a*n)    for iterating days and checking all assignments

由于您的结果结构是范围内的日期数组，因此您的第一种方法可能是更合适的选择。

如果您有非常大的数据集，并且可能有一些超出您的日期范围的作业，那么对作业进行排序可以为您带来额外的好处，因为您可以轻松过滤掉不相关的作业。

于 2013-05-27T10:34:06.927 回答