10

我正在编写一个使用 Dijkstra 算法在图中找到最小路径的应用程序。图中节点和边的权重是float数字，因此该算法对浮点数进行了许多算术运算。int如果我将所有重量都转换为s ，我能提高跑步时间吗？Java中的int算术运算比浮点运算快吗？

我试图编写一个简单的基准来检查它，但我对得到的结果并不满意。可能编译器已经优化了程序的某些部分，所以结果对我来说看起来不太好。

编辑：

我要解决的问题是在信息检索领域。应用程序应显示作为一组关键字的查询的答案。

我的数据结构是加权有向图。给定一组叶节点，我必须找到连接这些节点的最小树并向用户显示答案。权重由部分基于 tf/idf 技术的加权函数分配。用户不知道我为节点和边分配了什么权重，他只想查看与他提出的查询相关的答案。所以不需要精确的结果，只是可以根据他们的权重列举答案。只是权重函数的原生使用（正如我提到的，它基于 tf/idf）给出了浮点权重，所以到目前为止我使用了浮点数。

我希望这为这个问题增加了一些背景。

4

7 回答 7

2

for simple operations int is faster, however with int you may have to do more work to get the same result. e.g.

as float

float f = 15 * 0.987;

as int

int i = 15 * 987 / 1000;

The extra division means the int operation can take longer.

于 2010-07-28T07:59:38.077 回答
1

在我的机器上，整数减法比双减法快约 2.5 倍。然而，整数乘法仅比双乘法快约 1.5 倍。

以下测试适用于随机数据，这可能会阻止编译器进行优化。

// test whether int subs are faster than double subs
public void compareIntAndFloatSubtraction(){

    int N = 100000;  // input array size
    int k = 100000;  // number of mathematical operations performed on each element

    // generate random data
    int[] ints = new int[N];
    double[] doubles = new double[N];
    Random r = new Random(1l);
    for (int i = 0; i < N; i++) {
        ints[i] = r.nextInt();
        doubles[i] = r.nextDouble();
    }

    // measure integer subtractions
    long before = System.currentTimeMillis();
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < k; j++) {
            ints[i] -= ints[i-1];  // referring to another element might prevent from optimization also
        }
    }
    System.out.println(String.format("time needed for int subs [ms]: %s", System.currentTimeMillis()-before));

    // measure double subtractions
    before = System.currentTimeMillis();
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < k; j++) {
            doubles[i] -= doubles[i-1];
        }
    }
    System.out.println(String.format("time needed for double subs [ms]: %s", System.currentTimeMillis()-before));

}
于 2014-06-11T09:46:18.720 回答
1

与以往一样，您应该为自己设定一些性能目标，然后分析应用程序以查看它是否符合这些目标。

很多时候你可能会发现令人惊讶的结果；所花费的时间几乎不受基本数字类型的影响，或者您的算法不是最佳的。

关于编译器优化 - 它们是性能优化的真实有效部分。

如果理论上使用类型 A 比使用类型 B 更快，但是您的编译器可以优化类型 B 以在实际场景中更快，那么这是一个有价值的证据，而不是令人失望的来源。

于 2010-07-28T08:05:58.360 回答
0

通常，您不必担心性能原因之间int的选择。float

以下是Java Puzzlers附录的摘录：

浮点运算是不精确的。不要在需要精确结果的地方使用浮点数；相反，请使用整数类型或BigDecimal. double更喜欢float.

除非您有充分的理由，否则您通常应该更喜欢double必须float使用浮点运算。如果需要确切的结果，请继续使用BigDecimal; 它会变慢，因为它不是原始的，但除非分析表明它是不可接受的，否则这通常是最好的选择。

如果您必须使用浮点运算，那么尝试通过使用来优化它int是不明智的。这可能是一个过早的优化，只会使不必要的代码复杂化。用最自然、最易读的方式写出来。不要为了轻微的性能提升而不必要地使您的代码复杂化。

如果您实际上不需要浮点运算，那么请务必使用intorlong代替。

于 2010-07-28T08:45:34.850 回答
0

我认为性能在很大程度上取决于算法和软件运行的平台。

如果您在 X86 平台上进行矩阵/数组计算，则运行时可能会对其进行优化以使用 SSE，这是一个仅限浮点/双精度的扩展指令集。

在其他平台上，运行时可能会针对 OpenCL 进行优化（我不相信现在有人这样做，但它可能会发生：）。我不知道在这样的平台上什么运行速度最快，以及在什么条件下运行。可能只是 OpenCL 针对整数工作负载进行了优化。

在这种情况下，我会得出结论，此时优化数据类型（float 或 int）是没有用的，而只是优化代码的可读性。

如果您的代码对性能至关重要，并且您确切地知道系统现在和将来将在哪个硬件上运行，您可以使用各种算法测试典型的工作负载并选择最能满足您需求的一种。

但总的来说，只需使用您可以理解的算法，保持代码可读性，从而降低错误数量。如果结果不正确，快速代码就不值那么多了:)

于 2010-07-28T09:23:32.290 回答
0

如果你只是想比较权重，你应该更喜欢 int 浮动。

于 2010-07-28T08:30:56.857 回答
-6

我不这么认为。

浮点数为 4 个字节。Java中的Int也是4字节。

为什么不使用 Date(java.util.Date) 来获取运行时间？

您可以定义一个拥有 100000 个节点的图。然后计算一下。

于 2010-07-28T08:13:10.227 回答