2

リストに別のリスト（順序を保持）が含まれているかどうかを確認するための効率的で簡単な方法を見つけるのに苦労しています。これはstring.Contains（string）機能に類似しています。

私がintの4つのコレクションを持っているとしましょう：

 A = [1, 2, 3, 4, 5]
 B = [2, 3]
 C = [5, 6, 7]
 D = [3, 2, 4]

A.Contains(B)は真ですが、A.Contains(C)とA.Contains(D)は偽です。

助けることができればイテレータを使用したくないのですが、それを行うための効率的な方法を想像することはできません。次のコードは非常に非効率的です。

 public static bool IsSequentiallyEqual<T>(this IEnumerable<T> lhs, IEnumerable<T> rhs)
 {
      return lhs.Zip(rhs, (a, b) => a.Equals(b)).All(isEqual => isEqual == true);
 }

 public static bool StartsWith<T>(this IEnumerable<T> haystack, IEnumerable<T> needle)
 {
      return haystack.Take(needle.Count()).IsSequentiallyEqual(needle);
 }

 public static bool Contains<T>(this IEnumerable<T> haystack, IEnumerable<T> needle)
 {
      var result = list.SkipWhile((ele, index) => haystack.Skip(index).StartsWith(needle));
      return result.Count() >= needle.Count();
 }
4

4 に答える 4

2 
public static bool Contains<T>(this IEnumerable<T> first, IEnumerable<T> second)
 {
      return string.Join("~", first).Contains(string.Join("~", second));
 }

少し「ぎこちない」ものではなく、少なくとも長い長いリストの作業は避けてください。

public static bool Contains<T>(this IEnumerable<T> first, IEnumerable<T> second)
   {
       //trying to avoid multiple enumeration
        var firstList = first.ToList();
        var secondList = second.ToList();

        if (!secondList.Any(firstList.Contains)) return false;
        if (secondList.Count() > firstList.Count()) return false;
        if (Math.Max(firstList.Count(), secondList.Count()) > 99999)
             throw new ShouldNotUseThisUglyMethodException("I'm too kludgy to be used. Let me die...");
        return string.Join("~", firstList).Contains(string.Join("~", secondList));
    }
于 2012-05-24T23:20:40.967 に答える
1 
public static bool Contains<T>(this IEnumerable<T> haystack, IEnumerable<T> needle)
{
    var hayList = haystack.ToList();
    var needleList = needle.ToList();
    return Enumerable.Range(0, hayList.Count)
                     .Select(start => hayList.Skip(start).Take(needleList.Count))
                     .Any( subsequence => subsequence.SequenceEqual(needleList));
}
于 2012-05-25T05:34:54.753 に答える
0

このバージョンでは、キューを使用して可能なサブシーケンスを格納します。haystack最初のを除いて1回だけ反復しTake()、一致するものが見つかると反復を停止します。ただし、LINQステートメントの変数を変更します。

public static bool Contains<T>(this IEnumerable<T> haystack, IEnumerable<T> needle)
{
    var needleList = needle.ToList();
    var queue = new Queue<T>(haystack.Take(needleList.Count - 1));
    return haystack.Skip(needleList.Count - 1)
                   .Any( hay =>   
                       {
                           queue.Enqueue(hay);
                           bool areEqual = queue.SequenceEqual(needleList);
                           queue.Dequeue();
                           return areEqual;
                       });  
}
于 2012-05-25T15:01:09.337 に答える
-1

ハッシュの仕事を使用してください。すぐにfalseを返すために実行できるチェックがいくつかあることに注意してください。ただし、ここではプロセスの要点のみを示します。ここにそれは便利な拡張フォーマットです：

注文を処理するように更新

void Main()
{
    var first        = new List<int>() { 1, 2, 5 };
    var firstInOrder = new List<int>() { 1, 2, 3 };
    var second       = new List<int>() { 1, 2, 3, 4, 5 };
    var third        = new List<int>() { 1, 10, 20 };

    Console.WriteLine( first.FoundInOther( second ) );        // False
    Console.WriteLine( firstInOrder.FoundInOther( second ) ); // True
    Console.WriteLine( first.FoundInOther( third ) );         // False

}

public static class NumberExtensions
{

    public static bool FoundInOther( this IEnumerable<int> initial, IEnumerable<int> other )
    {
        int index = -1;
        var asDictionary = other.ToDictionary( itm => itm, itm => ++index );

        index = -1;
        return initial.All( oth => asDictionary.ContainsKey( oth ) && (asDictionary[oth] == ++index));
    }

}
于 2012-05-24T23:34:31.857 に答える