7

パラメータとして 2 つの配列 (x と y) を指定し、x で y が最初に出現する開始インデックスを見つけます。最も単純または最速の実装は何だろうと思っています。

例：

when x = {1,2,4,2,3,4,5,6}
     y =       {2,3}
result
     starting index should be 3

更新:コードが間違っているため、質問から削除しました。

4

8 に答える 8

8

一番書きやすい？

    return (from i in Enumerable.Range(0, 1 + x.Length - y.Length)
            where x.Skip(i).Take(y.Length).SequenceEqual(y)
            select (int?)i).FirstOrDefault().GetValueOrDefault(-1);

もちろん、それほど効率的ではありません...もう少し似ています：

private static bool IsSubArrayEqual(int[] x, int[] y, int start) {
    for (int i = 0; i < y.Length; i++) {
        if (x[start++] != y[i]) return false;
    }
    return true;
}
public static int StartingIndex(this int[] x, int[] y) {
    int max = 1 + x.Length - y.Length;
    for(int i = 0 ; i < max ; i++) {
        if(IsSubArrayEqual(x,y,i)) return i;
    }
    return -1;
}
于 2009-11-23T00:00:08.903 に答える
7

これは、最初の配列だけでなく、配列のすべての出現を見つける単純な (しかしかなり効率的な) 実装です。

static class ArrayExtensions {

  public static IEnumerable<int> StartingIndex(this int[] x, int[] y) {
    IEnumerable<int> index = Enumerable.Range(0, x.Length - y.Length + 1);
    for (int i = 0; i < y.Length; i++) {
      index = index.Where(n => x[n + i] == y[i]).ToArray();
    }
    return index;
  }

}

例：

int[] x = { 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4 };
int[] y = { 2, 3 };
foreach (int i in x.StartingIndex(y)) {
  Console.WriteLine(i);
}

出力：

1
5
9

このメソッドは、最初に配列をループして、x配列内の最初の項目のすべてのオカレンスを検索しy、それらのインデックスをindex配列に配置します。y次に、それらのどれが配列の 2 番目の項目とも一致するかをチェックして、一致を減らします。配列内のすべての項目yがチェックされると、index配列には完全一致のみが含まれます。

編集:
代替の実装はToArray、ループ内のステートメントから呼び出しを削除して、次のようにすることです。

index = index.Where(n => x[n + i] == y[i]);

これにより、メソッドの動作が完全に変わります。アイテムをレベルごとにループする代わりに、ネストされた式を含む列挙子を返し、列挙子が反復されるまで検索を延期します。つまり、必要に応じて最初の一致のみを取得できます。

int index = x.StartingIndex(y).First();

これは、すべての一致を見つけてから最初の一致を返すわけではなく、最初の一致が見つかるまで検索してから返します。

于 2009-11-23T00:00:50.057 に答える
4

これはMark Gravell の回答に基づいていますが、一般的なものにして、例外がスローされないようにするための簡単な境界チェックを追加しました。

private static bool IsSubArrayEqual<T>(T[] source, T[] compare, int start) where T:IEquatable<T>
{
    if (compare.Length > source.Length - start)
    {
        //If the compare string is shorter than the test area it is not a match.
        return false;
    }

    for (int i = 0; i < compare.Length; i++)
    {
        if (source[start++].Equals(compare[i]) == false) return false;
    }
    return true;
}

Boyer-Mooreを実装することでさらに改善できますが、短いパターンでは問題なく動作します。

于 2012-05-10T15:00:27.083 に答える
4

The simplest way is probably this:

public static class ArrayExtensions
{
    private static bool isMatch(int[] x, int[] y, int index)
    {
        for (int j = 0; j < y.Length; ++j)
            if (x[j + index] != y[j]) return false;
        return true;
    }

    public static int IndexOf(this int[] x, int[] y)
    {
        for (int i = 0; i < x.Length - y.Length + 1; ++i)
            if (isMatch(x, y, i)) return i;
        return -1;
    }
}

But it's definitely not the fastest way.

于 2009-11-22T23:58:28.580 に答える
2

この場合、「最も単純」と「最も高速」は正反対です。さらに、高速なアルゴリズムを記述するには、ソース配列と検索配列が互いにどのように関連しているかについて多くのことを知る必要があります。

これは本質的に、文字列内の部分文字列を見つけることと同じ問題です。「the quick brown fox jumps over the lazy dog」で「fox」を探しているとします。この場合、単純な文字列一致アルゴリズムは非常に優れています。「banananananabanananabananabananabananananananananananana...」という形式の 100 万文字の文字列内で「bananananananananananananananananana」を検索する場合、単純な部分文字列マッチング アルゴリズムはひどいものです。より複雑で洗練された文字列マッチング アルゴリズムを使用すると、はるかに高速な結果が得られます。 . 基本的に、単純なアルゴリズムは O(nm) です。ここで、n と m はソース文字列と検索文字列の長さです。O(n+m) 個のアルゴリズムがありますが、はるかに複雑です。

検索しているデータについて詳しく教えてください。大きさ、冗長性、検索配列の長さ、不一致の可能性はどれくらいですか?

于 2009-11-23T00:23:39.600 に答える
1

I find something along the following lines more intuitive, but that may be a matter of taste.

public static class ArrayExtensions
{
    public static int StartingIndex(this int[] x, int[] y)
    {
        var xIndex = 0;
        while(xIndex < x.length)
        {
            var found = xIndex;
            var yIndex = 0;
            while(yIndex < y.length && xIndex < x.length && x[xIndex] == y[yIndex])
            {
                xIndex++;
                yIndex++;
            }

            if(yIndex == y.length-1)
            {
                return found;
            }

            xIndex = found + 1;
        }

        return -1;
    }
}

このコードは、x = {3, 3, 7}、y = {3, 7} のような場合に実装で発生する可能性があると思われる問題にも対処しています。あなたのコードで何が起こるかは、最初の数字と一致し、2 番目の数字でリセットされますが、一致を開始した直後のインデックスに戻るのではなく、3 番目で再び一致を開始することだと思います。何かが欠けている可能性がありますが、それは間違いなく考慮すべきものであり、コードで簡単に修正できるはずです。

于 2009-11-22T23:59:23.790 に答える
0 
    //this is the best in C#

    //bool contains(array,subarray)
    //  when find (subarray[0])
    //      while subarray[next] IS OK
    //          subarray.end then Return True
    public static bool ContainSubArray<T>(T[] findIn, out int found_index,
 params T[]toFind)
    {
        found_index = -1;
        if (toFind.Length < findIn.Length)
        {

            int index = 0;
            Func<int, bool> NextOk = (i) =>
                {
                    if(index < findIn.Length-1)
                        return findIn[++index].Equals(toFind[i]);
                    return false;
                };
            //----------
            int n=0;
            for (; index < findIn.Length; index++)
            {
                if (findIn[index].Equals(toFind[0]))
                {
                    found_index=index;n=1;
                    while (n < toFind.Length && NextOk(n))
                        n++;
                }
                if (n == toFind.Length)
                {
                    return true;
                }
            }

        }
        return false;
    }
于 2013-04-03T18:39:28.953 に答える