-2

我对此很陌生，我在做这件事时遇到了一些麻烦：

我有一个清单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

感谢四位您的帮助（请记住，我是 .net 的新手 :-)

编辑*

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

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

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

...

Utilities.IsBetween 检查一个值是否介于其他两个值之间（如果 3 介于 2 和 6 之间 -> true）

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

抱歉我的英语不好和c#技能不好......我对此很陌生

谢谢

4

4 回答 4

1

欢迎来到 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 完全在 rangeB 的“左侧”
  2. rangeA.Start > rangeB.End其中说： rangeA 完全在 rangeB 的“右侧”

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

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

但是，我注意到您的 between 测试不使用 ">=" 或 "<=" ，因此仅与另一个开始共享结束的范围不会相交。因此，09:00 - 10:00样本中的范围不会与样本中的10:00 - 11:00范围重叠。因此，您可能会使用>&<而不是>=&<=运算符。

如果您需要，我很乐意发布代码和结果。

于 2012-12-17T21:02:24.790 回答
0

你看到这个问题是因为你只得到“这个项目在另一个项目期间开始的项目”，而不包括“另一个项目在这个项目期间开始的项目”。

一个简单的解决方法是

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:10and 12:00 - 13:00。

但是，这（与您的原始版本一样）效率非常低 - O(n^2)，而 O(n) 算法应该是可能的。

于 2012-12-17T13:47:16.160 回答
0

想想你什么时候处理从12:30到的时间14:00

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

也就是说，您可以将查询更改为此（删除AsParallelandToList方法，因为它们不是解决方案的组成部分）：

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序列，甚至是您知道已经匹配和相交的项目（因为您没有将它们配对，所以您不需要说 item 与 item重叠，您只需返回它重叠）。ab

有了这个，您可以通过不使用 LINQ 来减少遍历 N^2 项的次数，但前提是您的集合已物化并实现了IList<T>接口，数组和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;
    }
}
于 2012-12-17T13:48:43.323 回答
0

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的 s 可能完全在初始范围内）。最后，如果我们正在检查的项目不在范围内，我们将重置所有状态变量并将它们视为我们的开始范围。

这样可以确保您只需要遍历一次集合，代价是事先对其进行排序（如果您可以确保它们首先排序到这一点，则无论如何都消除了这种需要）。希望有帮助，希望有更简单的方法。

于 2012-12-17T17:27:34.437 回答