3

私は2つ持っていて、最初の2番目のオカレンス（またはその中の範囲）byte[]を見つけたいと思っています。byte[]byte[]

効率を上げるために文字列を使用したくありません（最初の文字列byte[]をaに変換stringすると非効率になります）。

基本的に私はそれstrstr()がCで何をするかだと信じています。

それを行うための最良の方法は何ですか（効率的で使いやすいように）？

これはどのように見えるべきかです：

int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, int bigArrayCount, byte[] smallArray);

ありがとう！

アップデート：

単純な検索よりも効率的なソリューションが必要です。これは、バッファの比較がより効率的であるという事実を使用する必要があることを意味します-memcmp（）は、バイトを反復処理するよりも効率的です。

また、次のようなシナリオを最適化するアルゴリズムがあることも知っています。

  • ビッグアレイ： "12312351231234"
  • 小さな配列： "1231234"
  • ナイーブアルゴリズム： 7は「1231235」が「1231234」と異なることを見つけるために比較し、2は次の「1」を見つけるために比較し、4は「1235」が「1231」と異なることを見つけるために比較し、3は次の「 1 "、7は一致を見つけるために比較します。合計7+2 + 4 + 3 + 7=23が比較されます。
  • スマートアルゴリズム： 7は、「1231235」が「1231234」とは異なることを確認するために比較し、（比較せずに）次の「1」に直接ジャンプします。4は、「1235」が「1231」とは異なることを確認するために比較し、 「5」、7は一致を見つけるために比較します。合計7+4 + 7=18が比較されます。
4

4 に答える 4

3

コードはありませんが、最速のソリューションの名前はBoyer-Mooreアルゴリズムです。O（n）よりもうまくいく可能性があります。

CodeProjectの文字列の実装を次に示します。への変換byte[]はそれほど難しくないようです。

于 2010-08-21T09:41:46.890 に答える
1 
int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, 
                               int bigArrayCount, byte[] smallArray)
{
     byte first = smallArray[0];
     bool cont= true;
     while (cont && 
            bigArrayOffset=Array.IndexOf(bigArray, first, bigArrayOffset) != -1)
     {
         if (bigArrayOffset + smallArray.Length > bigArray.Length)
         {
              bigArrayOffset = -1;
              break;
         }
         cont= false;
         for(int i=1; i< smallArray.Length; ++i)
         {
              if (bigArray[bigArrayOffset+i] != smallArray[i])
              { 
                 ++bigArrayOffset;
                 cont = true;
                 break;
              }
         }
     }
     return bigArrayOffset;
}

更新しました; (願わくば) Henk が警告してくれた問題を修正しました。

更新 2: 元の質問への更新への対応:

int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, 
                               int bigArrayCount, byte[] smallArray)
{
     int bigArrayEnd = Math.Min(bigArrayCount + bigArrayOffset, bigArray.Length)
     byte first = smallArray[0];
     bool cont= true;
     while (cont && 
            bigArrayOffset=Array.IndexOf(bigArray, first, bigArrayOffset) != -1)
     {
         int bookmark = bigArrauOffset + 1;
         bool bookmarkset = false;
         if (bigArrayOffset + smallArray.Length > bigArrayEnd )
         {
              bigArrayOffset = -1;
              break;
         }
         cont= false;
         for(int i=1; i< smallArray.Length; ++i)
         {
              if (!bookmarkset && bigArray[bigArrayOffset+i] == first)
              {
                   bookmark = bigArrayOffset+i;
                   bookmarkset = true;
              }
              if (bigArray[bigArrayOffset+i] != smallArray[i])
              { 
                 bigArrayOffset = bookmark;
                 cont = true;
                 break;
              }
         }
     }
     return bigArrayOffset;
}
于 2010-08-21T08:50:24.880 に答える
0

