定义高性能数据结构的一组基本规则 (java)

Question

我通常交替使用向量/数组列表、哈希图/树形图和其他 Java 集合，但有时存在功能性 API 要求（例如，在某些情况下我可能需要排序的数据集）。

然而，最近我发现需要将我正在运行的某些算法的 java 性能推向极限。

是否有一套高性能数据结构指南，我可以将其用作编码的基本规则？

我正在寻找一般规则，但是在这种情况下，答案是以下问题也可能非常有帮助：

1) 什么时候应该使用多维数组而不是嵌套 收藏？

2) Vector 与 ArrayList - 确实存在性能差异吗？

3) 收集 API 是否像 Google 的收集、java 技巧（例如 反射和转换），以及其他常见的 Java 开发人员习惯用法 在重负载时减慢 JVM 的速度？

4) 基元与常规对象（即 Double 与 double）速度会变慢吗 JVM 在进行大量计算时？

5) 对于处理大型问题，还有其他重要的指导方针吗？ java程序中的集合需要高性能吗？

• 注意：此时，我没有进行任何多线程处理...我意识到一旦开始并行化，可能还会应用其他约束。

Answer 1

所有性能问题都应首先通过分析（时间和内存/对象使用）来解决。不要优化那些不影响代码性能的东西。有了这个警告，有一些一般的经验规则（都应该通过分析来测试！）

1) 什么时候应该使用多维数组而不是嵌套集合？

当您不需要动态调整集合的大小并且不需要将数据提供给需要集合的任何内容时，那么多维数组（实际上是数组的数组）可能会更快。

2) Vector 与 ArrayList - 确实存在性能差异吗？

是的。 Vector中的许多方法都是同步的，这是昂贵的。如果您不使用多线程，请避免使用 Vector。即使您是这样，同步的粒度通常也是错误的，您最好自己提供线程安全性。

3) 像 Google 的集合那样的集合 API、Java 技巧（如反射和转换）以及其他常见的 Java 开发人员惯用语在 JVM 负载较重时是否会降低 JVM 的速度？

反射速度慢；垃圾收集速度很慢。您可以采取任何措施来避免这些情况，从而加快速度。

4) 在进行大量计算时，基元与常规对象（即 Double 与 double）会减慢 JVM 的速度吗？

是的。自动装箱/拆箱会很快产生大量垃圾。这一切都必须收集，这也会减慢你的程序。

5) 对于在需要高性能的 Java 程序中处理大型集合，还有其他重要的指导原则吗？

优先选择局部方法变量而不是字段访问。您可以通过搜索网络找到许多其他指南。不过，最重要的是分析。

编辑：此处提供了大量性能提示。

Answer 2

回答你的 4) 是的，Double 与 double 肯定会改变性能

当你有由基元组成的集合时，你当然可以使用由基元支持的集合，就像非常好的 Trove API。通过避免不断的基元到对象以及反之亦然（拆箱）装箱，您可以节省内存和宝贵的时间。

另外，Vector 类现在几乎已经成为过去。

Answer 3

1）如果您不需要真正动态调整大小，或者您可以将数据放入足够小的“最大大小”容器中，那么由于删除了方法，从数组的随机访问将比从集合中获得更好的性能调用开销甚至可能更多（取决于所使用的集合）。

2）在我看来，向量和哈希表几乎应该被视为已被弃用。它们是“线程安全的”，但对于大多数现实世界的场景，仅仅让数据结构本身是线程安全的是不够的；通常，您的应用程序逻辑也必须成为此同步的一部分。 ArrayList、HashMap 的性能会更好，因为它们没有同步块，而 99.9% 的情况下它们不会给你带来任何有用的东西。

3) Google 的集合 API 很棒，没有真正的性能问题。反射肯定很慢，不应该出现在内部循环中。

4）理想情况下，您希望避免在内循环中对基元进行装箱/拆箱。您可以找到专门针对原语进行调整的集合（即 Trove 集合 http://trove.starlight-systems.com /）。

5）这取决于具体用途，我不会说有任何通用准则。只需确保了解在转换集合等时您在做什么。例如，当您将列表转换为集合或类似内容时，请确保它不会克隆整个集合。

Answer 4

1. 我相信你唯一应该使用Vector的时候是当你需要它同步的时候，但是你可以在ArrayList上使用特殊的Synchronized东西，所以我想说Vector是不需要的。始终使用 ArrayList 而不是 LinkedList。它背离了常识，所以它必须是java的实现，但是ArrayList要快得多。我曾经相信 LinkedList 所以我创建了以下测试：

   导入java.util.ArrayList;
   导入 java.util.GregorianCalendar;
   导入 java.util.LinkedList;
   导入java.util.List；
   import java.util.Random;

/**
*
*/

