-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 は 2 つのプロパティを持つアイテムの単なるリストではありません:

Item1(SpanRangeStartIndex=06:40 SpanRangeEndIndex=07:10)

Item2(SpanRangeStartIndex=06:55 SpanRangeEndIndex=07:13)

...

Utilities.IsBetween は、値が他の 2 つの値の間にあるかどうかをチェックします (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へようこそ！

あなたが解決しようとしている問題は、一連の範囲のどの範囲が同じセットの他の範囲と重複しているかを知りたいということだと思います。

問題は、「間」の範囲の一方の端をテストし、もう一方の端をテストしないことです。(私は、あなたが行うことを行うサンプル プログラムを作成し、いくつかのコメントを追加し、プロパティ名と呼び出しから「SpanRange」と「Index」を削除しました。.AsParallel()これにより、返されるデータの順序が変わる可能性がありますが、全体的には同じです。コンテンツ。）

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ある範囲が別の範囲内に完全に含まれている場合に表示に失敗する可能性がある「完全に含まれる」範囲テストがある可能性があると思うので、他の 2 つのコメント付き呼び出しを追加しました。

別の注意として、2 つの範囲がどのように交差しないかという単純なケースを最初に考えることによって、範囲がいつ交差するかをテストする方法について、あなたの考えを少し変えようとするかもしれません。

次のいずれかの場合、2 つの範囲は交差しません。

  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

多くの二重カウントを行っているため、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 に答える
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:10している と が含まれ12:00 - 13:00ます。

ただし、これは（オリジナルと同様に）非常に非効率的です-O（n ^ 2）、O（n）アルゴリズムが可能である必要があります。

于 2012-12-17T13:47:16.160 に答える
0

12:30からまでの時間を扱っているときを考えてください14:00

前の要素 ( from 12:00to ) はそのウィンドウと交差していますが、終了時刻が範囲内にあるかどうかを確認する必要があるときに、開始時刻が範囲内にある13:00かどうかのみを確認しているため、クエリはそれを見逃しています。

つまり、クエリを次のように変更できます (ソリューションに不可欠ではないため、 AsParallelandメソッドを削除しました)。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)));

現在、すべてのアイテムのシーケンス全体 を繰り返し処理しています。既に一致して交差していることがわかっているアイテムも含めます (それらをペアリングしていないため、 item が itemと重複していると言う必要はありません。単に重複していることを返す）。timeItemsab

これを使用すると、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 に答える