LINQ的：获取相交

Question

我是新来这个项目，我有一个小麻烦要做到这一点：

我有timeitems列表：

06:40 - 07:10 
06:55 - 07:13 
07:00 - 08:35 
07:13 - 07:14 
09:00 - 10:00 
10:00 - 11:00 
12:00 - 13:00 
12:30 - 14:00 

现在我想相交的所有项目：

06:40 - 07:10 
06:55 - 07:13 
07:00 - 08:35 
07:13 - 07:14 

12:00 - 13:00 
12:30 - 14:00 


var intersects = timeitems 
      .Where(a => timeitems 
      .Any(b => Utilities.IsBetween(a.SpanRangeStartIndex, b.SpanRangeStartIndex, b.SpanRangeEndIndex))) 
      .AsParallel() 
      .ToList(); 

但我只得到这一点，我不知道为什么：

06:55 - 07:13 
07:00 - 08:35 
07:13 - 07:14 

12:30 - 14:00 

感谢Four的帮助（请记住，我是新来的.NET :-)

编辑*

OK，一个timeitem IST只是一个具有两个属性的项目列表：

项目1（SpanRangeStartIndex = 06：40 SpanRangeEndIndex = 07：10）

项目2（SpanRangeStartIndex = 06：55 SpanRangeEndIndex = 07：13）

...

如果

Utilities.IsBetween检查的值是其他两个值之间（如果3是2到6 - >真）

public static bool IsBetween(int value, int start, int end) 
    { 
     return (value > start) & (value <end); 
    } 

对不起，我英文不好和坏的C＃-skill ......我很新这个

感谢

Answer 1

你会看到这个问题，因为你只得到“项目，使得该项目的另一项目时开始”，并没有包括“项目，使得另一个项目此项目中启动”。

一个简单的修正将是

var intersects = timeitems 
    .Where(a => timeitems.Any(b => 
     Utilities.IsBetween(a.SpanRangeStartIndex, 
      b.SpanRangeStartIndex, b.SpanRangeEndIndex) || 
     Utilities.IsBetween(b.SpanRangeStartIndex, 
      a.SpanRangeStartIndex, a.SpanRangeEndIndex))) 
    .AsParallel() 
    .ToList(); 

这使你的代码对称，将包括失踪06:40 - 07:10和12:00 - 13:00。但是，这个（与原来的一样）是非常低效的--O（n^2），当一个O（n）算法应该是可能的。

Answer 2

认为当你正在处理从12:30时间14:00

前面的元素（从12:00到13:00）的与该窗口相交，但是您的查询错过它，因为你只检查，看看是否开始时间在您必须检查结束时间是否在范围内的范围内。

这就是说，你可以查询更改这个（删除AsParallel和ToList方法，因为它们没有被整合到解决方案）：

var intersects = timeitems 
    .Where(a => timeitems 
     .Any(b => 
      // Check the start of the window... 
      Utilities.IsBetween(a.SpanRangeStartIndex, 
       b.SpanRangeStartIndex, b.SpanRangeEndIndex) && 
      // *AND* the end of the window... 
      Utilities.IsBetween(a.SpanRangeEndIndex, 
       b.SpanRangeStartIndex, b.SpanRangeEndIndex))); 

现在，你通过整个迭代timeItems顺序为每项目，甚至你知道已经匹配和相交的项目（因为你不配对他们，你不需要说项目a重叠项目b，你只需要返回它重叠）。

有了这个，你可以通过不使用LINQ来减少必须遍历N^2个项目，但只有当你的集合被实现并实现了IList<T> interface，这个数组和List<T>实例）。

你会向前看，保持跟踪什么重叠，并取得了，就像这样：

public IEnumerable<TimeItem> GetOverlappingItems(this IList<TimeItem> source) 
{ 
    // Validate parameters. 
    if (source == null) throw new ArgumentNullException("source"); 

    // The indexes to ignore that have been yielded. 
    var yielded = new HashSet<int>(); 

    // Iterate using indexer. 
    for (int index = 0; index < source.Count; ++index) 
    { 
     // If the index is in the hash set then skip. 
     if (yielded.Contains(index)) continue; 

     // Did the look ahead yield anything? 
     bool lookAheadYielded = false; 

     // The item. 
     TimeItem item = source[index]; 

     // Cycle through the rest of the indexes which are 
     // not in the hashset. 
     for (int lookAhead = index + 1; lookAhead < source.Count; ++lookAhead) 
     { 
      // If the item has been yielded, skip. 
      if (yielded.Contains(lookAhead)) continue; 

      // Get the other time item. 
      TimeItem other = source[lookAhead]; 

      // Compare the two. See if the start or the end 
      // is between the look ahead. 
      if (Utilities.IsBetween(item.SpanRangeStartIndex, 
        other.SpanRangeStartIndex, other.SpanRangeEndIndex) || 
       Utilities.IsBetween(item.SpanRangeEndIndex, 
        other.SpanRangeStartIndex, other.SpanRangeEndIndex)) 
      { 
       // This is going to be yielded. 
       lookAheadYielded = true; 

       // Yield the item. 
       yield return other; 

       // Add the index to the hashset of what was yielded. 
       yielded.Add(lookAhead); 
      } 
     } 

     // Was a look ahead yielded? 
     // No need to store the index, we're only moving 
     // forward and this index doesn't matter anymore. 
     if (lookAheadYielded) yield return item; 
    } 
} 

