strstr () äquivalent in C #

Question

Ich habe zwei byte[] und ich möchte das erste Vorkommen des zweiten byte[] im ersten byte[] (oder einen Bereich darin) zu finden.

Ich mag nicht, Strings verwenden, um die Effizienz (den ersten byte[] zu einem string übersetzen wird ineffizient).

Im Grunde glaube ich, dass das, was strstr() in C der Fall ist.

Was ist der beste Weg, das zu tun (so es effizient sein und einfach zu bedienen)?

Dies ist, wie es aussehen sollte:

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

Danke!

UPDATE:

Ich möchte eine Lösung, die als eine einfache Suche effizienter wäre. Dies bedeutet, dass unter Verwendung der Tatsache, dass der Vergleich Puffer effizienter sein kann, sollte verwendet werden - memcmp () ist effizienter als die Iteration über Bytes .

Auch ich weiß, es gibt Algorithmen, die optimize Szenarien wie diese:

• big-Array: "12312351231234"
• kleine Array: "1231234"
• Naive Algorithmus: 7 vergleicht, dass "1231235" zu finden ist anders als "1231234", 2 vergleicht die nächste "1" zu finden, 4 Produkt zu finden, dass "1235" ist anders als " 1231" , 3 vergleicht die nächste zu finden ‚1‘, 7 vergleicht Übereinstimmung zu finden. Insgesamt 7 + 2 + 4 + 3 + 7 = 23 vergleicht.
• Smart-Algorithmus: 7 vergleicht, dass "1231235" zu finden ist anders als "1231234", direkt springt zum nächsten "1" (ohne Vergleich), 4 vergleicht, dass "1235" zu finden ist anders als „1231“, direkt über die „5“ springt, 7 vergleicht das Spiel zu finden. Insgesamt 7 + 4 + 7 = 18 vergleicht.

Answer 1

Ich habe keinen Code für Sie habe aber den Namen der schnellsten Lösung finden Sie die Boyer-Moore-Algorithmus . Es kann besser als O (n).

Hier ist eine Implementierung für Strings auf Codeproject. Sieht aus wie eine Umstellung auf byte[] sollte nicht allzu schwierig sein.

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

AKTUALISIERT; (Hoffentlich) Problem behoben, Henk alarmierte mich.

UPDATE 2: Adressierung Update ursprüngliche Frage:

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

In Algorithmus Theorie, ist es bekannt, dass für die Geschwindigkeit zu optimieren Kosten kehrt Speicher und umgekehrt. Mein Algorithmus verwendet ein bisschen mehr Speicher (nicht viel), aber im Gegenzug nur scannt das große Array einmal.

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

Die Liste starts wird verwendet, um potentielle Startverschiebungen von smallArray in bigArray zu verfolgen. Es wird nie mehr Elemente als die Anzahl der Vorkommen von smallArray[0] in smallArray enthalten (die im Voraus berechnet werden können, um die Liste und reduzieren die Anzahl der Speicher Umverteilungen zu optimieren). Wenn nicht genügend Bytes übrig sind in bigArray smallArray zu enthalten, ist es nicht versucht, und wenn smallArray gefunden wurde, stoppt der Algorithmus. Es hält auch wenn das Ende des bigArray erreicht ist. Daher wird die ungünstigste Laufzeit wäre O (1), und die Speichernutzung wäre O (1).

Weitere mögliche Optimierungen umfassen die Verwendung von Zeigern in unsicherem Code, und das Ersetzen die Liste mit einer festen Anordnung, deren Größe im Voraus berechnet werden (wie zuvor angegeben). Da jedoch in der Liste falsch Offsets (kleinere innere Schleife) entfernt werden und in einem Array falsch Offsets zu überspringen haben (feste Größe innere Schleife, aber möglicherweise schnellen Elementzugriff), dann würden Sie zu Benchmark haben, die man schneller ist.

Es ist ausserdem wichtig, ob Sie smallArray erwarten groß sein oder nicht. Wenn Sie das tun, könnten Sie einen Scheck an den while-Schleife, welche prüft, ob starts.Length != 0 || offset <= (bigArrayOffset + bigArrayCount - smallArray.Length) hinzuzufügen. Andernfalls kann die Schleife haben stoppen und keine Vorkommen gefunden.

Answer 4

Hier ist mein nehmen an einer Lösung. Es ist in zwei Teile gespalten. Der erste Teil sucht in erster Linie für einen möglichen Start. Wenn es einen findet es die vergleicht die Liste von beiden Enden (um die Schleifenzahl zu senken, die im Grunde ist eine Mikro-Optimierung mit einem Profiler aber in die Regel es ist schneller)

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