1

我基本上是在做以下事情：

  • 将数据库表中的一整行数据作为字符串转储到 ArrayList< ArrayList< String>>.

  • 对另一个数据库表做同样的事情。

  • ArrayList< String>通过遍历它并在第二个数据库中查找第一个数据库中的所有行并执行a.contains(b.get(i)). 如果包含，true那么我做a.remove(b.get(i))

现在，如果我使用 Hashtable< Arraylist< String>> 而不是上面提到的 ArrayList 使用a.containsKey(i.getKey())where i 是 b 上的迭代器，然后使用 i.remove 删除，它会快多少？它是否足以做出改变？

另外，使用 Hashmap 会更谨慎吗？如果是为什么...

4

2 回答 2

5

我自下而上的回答：

  • Hashtable 和 HashMap 之间的区别已在 HashMap 和 Hashtable 的区别中（彻底）讨论过？. 简短的总结：HashMap 更高效，应该使用 Hashtable 代替。

  • 在哈希数据结构（contains() 和 remove() 操作）中查找数据的顺序为 O(log2) - 也就是说，它与结构中数据点数量的 2 对数成正比。如果有 4 个数据元素，则需要 X 时间；如果有 8 个元素，则需要 2X 时间，16 个元素，3X 时间等等。哈希结构的数据访问时间增长非常缓慢。
    在列表中查找数据的顺序为 O(N) - 也就是说，与列表中元素的数量成正比。1 个元素需要 Y 时间，2 个元素需要 2Y 时间，4 个元素需要 4Y 时间，依此类推。所以时间消耗随着列表的大小线性增长。

  • 所以：如果你必须从一个数据结构中随机找到大量元素，哈希数据结构是最好的选择，只要：
    - 数据有一个不错的 hashCode() 实现（ArrayList 的那个就可以）
    -数据具有相互匹配的 hashCode() 和 equals() 实现，即。如果 a.equals(b) 则 a.hashCode() == b.hashCode()。ArrayList 也是如此。

  • 另一方面，如果您正在处理有序数据，那么还有其他算法可以大大减少搜索和删除时间。如果数据库中的数据被索引，那么在获取数据时使用 ORDER BY 并使用排序数据的算法可能是值得的。

总结一下：使用 HashMap 而不是 ArrayList 用于列表 a。

我写了一个小程序来对问题进行基准测试。结果优先：程序在适用于 Windows 7、32 位、Core i5 2.40 GHz CPU 的 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 回答
1

ArrayList 的 Javadoc 注释的一小段摘录：

size、isEmpty、get、set、iterator 和 listIterator 操作在恒定时间内运行。添加操作在摊销常数时间内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都以线性时间运行（粗略地说）。与 LinkedList 实现相比，常数因子较低。

这意味着，第二个列表上的 get 操作以恒定时间 O(1) 运行，从性能的角度来看应该没问题。但是包含和删除操作（在第一个列表上）在线性时间 O(n) 中运行。像第二个列表的大小一样多次调用这些操作可能会持续很长时间，尤其是在两个列表都很大的情况下。

对第一个使用散列数据结构将导致常数时间 - O(1) - 用于调用操作包含和删除。我建议对第一个“列表”使用 HashSet。但这仅适用于所有行不相等的情况。

但是在尝试优化某些东西之前，您应该始终进行分析。首先确保您正在优化正确的位置。

于 2013-07-09T09:04:12.283 回答