これが私の解決策です。2つに分かれています。最初の部分は、主に潜在的なスタートを探します。見つかった場合は、両端からのリストを比較します (基本的にプロファイラーを使用しないマイクロ最適化であるループ カウントを下げるためですが、通常は高速です) 。

int GetOffsetOfArrayInArray(byte[] bigArray,
                        int bigArrayOffset,
                        int bigArrayCount,
                        byte[] smallArray)
    {
        var length = smallArray.Length;
        var lastPossibleStart = bigArray.Length - length;
        var startByte = smallArray[0];

        for (var first = bigArrayOffset; first < lastPossibleStart; first++)
        {
           if (bigArray[first] == startByte &&
               check(bigArray, smallArray, first, length))
           {
              return first;
           }
        }
        return -1;
    }

    bool check(byte[] bigArray, byte[] smallArray, int first, int length)
    {
        var smallIndex = 0;
        var smallLast = length - 1;
        var last = first + length - 1;
        for (var i = first; smallIndex <= smallLast; i++)
        {
            if (bigArray[i] != smallArray[smallIndex] ||
                 bigArray[last] != smallArray[smallLast])
            {
                return false;
            }
            smallIndex = i - first + 1;
            last--;
            smallLast--;
        }
        return true;
    }
}
于 2010-08-21T10:55:29.693 に答える
0

アルゴリズム理論では、速度を最適化するとメモリが消費され、その逆も同様であることがよく知られています。私のアルゴリズムはもう少し多くのメモリを使用しますが (あまり多くはありません)、代わりに大きな配列を 1 回だけスキャンします。

public static int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, int bigArrayCount, byte[] smallArray)
{
    // TODO: Check whether none of the variables are null or out of range.
    if (smallArray.Length == 0)
        return 0;

    List<int> starts = new List<int>();    // Limited number of elements.

    int offset = bigArrayOffset;
    // A single pass through the big array.
    while (offset < bigArrayOffset + bigArrayCount)
    {
        for (int i = 0; i < starts.Count; i++)
        {
            if (bigArray[offset] != smallArray[offset - starts[i]])
            {
                // Remove starts[i] from the list.
                starts.RemoveAt(i);
                i--;
            }
            else if (offset - starts[i] == smallArray.Length - 1)
            {
                // Found a match.
                return starts[i];
            }
        }
        if (bigArray[offset] == smallArray[0] &&
            offset <= (bigArrayOffset + bigArrayCount - smallArray.Length))
        {
            if (smallArray.Length > 1)
                // Add the start to the list.
                starts.Add(offset);
            else
                // Found a match.
                return offset;
        }
        offset++;
    }
    return -1;
}

リストは、 instartsの潜在的な開始オフセットを追跡するために使用されます。inの出現回数よりも多くの要素が含まれることはありません(リストを最適化し、メモリの再割り当ての回数を減らすために事前に計算される場合があります)。を含むのに十分なバイト数が残っていない場合は試行されず、 が見つかった場合、アルゴリズムは停止します。の最後に達すると停止します。したがって、最悪の場合の実行時間は O(1) になり、メモリ使用量は O(1) になります。smallArraybigArraysmallArray[0]smallArraybigArraysmallArraysmallArraybigArray

さらに考えられる最適化には、アンセーフ コードでのポインターの使用、およびサイズを事前に計算できる固定配列によるリストの置き換えが含まれます (前述のとおり)。ただし、リストでは間違ったオフセットが削除され (小さい内側のループ)、配列では間違ったオフセットがスキップされなければならないため (固定サイズの内側のループですが、要素へのアクセスが高速になる可能性があります)、どちらが高速かをベンチマークする必要があります。

また、大きくなると予想するかどうかも重要ですsmallArray。その場合、while ループにチェックを追加して、starts.Length != 0 || offset <= (bigArrayOffset + bigArrayCount - smallArray.Length). そうしないと、ループが停止し、オカレンスが見つからない可能性があります。

于 2010-08-21T12:59:01.693 に答える