1

私は基本的に次のことをやっています：

  • DB テーブルのデータ行全体を文字列として ArrayList< ArrayList< String>>.

  • 別の DB テーブルに対して同じことを行います。

  • 最初の DB のすべての行ArrayList< String>を 2 番目の DB で反復処理してa.contains(b.get(i)). が含まれている場合、true私はそうしますa.remove(b.get(i))

ここで、上記の ArrayList の代わりに Hashtable< Arraylist< String>> を使用しa.containsKey(i.getKey())、 i が b のイテレータであり、 i.remove を使用して削除した場合、どのくらい高速になりますか? 変更を加えるのに十分な増加でしょうか？

また、ハッシュマップを使用する方が賢明でしょうか? だとしたらなぜ...

4

2 に答える 2

5

私のボトムアップの答え：

  • Hashtable と HashMap の違いは、HashMap と Hashtable の違いで (徹底的に) 説明されていますか? . 簡単な要約: HashMap はより効率的であり、Hashtable の代わりに使用する必要があります。

  • ハッシュ データ構造 (contains() および remove() 操作) 内のデータの検索は、O(log2) の順序で行われます。つまり、構造内のデータ ポイント数の 2 対数に比例します。4 つのデータ要素がある場合、X 時間かかります。8 要素の場合は 2 倍の時間、16 要素の場合は 3 倍の時間がかかります。ハッシュ構造のデータ アクセス時間は、非常にゆっくりと増加します。
    リスト内のデータの検索は、O(N) の順序で行われます。つまり、リスト内の要素の数に正比例します。1 つの要素には Y 時間、2 つの要素には 2Y 時間、4 つの要素には 4Y 時間かかります。したがって、時間の消費はリストのサイズに比例して増加します。

  • したがって、データ構造から多数の要素をランダムに見つける必要がある場合は、ハッシュ データ構造が最良の選択です
    。
    データには、互いに一致する hashCode() と equals() の実装があります。a.equals(b) の場合、a.hashCode() == b.hashCode()。これは ArrayList にも当てはまります。

  • 一方、順序付けられたデータを扱っている場合は、検索を大幅に短縮して時間を大幅に削減できる他のアルゴリズムがあります。データベース内のデータがインデックス化されている場合は、データをフェッチするときに ORDER BY を使用してから、順序付けられたデータのアルゴリズムを使用する価値があります。

要約すると、リスト a には ArrayList の代わりに HashMap を使用します。

問題をベンチマークする小さなプログラムを作成しました。最初の結果: プログラムは、Core i5 2.40 GHz CPU 上の Windows 7、32 ビット用の Sun JVM 1.6.0_41 で実行されました。プリントアウト：

For 1000 words: List: 1 ms, Map: 2 ms
For 5000 words: List: 15 ms, Map: 12 ms
For 10000 words: List: 57 ms, Map: 12 ms
For 20000 words: List: 217 ms, Map: 37 ms
For 30000 words: List: 485 ms, Map: 45 ms
For 50000 words: List: 1365 ms, Map: 61 ms

パフォーマンス特性は、このような簡単なテストでよくわかります。より多くのデータを使用してマップ バージョンを実行したところ、次の結果が得られました。

For 100000 words: List: - ms, Map: 166 ms
For 500000 words: List: - ms, Map: 1130 ms
For 1000000 words: List: - ms, Map: 3540 ms

最後に、ベンチマーク コード:

public void benchmarkListVersusMap() {
    for (int count : new int[]{1000, 5000, 10000, 20000, 30000, 50000}) {
        // Generate random sample data
        List<List<String>> words = generateData(count, 10, count);

        // Create ArrayList
        List<List<String>> list = new ArrayList<List<String>>();
        list.addAll(words);

        // Create HashMap
        Map<List<String>, Boolean> map = new HashMap<List<String>, Boolean>();
        for (List<String> row : words) {
            map.put(row, true);
        }

        // Measure:
        long timer = System.currentTimeMillis();
        for (List<String> row: words) {
            if (list.contains(row)) {
                list.remove(row);
            }
        }
        long listTime = System.currentTimeMillis() - timer;
        timer = System.currentTimeMillis();
        for (List<String> row : words) {
            if (map.containsKey(row)) {
                map.remove(row);
            }
        }
        long mapTime = System.currentTimeMillis() - timer;
        System.out.printf("For %s words: List: %s ms, Map: %s ms\n", count, listTime, mapTime);
    }
}

private List<List<String>> generateData(int rows, int cols, int noOfDifferentWords) {
    List<List<String>> list = new ArrayList<List<String>>(rows);
    List<String> dictionary = generateRandomWords(noOfDifferentWords);
    Random rnd = new Random();
    for (int row = 0; row < rows; row++) {
        List<String> l2 = new ArrayList<String>(cols);
        for (int col = 0; col < cols; col++) {
            l2.add(dictionary.get(rnd.nextInt(noOfDifferentWords)));
        }
        list.add(l2);
    }
    return list;
}

private static final String CHARS = "abcdefghijklmnopqrstuvwxyz0123456789";
private List<String> generateRandomWords(int count) {
    Random rnd = new Random();
    List<String> list = new ArrayList<String>(count);
    while (list.size() < count) {
        StringBuilder sb = new StringBuilder(20);
        for (int i = 0; i < 10; i++) {
            sb.append(CHARS.charAt(rnd.nextInt(CHARS.length())));
        }
        list.add(sb.toString());
    }
    return list;
}
于 2013-07-09T11:54:31.867 に答える