42

さまざまなモジュールのデータを含む一連の CSV ファイルを単純にループするメソッドを実装しました。これにより、「moduleName」が hashSet に追加されます。(以下にコードを示します)

ArrayList の代わりに、重複が挿入されないことを保証する hashSet を使用しました。ArrayList は、contain() メソッドを使用し、リストを繰り返し処理して、既に存在するかどうかを確認する必要があります。

ハッシュ セットを使用すると、配列リストよりも優れたパフォーマンスが得られると思います。私はそれを述べて正しいですか？

また、誰かが私に説明できますか：

  1. 使用されている場合、各データ構造のパフォーマンスをどのように処理しますか?

  2. big-O 表記を使用した場合の複雑さは?

    HashSet<String> modulesUploaded = new HashSet<String>();

for (File f: marksheetFiles){
    try {
        csvFileReader = new CSVFileReader(f);
        csvReader = csvFileReader.readFile();
        csvReader.readHeaders();

        while(csvReader.readRecord()){
            String moduleName = csvReader.get("Module");

            if (!moduleName.isEmpty()){
                modulesUploaded.add(moduleName);
            }
        }

    } catch (IOException e) {
        e.printStackTrace();
    }

    csvReader.close();
}
return modulesUploaded;

    }

4

4 に答える 4

26

それらは完全に異なるクラスなので、問題は次のとおりです。どのような動作が必要ですか。

HashSet重複がないことを確認し、O（1）contains()メソッドを提供しますが、順序は保持しません。
ArrayList重複がないことを保証するわけではありません。O contains()（n）ですが、エントリの順序を制御できます。

于 2012-04-17T18:07:42.420 に答える
22

ハッシュ セットを使用すると、配列リストよりも優れたパフォーマンスが得られると思います。私はそれを述べて正しいですか？

多くの (それが何を意味するにせよ) エントリで、はい。ただし、データ サイズが小さい場合は、生の線形検索の方がハッシュよりも高速になる可能性があります。損益分岐点が正確にどこにあるかは、測定するだけです。私の直感では、要素が 10 個未満の場合、線形ルックアップの方がおそらく高速です。100 個を超える要素のハッシュはおそらく高速ですが、それは私の感覚です...

要素の hashCode 実装が正常であれば、HashSet からのルックアップは一定時間 O(1) です。リストからの線形ルックアップは線形時間、O(n) です。

于 2012-04-17T18:10:33.137 に答える
5

これは、データ構造の使用法に依存します。

にデータを保存してHashSetいます。あなたのケースでは、ストレージのHashSetほうが優れArrayListています（重複したエントリが必要ないため）。しかし、保管するだけが通常の意図ではありません。

保存されたデータをどのように読み取り、処理するかによって異なります。シーケンシャル アクセスまたはランダム インデックス ベースのアクセスが必要なArrayList場合は、その方が適切です。順序が問題にならない場合は、そのHashSet方が適切です。

順序付けは重要だが、多くの変更 (追加と削除) を行いたい場合は、LinkedList の方が優れています。

特定の要素にアクセスするためのHashSet時間の複雑さは O (1) であり、使用ArrayListした場合は O (N) であり、あなた自身が指摘したようにiterate、リストを調べて要素が存在しないかどうかを確認する必要があります。

于 2016-03-05T12:55:36.290 に答える