Answer 3

LINQ可能不是一个好主意，在这里，因为你在做重复计算了不少。如果你可以假设它们都是按照起始索引排序的（如果你无法做出保证，那么你可以使用LINQ来订购它），那么迭代它们时保持一个滚动窗口会更容易：

timeitem workingRange = null, rangeStart = null; 
bool matched = false; 
foreach(timeitem t in timeitems) // timeitems.OrderBy(ti => ti.SpanRangeStartIndex) if unsorted 
{ 
    if(workingRange is null) 
    { 
     rangeStart = t; 
     workingRange = new timeitem { SpanRangeStartIndex = t.SpanRangeStartIndex, SpanRangeEndIndex = t.SpanRangeEndIndex }; 
     continue; 
    } 

    if(Utilities.IsBetween(t.SpanRangeStartIndex, 
     workingRange.SpanRangeStartIndex, workingRange.SpanRangeEndIndex)) 
    { 
     if(!matched) 
     { 
      matched = true; 
      yield return rangeStart; 
     } 
     workingRange.SpanRangeEndIndex = Math.Max(workingRange.SpanRangeEndIndex, t.SpanRangeEndIndex); 
     yield return t; 
    } 
    else 
    { 
     matched = false; 
     rangeStart = t 
     workingRange = new timeitem { SpanRangeStartIndex = t.SpanRangeStartIndex, SpanRangeEndIndex = t.SpanRangeEndIndex }; 
    } 
} 

一些注意事项。保留范围的原始第一项的引用，因为我不知道它是否是结构/类，并且除非您正在执行某种转换，否则最好产生原始项目。工作范围可以很容易地修改为使用DateTime（这可能更容易阅读/理解）。我们需要跟踪我们是否匹配，因为我们仍然需要产生/返回原始工作项目，并确保我们不会再次产生它（不能使用范围作为度量，因为后续的timeitem可能是完全在初始范围内）。最后，如果我们检查的项目不在范围内，我们重置所有状态变量并将它们作为我们的开始范围。

这可以确保您只需要一次遍历集合，而不必事先对其进行排序（如果您可以确保他们首先排序，则首先排除该需求）。希望有所帮助，希望有一个更简单的方法。

Answer 4

欢迎来到SO！

我相信你要解决的问题是你想知道你的范围集合中的哪些范围与同一集合中的任何其他范围重叠。

这个问题似乎是你测试范围的一端“之间”，而不是另一端。 （我写了一个示例程序，做你自己做的，并添加了一些注释，并从属性名称以及.AsParallel()调用中删除了“SpanRange”和“Index” - 这可能会改变返回的数据的顺序，但仍然有相同的整体内容。）

var intersects = 
    data.Where(a => data 
     .Any(b => 
      IsBetween(a.Start, b.Start, b.End) // <-- this is the test you did 
      || IsBetween(a.End, b.Start, b.End) // <-- the missing other end 
//   || IsBetween(b.Start, a.Start, a.End) // potentially necessary 
//   || IsBetween(b.End, a.Start, a.End) // potentially necessary 
     )); 

我加入了另外两个评论IsBetween电话，因为我觉得有可能是“完全包含”可能无法显示当一个范围完全在另一个内包含的范围测试。

在不同的音符，我可能会尝试改变你如何测试范围时，通过相交的两个范围怎么也不会相交的简单的情况的第一思维思考一点点。

1. rangeA.End < rangeB.Start它说：要么当

   两个区域不相交rangeA完全是“以左”范围b

2. rangeA.Start > rangeB.End它说：rangeA完全是“以权”范围b

doNotIntersect = (rangeA.End < rangeB.Start) || (rangeA.Start > rangeB.End)

因此，我们可以测试是否范围相交通过否定上述EXPRES锡永：
isIntersecting = (rangeA.End >= rangeB.Start) && (rangeA.Start <= rangeB.End)

然而，我注意到，你之间的测试不使用“> =”或“< =”，这样只共享与其他的开始结束了一系列不相交。因此，样本中的09:00 - 10:00范围不会与样本中的10:00 - 11:00范围重叠。所以，很可能你会使用> & <而非>= & <=运营商。

我会很高兴，如果你需要它张贴代码和结果。