strstr () equivalente in C #

Question

Ho due byte[] e voglio trovare la prima occorrenza del secondo byte[] nella prima byte[] (o un intervallo in esso).

Non voglio usare le stringhe di efficienza (traducendo il primo byte[] ad un string sarà inefficiente).

In sostanza io credo che è quello che strstr() fa in C.

Qual è il modo migliore per farlo (in modo che sia efficiente e facile da usare)?

Questo è come dovrebbe essere simile:

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

Grazie!

UPDATE:

Voglio una soluzione che sarebbe più efficiente di una semplice ricerca. Questo significa che sfruttando il fatto che i buffer di confronto possono essere più efficienti deve essere usato - memcmp () è più efficiente rispetto iterare il byte .

Inoltre, so che ci sono algoritmi che gli scenari ottimizzare come questo:

• grande array: "12312351231234"
• piccola matrice: "1231234"
• algoritmo Naive: 7 paragona a scoprire che "1.231.235" è diverso da "1.231.234", 2 paragona a trovare il prossimo "1", 4 paragona a scoprire che "1235" è diverso da " 1231" , 3 paragona a trovare il prossimo '1', 7 confronta per trovare corrispondenza. Un totale di 7 + 2 + 4 + 3 + 7 = 23 confronta.
• Smart algoritmo: 7 paragona a scoprire che "1.231.235" è diverso da "1.231.234", direttamente salta al prossimo "1" (senza il confronto), 4 paragona a scoprire che "1235" è diverso da "1231", salta direttamente al di là del "5", 7 confronta per trovare la corrispondenza. Un totale di 7 + 4 + 7 = 18 confronta.

Answer 1

Non ho alcun codice per voi, ma il nome della soluzione più veloce si trova è il Boyer-Moore algoritmo. Si può fare meglio di O (n).

qui è un'implementazione per le stringhe su CodeProject. Si presenta come una conversione a byte[] non dovrebbe essere troppo difficile.

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

AGGIORNAMENTO; problema (si spera) fissa Henk mi ha avvisato a.

UPDATE 2: Affrontare aggiornamento alla domanda iniziale:

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 algoritmo teoria, è ben noto che l'ottimizzazione per la velocità costa memoria e viceversa. Il mio algoritmo utilizza un po 'più di memoria (non molto), ma in cambio analizza solo il grande schieramento di una volta.

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

La lista starts viene utilizzato per tenere traccia potenziali offset di inizio di smallArray in bigArray. Non sarà mai contenere più elementi rispetto al numero di occorrenze di smallArray[0] in smallArray (che può essere calcolato in anticipo per ottimizzare la lista e ridurre il numero di riassegnazioni di memoria). Quando non ci sono abbastanza byte lasciati in bigArray per contenere smallArray, non è provato, e quando è stato trovato smallArray, l'algoritmo si arresta. Si ferma anche quando è stata raggiunta la fine del bigArray. Perciò, il caso peggiore tempo di esecuzione sarebbe O (1), e l'utilizzo della memoria sarebbe O (1).

Ulteriori ottimizzazioni possibili includono l'utilizzo di puntatori nel codice non sicuro, e sostituendo lista da una matrice fissa la cui dimensione può essere calcolato in anticipo (come indicato in precedenza). Tuttavia, poiché nella lista offset errati vengono rimossi (più piccolo ciclo interno) ed in un array offset errati devono essere saltati (ciclo interno di dimensioni fisse, ma l'accesso elemento forse più veloce), che avrebbe dovuto benchmark che uno è più veloce.

Non importa anche se ci si aspetta smallArray ad essere grande o no. Quando si esegue, si potrebbe aggiungere un controllo per il ciclo while che verifica se starts.Length != 0 || offset <= (bigArrayOffset + bigArrayCount - smallArray.Length). In caso contrario, il ciclo può arrestare e sono stati trovati non occorrenze.

Answer 4

Ecco il mio prendere su una soluzione. E 'diviso in due. La prima parte cerca principalmente per un potenziale inizio. Se ne trova uno che la mette a confronto la lista da entrambe le estremità (per abbassare il numero di loop, che è fondamentalmente un micro ottimizzazione con un profiler, ma di solito è più veloce)

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