私は文字列のHashSetと文字列の配列を持っています。私は配列内の要素のどれかがHashSetに存在するかどうか調べたい。私は以下のコードを動作させていますが、速くできると感じています。文字列配列内の任意の要素のHashSetを検索する
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;
}
ありがとうございます。
O（n）この場合（配列が使用されています）、これは高速にはできません。
あなただけのコードをきれいにしたい場合：
return !Collections.disjoint(group, Arrays.asList(elements));
これはやや妥当と思われます。 HashSetにはO（1）（通常）があります。インデックスを検索するために渡した文字列を単にハッシュしなければならず、そこには何かが存在していないか、存在しないからです。
アレイ内の各要素を確認する必要がある場合は、それを実行するための迅速な方法はありません（もちろん順番に）。
もっと速くしたい場合は、i ++の代わりに++ iを使います。私はコンパイラがあなたのためにそれを最適化するかどうかは分かりません。 –
私はそれがまったく違いを生むのではないかと疑います。さらに、この種のマイクロ最適化は、異なるJava実装に移行すると容易に反最適化に変わる可能性があります。 –
コンパイラによって最適化されます。 ++ iとi ++の間に違いがない理由を説明しているSOの答えがたくさんあります:) –
を...私はそれがより速く行うことができると感じています。
私はより速い方法があるとは思わない。あなたのコードは平均でO(N)です。ここで、Nは配列内の文字列の数です。私はあなたがそれを改善できるとは思わない。
他の人からも言われているように、アルゴリズムの中で最も遅い部分は、配列のすべての要素を繰り返し処理しています。唯一の方法は、配列の内容に関する情報を事前に知っていて、配列がソートされていて、既知の位置や何かに重複があった場合など、特定の要素をスキップできるようにすることです。入力が本質的にランダムであれば、あなたができることはあまりありません。
実際、彼らはそれを言っておらず、それは真実ではありません。最も遅い部分は 'contains（str）'コールです。 'str.hashCode（）'を呼び出し、 'str'と潜在的に同じハッシュチェーン内の他の文字列と比較しなければなりません。 –
はい、あなたは正しいです。私が意味することは、配列の内容を事前に知らなくても、配列を反復するためのO（n）を改善できないということでした。明確にするのを助けてくれてありがとう。 –
セットがソートされたセットであり、配列がソートされていることが分かっている場合は、最初から最後までinterval setを取得して、O（array | * access-time（set） ）、特にO（| array |）のネガティブな結果よりも優れていますが、ハッシュしている場合はできません。
O（1）はより高速です... –
この場合、要素はO（1）にできない配列です。 –
@Andrew White：非ネイティブスピーカーに疑念の恩恵を与える：おそらく、「*検索はO（n）でなければならず、それ以上の時間では実行できません。 （**編集：**卢声遠Shengyuan Luのコメントはこれを確認するようだ）私は-1が必要ではないと思う。 –