Finden übereinstimmende aufeinanderfolgende Ganzzahlen im Array

Question

Gegeben zwei Arrays mit Ganzzahlen, herauszufinden, ob drei aufeinanderfolgende Ganzzahlen in beiden Arrays vorhanden sind oder nicht. Zum Beispiel: A = [1, 4, 5, 7, 2] und B = [3, 1, 4, 5, 9] ergibt "wahr"/1, weil [1, 4, 5] in vorhanden ist beide Arrays.

Meine Lösung für diese Aufgabe ist unten aufgeführt, aber ich habe das Gefühl, dass es eine optimierte Lösung geben muss.

int consecutiveInts(int *a, int sizeA, int *b, int sizeB){ 
    int i, j; 

    // Iterate over every integer in array b for every integer in array a. 
    for (i = 0 ; i < sizeA - 2 ; i++){ 
     for (j = 0 ; j < sizeB - 2 ; j++){ 
      if (a[i] == b[j] && a[i + 1] == b[j + 1] && a[i + 2] == b[j + 2]) 
       return 1; 
     } 
    } 
    return 0; 
} 

Answer 1

Für kleine Arrays ist der OP-Ansatz in Ordnung. Für Array-Längen hat es O(m*n) Laufzeit.

Eine Alternative erstellt 2 Wertearrays, sortiert sie und sucht dann nach einem gemeinsamen Element. Es hat O(m*log2(m) + n*log2(n)) Laufzeit. Sicherlich schneller mit großen Arrays als OP-Code.

typedef struct { 
    int i[3]; 
} int3; 

void Init3(int3 *i3, const int *i, size_t n) { 
    while (n--) { 
    i3[n].i[0] = i[n]; 
    i3[n].i[1] = i[n + 1]; 
    i3[n].i[2] = i[n + 2]; 
    } 
} 

int fcmp(const void *a, const void *b) { 
    return memcmp(a, b, sizeof (int3)); 
} 

bool Pattern3(const int *a, size_t size_a, const int *b, size_t size_b) { 
    if (size_a < 3 || size_b < 3) return false; 

    int3 a3[size_a - 2]; 
    Init3(a3, a, size_a - 2); 
    qsort(a3, size_a - 2, sizeof *a3, fcmp); 

    int3 b3[size_b - 2]; 
    Init3(b3, b, size_b - 2); 
    qsort(b3, size_b - 2, sizeof *b3, fcmp); 

    while (size_a && size_b) { 
    int cmp = fcmp(&a[size_a - 1], &b[size_b - 1]); 
    if (cmp == 0) return true; 
    if (cmp > 0) size_a--; 
    else size_b--; 
    } 
    return false; 
} 

int main() { 
    int A[] = { 1, 4, 5, 7, 2 }; 
    int B[] = { 3, 1, 4, 5, 9 }; 
    printf("%d\n", Pattern3(A, sizeof A/sizeof *A, B, sizeof B/sizeof *B)); 
} 

wäre eine Alternative eine bsearch() anstatt die zweite int3 b3[]/qsort() Formular.

Answer 2

Ich glaube, ich kann nicht falsch sein durch Sayin, dass außerhalb der Schleife i und j erklärt nutzlos ist und nicht optimiert.

Etwas wie:

for (unsigned i = 0; i < sizeA - 2; i++) // i will only exist inside the loop 

Würde ein wenig besser sein. Ich benutze vorzeichenlosen Typ, weil es eine Gewohnheit ist, die ich bei der Verwendung einer sich wiederholenden Variable genommen habe. Ich denke, das ist eine Sache, die, wenn Sie interessiert sind und noch nicht informiert sind, Sie von this Thema lesen könnten.

Answer 3

versuchen, die folgende Schleife

for(int i=0;i<A.length;i++) 
{ 
    for(int j=0;j<A.length;j++) 
    { 
     if(A[i]==B[j]) 
     { 
      count=count+1; //It checks how many times equal elements have been found 
          //ensure to declare and initialize int count=0; 
     } 
    } 
} 
if(count>=3) 
    System.out.println("true"); 

Answer 4

nicht sicher, dass es Geschwindigkeit optimiert läuft, aber ich merke, dass es in dem Fall wiederholt werden Zahlen Sie nicht brauchen, sie über zu überprüfen und immer wieder.

Zum Beispiel sind alle drei sequentiellen Elemente im ersten Array 1. Nach der Überprüfung a[i] und sehen, es ist eine Diskrepanz können Sie direkt zu a[i + 3] ohne Vergleich a[i + 1] oder a[i + 2] (sie sind auch ein Mismatch) zu überspringen.

Die Verwaltung dieser Bedingung, insbesondere wenn es sich um eine kurze Sequenz von Wiederholungen handelt, kann die Laufzeit möglicherweise nicht verbessern. Du musst messen.

Answer 5

Mit Codeänderungen, die die order of complexity nicht beeinflussen, müssen alle möglichen Verbesserungen Profiling (Tests, die die Leistung messen) zu überprüfen.

Im folgenden ist noch ein O (n * m), noch mit reduziertem Koeffizient, während es durch b[] schnellen Schritt kann, wenn a[] Werte wiederholt, die auch in b[] existieren. Dies beschleunigt die innere b[] Schleife, in der die meiste Zeit verbraucht wird.

---

Blick auf die a[] Muster für verschiedene Werte so j kann schneller vorangetrieben werden.
Beispiel:

#define x 0 
bool Pattern3(const int *a, size_t size_a, const int *b, size_t size_b) { 
    static const unsigned char deltas[2][2][2][2] = { // 
     //     What type of pattern is a[0], a[1], a[2]? 
     { { { 1, 1 }, // X Y Z 
     { 1, 1 } },  // X Y Y 
     { { 1, 2 },  // X Y X 
     { x, x } } }, // not possible 
     { { { 2, 1 }, // X X Y 
     { x, x } },  // not possible 
     { { x, x },  // not possible 
     { 2, 3 } } } }; // X X X 
    for (unsigned i = 0; i + 2 < size_a; i++) { 
    const unsigned char *delta23 = deltas[a[0] == a[1]][a[0] == a[2]][a[1] == a[2]]; 
    for (unsigned j = 0; j + 2 < size_b;) { 
     if (a[0] != b[j]) { 
     j++; 
     } else if (a[0 + 1] != b[j + 1]) { 
     j += delta23[0]; 
     } else if (a[0 + 2] != b[j + 2]) { 
     j += delta23[1]; 
     } else { 
     return true; 
     } 
    } 
    a++; 
    } 
    return false; 
} 

---

Weitere kleinere Änderungen, die helfen können.

In den obigen, tauschen a,b, wenn size_a > size_b.

Verwenden Sie const, da weniger Compiler darauf optimiert werden können.

// int consecutiveInts(int *a, int sizeA, int *b, int sizeB){ 
int consecutiveInts(const int *a, int sizeA, const int *b, int sizeB){ 

Iterate von 2.Stellen Sie die Indizierung entsprechend ein.