Was kann ich tun, um diesen Code zu beschleunigen (String Similarity)?

Question

Dies ist ein in C++ geschriebener Code, der Standardbibliotheken verwendet, um die String-Ähnlichkeit eines Strings S mit jedem seiner Suffixe zu finden.

Obwohl es die richtige Ausgabe gibt, braucht es viel Zeit für große Strings. Hier ist der Code:

#include <iostream> 
#include <string> 
using namespace std; 

int sim(string a, string b){ 
    int count=0; 
    int sa=a.size(); 
    int sb=b.size(); 
    int iter; 
    if(sa>sb) iter=sb; 
    else iter=sa; 
    for(int i=0; i<iter; i++){ 
     if (a[i]!=b[i]) break; 
     else count++; 
    } 
    return count; 
} 

int strsim(string a){ 
    int sum=0; 
    int s=a.size(); 
    for(int i=0; i<s; i++){ 
     sum=sum+sim(a,a.substr(i)); 
    } 
    return sum; 
} 

int main(){ 
    int n; 
    cin >> n; 
    string a[n]; 
    for(int i=0; i<n; i++){ 
     cin >> a[i]; 
    } 
    for(int i=0; i<n; i++){ 
     cout << strsim(a[i]) << '\n'; 
    } 
} 

Constraints: Die Länge der einzelnen Strings höchstens 100000 und enthält nur Kleinbuchstaben und die Anzahl der Testfälle, ‚n‘ darf nicht länger als 10

Probe I/O :

Input:

1 ababaa 

Output:

11 

d.h, 6 + 0 + 3 + 0 + 1 + 1 = 11

Answer 1

berechnet Ihre aktuelle Code für einen einzelnen String für Länge L, in O(L^3) (substr nimmt linear Laufzeit). Ganz zu schweigen von hohen konstanten Kosten für die obige Komplexität aufgrund ineffizienter Weitergabe von Strings.

Ihr Algorithmus kann einfach auf die längsten gemeinsamen Präfixe eines Strings mit allen Suffixen reduziert werden. Dies kann einfach mit Suffix Aray durchgeführt werden. Das Konzept kann nicht als Antwort erklärt werden, daher werde ich Sie sehr empfehlen read this.

A suboptimal und einfach zu Code Suffixarray Lösung wird O(Llg^2(L)) (L = String-Länge) Bauzeit und O(1) Zeit längsten gemeinsamen Präfix von 2 Endungen abzufragen Range Minimum Query verwenden. Beachten Sie, dass die gesamte Zeichenfolge selbst ein eigenes Suffix ist. In Ihrem Fall müssen Sie für jede Zeichenfolge L Abfragen erstellen. Die gesamte Komplexität für eine Zeichenfolge ist also O(Llg^2(L)) + O(L).

Wenn Sie weiter verbessern möchten, können Sie die Bauzeit zu O(Llg(L)) reduzieren, indem Radixsort, oder zu O(L) (Read)

Answer 2

Die größt Kosten Sie hier haben, ist, dass Sie die Saiten von Wert sind vorbei - Das bedeutet, dass jeder Aufruf von "sim" zwei brandneue Strings erstellt und die Daten an sie kopiert. Sie sollten dies beseitigen und durch Pass-by-Reference ersetzen.

#include <iostream> 
#include <string> 
#include <vector> 
using namespace std; 

size_t compareSubstring(const std::string& str, size_t offset) 
{ 
    size_t count = 0; 
    std::string::const_iterator lhsIt = str.begin(); 
    std::string::const_iterator rhsIt = str.begin() + offset; 
    for (; rhsIt != str.end() ; ++lhsIt, ++rhsIt) { 
     if (*lhsIt != *rhsIt) 
      break; 
     ++count; 
    } 
    return count; 
} 

int compareString(const string& str) 
{ 
    size_t count = 0; 
    const size_t length = str.size(); 
    for(size_t i = 0; i < length; ++i) { 
     count += compareSubstring(str, i); 
    } 
    return count; 
} 

int main() 
{ 
    size_t numStrings = 0; 
    std::cin >> numStrings; 

    std::vector<std::string> strings; 
    strings.resize(numStrings); 

    for(size_t i = 0; i < numStrings; ++i) { 
     std::cin >> strings[i]; 
    } 

    for(size_t i = 0; i < numStrings; ++i) { 
     std::cout << compareString(strings[i]) << std::endl; 
    } 
} 

Answer 3

Ein Zusatz von einer weiteren Zeile zu Ihrer strsim() Funktion einig zusätzlichen Funktions Anrufe an Ihrer sim() Funktion reduzieren. Wie wir wissen, dass die Kosten für einen Funktionsaufruf (extra Speicher und Verarbeitung für „Prolog“ verbraucht und „Epilog“ -Mechanismus) recht beträchtlich ist, wenn wir über die Leistung sprechen.

Also Sim-Funktion nur aufrufen, wenn das erste Zeichen der beiden Strings in Ihrem Fall "a" und "astring" gleich sind.Hier

 int strsim(string a){ 
    int sum=0; 
    int s=a.size(); 
    for(int i=0; i<s; i++){ 

    if(a[i] == a[0]) //add this extra line 
    sum=sum+sim(a,a.substr(i)); 

    } 
    return sum; 
    } 

Answer 4

ist so effizient, wie man es machen kann (ohne in FFT Territorium zu gehen):

sum_i = 0^j sum_j = 0^s f_i, j

int strsim(const string &a){ 
    int s=a.size(); 
    int sum=0; 
    for(int i=0; i<s; i++){ 
     for (int j=i;j<s;++j){ 
      if (a[j-i]!=a[i]) break; 
      sum ++; 
     } 
    } 
    return sum; 
} 

Ich weiß, Es scheint anders als Ihr Code, aber (es sei denn, ich habe einen Fehler) sollte es das gleiche zurückgeben.

Probieren Sie es aus und lassen Sie es mich wissen!

Answer 5

Zuerst sollten Sie prüfen, ob es keinen besseren Algorithmus gibt. Dann, abhängig davon, wie viel Sie bereit sind zu investieren und die Portabilität verlieren, möchten Sie vielleicht Ihren Code manuell vektorisieren, wenn der Compiler es nicht geschafft hat. Mit gcc intrinsics (siehe zB This tutorial) konnte ich eine x6-Beschleunigung auf einen ähnlichen Code bekommen.