1

リスト B で検索したいジェネリック ドット NET リスト A があります。リスト B でリスト A を検索するにはどうすればよいですか? リスト A がリスト B で始まる場所のインデックスが必要です。

4

4 に答える 4

2

これは、この回答の一般的な実装であり、any を許可IListし、optional を渡すことができますIEqualityComparer。これは最速の検索方法ではありませんが、より高度な回答を得るには良い出発点です。

static class GenericSearcher
{

    static readonly int[] Empty = new int[0];

    public static int[] Locate<T>(this IList<T> self, IList<T> candidate)
    {
        return Locate(self, candidate, EqualityComparer<T>.Default);
    }

    public static int[] Locate<T>(this IList<T> self, IList<T> candidate, IEqualityComparer<T> comparer)
    {
        if (IsEmptyLocate(self, candidate))
            return Empty;

        var list = new List<int>();

        for (int i = 0; i < self.Count; i++)
        {
            if (!IsMatch(self, i, candidate, comparer))
                continue;

            list.Add(i);
        }

        return list.Count == 0 ? Empty : list.ToArray();
    }

    static bool IsMatch<T>(IList<T> array, int position, IList<T> candidate, IEqualityComparer<T> comparer)
    {
        if (candidate.Count > (array.Count - position))
            return false;

        for (int i = 0; i < candidate.Count; i++)
            if (comparer.Equals(array[position + i],candidate[i]) == false)
                return false;

        return true;
    }

    static bool IsEmptyLocate<T>(ICollection<T> array, ICollection<T> candidate)
    {
        return array == null
            || candidate == null
            || array.Count == 0
            || candidate.Count == 0
            || candidate.Count > array.Count;
    }

}

VBコードで更新（ajakblackgoatに感謝）：

Module GenericSearcher

    Private ReadOnly Empty As Integer() = New Integer(-1) {}

    <System.Runtime.CompilerServices.Extension> _
    Public Function Locate(Of T)(self As IList(Of T), candidate As IList(Of T)) As Integer()
        Return Locate(self, candidate, EqualityComparer(Of T).[Default])
    End Function

    <System.Runtime.CompilerServices.Extension> _
    Public Function Locate(Of T)(self As IList(Of T), candidate As IList(Of T), comparer As IEqualityComparer(Of T)) As Integer()
        If IsEmptyLocate(self, candidate) Then
            Return Empty
        End If

        Dim list = New List(Of Integer)()

        For i As Integer = 0 To self.Count - 1
            If Not IsMatch(self, i, candidate, comparer) Then
                Continue For
            End If

            list.Add(i)
        Next

        Return If(list.Count = 0, Empty, list.ToArray())
    End Function

    Private Function IsMatch(Of T)(array As IList(Of T), position As Integer, candidate As IList(Of T), comparer As IEqualityComparer(Of T)) As Boolean
        If candidate.Count > (array.Count - position) Then
            Return False
        End If

        For i As Integer = 0 To candidate.Count - 1
            If Not comparer.Equals(array(position + i), candidate(i)) Then
                Return False
            End If
        Next

        Return True
    End Function

    Private Function IsEmptyLocate(Of T)(array As ICollection(Of T), candidate As ICollection(Of T)) As Boolean
        Return array Is Nothing OrElse candidate Is Nothing OrElse array.Count = 0 OrElse candidate.Count = 0 OrElse candidate.Count > array.Count
    End Function

End Module
于 2013-06-18T01:55:07.777 に答える
2

という非常に素朴なアプローチがありO(|A| * |B|)ます。基本的に、これは単純な部分文字列検索アルゴリズムです1 :

for(int i = 0; i < B.Count - A.Count; i++) {
     bool matchPossible = true;
     for(int j = 0; matchPossible && j < A.Count; j++) {
         if (!B[i + j].Equals(A[j])) { // should check for B[i + j] == null
              matchPossible = false;
              break;
         }
     }
     if(matchPossible) {
         return i;
     }
 }     
 return -1;

アプローチに集中できるように、実行すべき明らかなエラー チェックを省略しました。明らかなチェックの1つにコメントしました。Bこれにより、検索できる場所のインデックスが得られますA 。

アプローチがあなたを引きずっていることをベンチマークが示さない限り、私はこれに固執します. もしそうなら、Knuth-Morris-Pratt のようなもっと洗練されたものを調べる必要があります。

ListAと Listの両方Bが次のように宣言されていList<string>ます。LINQでこれを行う方法があるかもしれないと思っていましたか? リストA内のリストを検索しBますか?

もちろん。

for(int i = 0; i < B.Count - A.Count; i++) {
    if(B.SequenceEqual(A.Skip(i).Take(B.Count))) {
        return i;
    }
}
return -1;

これは基本的には上で示したアルゴリズムと同じですが、もう少しきれいに表現されていることに注意してください。ただし、このアプローチには欠点があります。Enumerable.Skip利用可能なときにインデクサーを使用するのに十分スマートかどうかはわかりません。このバージョンは、インデクサーを使用しない場合、元のバージョンよりもパフォーマンスが低下する可能性があります。これが、最初のアプローチでこれを使用しなかった理由です。

また、VB.NET に変換する必要があります。私はコンパイラを手元に持っておらず、流暢な C# を話します (構文をチェックするためにコンパイラは必要ありません) が、VB は話せません。

1 : 何らかの理由で、このアプローチが K&R の小さな C の本でカバーされているという突然のフラッシュバックがありましたか? 誰でも確認できますか。私のコピーが今どこにあるのかわからないのですか？2

2 : 見つけた。はい、セクション 4.1 です。機能はstrindex.

于 2013-06-18T01:43:49.310 に答える
1

ListAとを受け取るこの関数を試してくださいListB:

Dim index As Integer = listB.IndexOf(listA(0))
Dim iCont As Integer
Dim bMatch As Boolean

While index >= 0
    bMatch = True
    iCont = 1

    'Check if lists match on all the items in list A
    While bMatch
        index += 1
        bMatch = (index < listB.Count) AndAlso (listA(iCont) = listB(index))

        iCont += 1
        If iCont >= ListA.Count Then Exit While
    End While         

    If bMatch Then Exit While
    index = listB.IndexOf(listA(0), index)
End While

return bMatch
于 2013-06-18T07:24:33.627 に答える