strstr () ما يعادل في c#

Question

لدي اثنين byte[] وأريد أن أجد أول حدث للثاني byte[] في الاول byte[] (أو نطاق فيه).

لا أريد استخدام سلاسل للكفاءة (ترجمة الأول byte[] إلى 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 مقارنة.

Answer 1

ليس لدي أي رمز لك ولكن اسم الحل الأسرع الذي ستجده هو بوير مور خوارزمية. يمكن أن تفعل أفضل من o (n).

هنا هو تطبيق للسلاسل على مشروع codeproject. يبدو وكأنه تحويل إلى byte[] لا ينبغي أن يكون صعبا للغاية.

Answer 2

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;
}

محدث؛ (نأمل) مشكلة ثابتة هينك نبهني إلى.

تحديث 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;
}

Answer 3

في نظرية الخوارزمية ، من المعروف جيدًا أن تحسين ذاكرة السرعة والعكس صحيح. تستخدم الخوارزمية الخاصة بي ذاكرة أكثر قليلاً (ليس كثيرًا) ولكن في المقابل فقط تقوم بمسح الصفيف الكبير مرة واحدة.

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;
}

القائمة starts يستخدم لتتبع التعويضات المحتملة smallArray في bigArray. لن تحتوي أبدًا على عناصر أكثر من عدد حوادث smallArray[0] في smallArray (والتي يمكن حسابها مقدمًا لتحسين القائمة وتقليل عدد عمليات إعادة تخصيص الذاكرة). عندما لا يكون هناك ما يكفي من البايتات bigArray لاحتواء smallArray, ، لم تتم محاكمة ومتى smallArray تم العثور عليه ، تتوقف الخوارزمية. يتوقف أيضًا عند نهاية bigArray تم الوصول إليه. لذلك ، سيكون أسوأ وقت تشغيل هو O (1) ، وسيكون استخدام الذاكرة O (1).

تتضمن التحسينات الممكنة الإضافية استخدام مؤشرات في رمز غير آمن ، واستبدال القائمة بواسطة صفيف ثابت يمكن حساب حجمه مسبقًا (كما هو مذكور من قبل). ومع ذلك ، لأنه في القائمة تتم إزالة الإزاحة الخاطئة (حلقة داخلية أصغر) وفي صفيف ، يجب تخطي إزاحة خاطئة (حلقة داخلية ذات حجم ثابت ولكن من المحتمل أن يكون لديك إمكانية الوصول إلى العناصر بشكل أسرع) ، يجب أن تقوم بتقييم أي واحد أسرع.

من المهم أيضًا ما إذا كنت تتوقع smallArray لتكون كبيرة أم لا. عندما تفعل ذلك ، يمكنك إضافة شيك إلى الحلقة التي تتحقق سواء starts.Length != 0 || offset <= (bigArrayOffset + bigArrayCount - smallArray.Length). وإلا فإن الحلقة قد تتوقف ولم يتم العثور على أي أحداث.

Answer 4

هذا هو رأيي في حل. إنه منقسم إلى قسمين. يبحث الجزء الأول بشكل رئيسي عن بداية محتملة. إذا وجدت واحدة ، فإنها تقارن القائمة من كلا الطرفين (لخفض عدد الحلقة وهو في الأساس تحسينًا صغيرًا مع البذيئة ولكن عادة انه اسرع)

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;
    }
}