/**
* @作者汤姆
*
*/
public class ListTest {

private ArrayList<Integer>      arrayList = new ArrayList<Integer>();
private LinkedList<Integer>     linkedList = new LinkedList<Integer>();

/**
 * 
 */
public void test(){
    LinkedList<Integer> arrayTimes = new LinkedList<Integer>();
    LinkedList<Integer> linkedTimes = new LinkedList<Integer>();

    for(int ix = 0; ix < 100; ix ++){
        arrayList.clear();
        long start = new GregorianCalendar().getTimeInMillis();
        fillList(arrayList);
        long stop = new GregorianCalendar().getTimeInMillis();
        int elapsed = (int) (stop - start);
        arrayTimes.add(elapsed);
    }

    for(int ix = 0; ix < 100; ix ++){
        linkedList.clear();
        long start = new GregorianCalendar().getTimeInMillis();
        fillList(linkedList);
        long stop = new GregorianCalendar().getTimeInMillis();
        int elapsed = (int) (stop - start);
        linkedTimes.add(elapsed);
    }

    double arrayAvg = avg(arrayTimes);
    double linkedAvg = avg(linkedTimes);

    System.err.println("Adding 100,000 entries 100 times to linked list.");
    System.err.println("ArrayList elapsed time (ms.):" + arrayAvg);
    System.err.println("LinkedList elapsed time (ms.):" + linkedAvg);

    arrayTimes.clear();
    linkedTimes.clear();

    long start = new GregorianCalendar().getTimeInMillis();
    insertMiddle(arrayList);
    long stop = new GregorianCalendar().getTimeInMillis();
    int elapsed = (int) (stop - start);

    System.err.println();
    System.err.println("Inserting 1,000 entries to the middle of the list.");
    System.err.println("ArrayList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    insertMiddle(linkedList);
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);
    System.err.println("LinkedList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            arrayList.get(jx);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);

    System.err.println();
    System.err.println("Sequentially reading the list 100 times");
    System.err.println("ArrayList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            linkedList.get(jx);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);
    System.err.println("LinkedList elapsed time (ms.):" + elapsed);

    Random rnd = new Random();
    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            int index = rnd.nextInt(100000);
            arrayList.get(index);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);

    System.err.println();
    System.err.println("Randomly reading the list 100 times");
    System.err.println("ArrayList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            int index = rnd.nextInt(100000);
            linkedList.get(index);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);
    System.err.println("LinkedList elapsed time (ms.):" + elapsed);
}

/**
 * @param values
 */
protected double avg(List<Integer> values){
    double sum = 0;
    for(int ix:values){
        sum += ix;
    }

    double result = sum / values.size();
    return result;
}

/**
 * @param list
 */
protected void fillList(List<Integer> list){
    for(int ix = 0; ix < 100000; ix++){
        list.add(ix);
    }
}

/**
 * @param list
 */
protected void insertMiddle(List<Integer> list){
    for(int ix = 0; ix < 1000; ix++){
        list.add(50000, ix);
    }
}

/**
 * @param args
 */
public static void main(String[] args) {
    ListTest listTest = new ListTest();
    listTest.test();
}

}

它产生了以下结果：

Adding 100,000 entries 100 times to linked list.
ArrayList elapsed time (ms.):2.78
LinkedList elapsed time (ms.):12.24

Inserting 1,000 entries to the middle of the list.
ArrayList elapsed time (ms.):35
LinkedList elapsed time (ms.):154

Sequentially reading the list 100 times
ArrayList elapsed time (ms.):94
LinkedList elapsed time (ms.):748271

Randomly reading the list 100 times
ArrayList elapsed time (ms.):404
LinkedList elapsed time (ms.):1158273

请有人验证我的代码以确保我没有做一些愚蠢的事情，但它表明 ArrayList 在所有方面都比 LinkedList 快得多。

1. 反射肯定很慢。

2. 基元的计算速度要快得多。请小心自动装箱，因为它会影响性能。这很好，只要确保您了解成本

Answer 5

1）当你知道最大尺寸时，使用数组。

2) Vector 有同步方法，因此比 ArrayList 慢。有一个区别。最近有使用 Collections.synchronizedList 而不是向量的趋势。

3）有一些“快速”集合的实现，例如 http://labs.carrotsearch.com/ hppc.html 或 Trove，其他什么是最高效的 Java Collections 库？

4) 如果可以，请使用原语。包装器会带来额外的开销。

5）想想你必须做什么，最常执行什么操作，例如向集合中添加元素比向数组列表中添加元素要慢，遍历数组列表比在集合中迭代要快。然而，从 arraylist 中删除元素比在 set 中删除元素要慢。当可以使用数组时 - 它们将比任何其他集合更快。当您必须使用集合，但您大约知道将插入多少元素时，请使用具有初始大小的构造函数。

Answer 6

恕我直言，首要的规则是为您的用例选择正确的结构。

使用映射来实现字典可能会提高性能（时间），但会占用大量内存（空间），请使用

哈希搜索（使用 HashMap）很好，但如果你有一个有限数字范围的键，那么数组会做得更好。

我建议的唯一经验法则是，当您必须处理 GB 级数据和/或微秒级响应要求时，设计自己的数据结构。

Answer 7

您是否需要直接访问数据？如果需要，您现在是否知道对象的确切位置？如果你一直循环遍历集合来找出你需要的对象在哪里，这需要一些时间（因此直接访问将是有利的）

而且自动装箱确实需要时间，因为你无法创建对象的集合原始类型，它们将始终被自动装箱到其亲属中。

Answer 8

另一个小技巧：

如果您使用非常大的集合，并且您提前知道（或可以估计）它们的大小，则应该使用允许您指定初始容量的构造函数。这避免了多个数组分配。