Durchsuchen eines HashSets nach einem beliebigen Element in einem String-Array

Question

Ich habe ein HashSet von Zeichenfolgen und ein Array von Zeichenfolgen. Ich möchte herausfinden, ob eines der Elemente im Array im HashSet vorhanden ist. Ich habe den folgenden Code, die Arbeit, aber ich fühle, dass es schneller getan werden könnte.

public static boolean check(HashSet<String> group, String elements[]){
    for(int i = 0; i < elements.length; i++){
        if(group.contains(elements[i]))
            return true;
    }
    return false;
}

Merci.

Answer 1

Es ist O(n) in diesem Fall (Array wird verwendet), kann es nicht schneller sein.

Wenn Sie den Code nur sauberer machen wollen:

 return !Collections.disjoint(group, Arrays.asList(elements));

Answer 2

Das erscheint einigermaßen vernünftig. HashSet hat eine O(1) (normalerweise) contains() da es einfach nur die Zeichenkette, die Sie ihm geben, hacken muss, um einen Index zu finden, und entweder ist etwas da oder nicht.

Wenn Sie jedes Element in Ihrem Array überprüfen müssen, gibt es einfach keinen schnelleren Weg, dies zu tun (natürlich sequentiell).

Answer 3

... aber ich habe das Gefühl, dass es schneller gehen könnte.

Ich glaube nicht, dass es einen schnelleren Weg gibt. Ihr Code ist O(N) im Durchschnitt, wobei N ist die Anzahl der Zeichenketten im Array. Ich glaube nicht, dass man das noch verbessern kann.

Answer 4

Wie bereits von anderen gesagt, ist der langsamste Teil des Algorithmus die Iteration über jedes Element des Arrays. Der einzige Weg, es schneller zu machen, wäre, wenn man vorher einige Informationen über den Inhalt des Arrays wüsste, die es erlauben würden, bestimmte Elemente zu überspringen, z.B. wenn das Array sortiert wäre und Duplikate an bekannten Positionen hätte oder so. Wenn die Eingabe im Wesentlichen zufällig ist, dann gibt es nicht viel, was man tun kann.

Answer 5

Wenn Sie wissen, dass die Menge eine sortierte Menge ist und dass das Array sortiert ist, können Sie die Intervallsatz vom Anfang bis zum Ende, um möglicherweise besser als O(|array| * Zugriffszeit(Menge)) zu sein, und was insbesondere einige besser als O(|array|) negative Ergebnisse ermöglicht, aber wenn man hasht, kann man das nicht.