Count das Verhältnis von nicht passenden Buchstaben

Question

eine Referenzfolge X angegeben und mainstring Y, den Prozentsatz X zählen, die leider nicht in der Y. auftreten Bedeutung: zB X = ABCD und Y = ABCDABRR dann haben wir den Prozentsatz 2/8 = 0,25, weil die 2RRs nicht mit ABCD = X und einem weiteren Beispiel, X = ABCD, Y = ABCDABRD, dann 1/8 ausgerichtet wurden.

public static void main(String[] args) { 
String mainS = "ABCDEABCDERRCRR"; 
String ref = "ABCDE"; 
double fails = 0; //count the fails. 
double len = mainS.length(); //length of main String. 
for(int i = 0; i < len; i++){ 
    String charAti = mainS.substring(i, i+1); 
    if(ref.contains(charAti)){ 
     //PASS 
    } else{ 
    ++fails; 
    } 
} 
double ratio = fails/len; 
System.out.println("Failure ratio is: " + ratio); 

}

Dies funktioniert, glaube ich O(N), aber kann ich schneller?

Answer 1

Für die Argumente, die Sie zur Verfügung stellen, in denen ref kurz ist, ist dies ein vollkommen vernünftiger Ansatz. Sie rufen jedoch contains() mehrmals auf. Die Java-Dokumentation spezifiziert nicht die Implementierung oder die Komplexität dieser Funktionen, aber es ist im allgemeinen Fall erforderlich zu sehen, ob eine Zeichenfolge eine andere enthält, so dass die Kosten für jeden Aufruf von contains() wahrscheinlich zumindest linear anwachsen mit der Länge der gesuchten Zeichenfolge. Ihre Komplexität wird wahrscheinlich genauer als O (mn) beschrieben, wobei m und n die Längen der beiden beteiligten Strings sind.

Sie hätten eine geringere theoretische Komplexität, wenn Sie die ref-Zeichenfolge zum Auffüllen eines HashSet-Zeichens verwenden und jedes Zeichen in mainS testen, um festzustellen, ob es im HashSet enthalten ist, da jeder dieser Tests nur O (1) kostet von der Größe des HashSet, die die Länge der ref.