用数字表示算法的效率
Putting a number to the efficiency of an algorithm
我已经使用 Java 开发了一段时间，并且总是努力以最有效的方式做某事。到目前为止，我主要是在尝试压缩我拥有的代码行数。但是当开始使用 2d 渲染时，更多的是计算一段代码需要多长时间，因为它每秒被调用多次。
我的问题：
有什么方法可以衡量在 Eclipse 中计算一段特定代码需要多长时间，Java，...？
一般来说，速度与代码行数并不是最有效的性能衡量标准，因为它在很大程度上取决于您的硬件和编译器。有一种叫做 Big Oh 表示法的东西，它给出了随着输入数量的增加算法 运行 的速度的图片。
例如，如果您的算法速度为 O(n)，那么代码 运行 所花费的时间与时间呈线性关系。如果你的算法速度是 O(1)，那么你的代码到 运行 所花费的时间将是恒定的。
我发现这种衡量性能的特殊方法很有用，因为您了解到影响速度的并不是真正的代码行，而是您的代码设计会影响速度。具有更有效处理问题方法的代码比具有 1/10 行代码的效率较低方法的代码更快。
行数与程序执行速度的相关性很小。
你的程序经过编译器处理后看起来会完全不同。通常，大型编译器会执行许多优化，例如循环展开、删除未使用的变量、删除死代码等等。
因此，不要尝试使用 short 代替 int，而是使用 char[] 代替 "squeeze" 从您的程序中取出 performance/memory 的最后一位String 或您认为 "optimize" （过早优化）您的程序的任何方法，只需使用对您有意义的对象或类型来执行，这样维护起来会更容易。您的编译器、解释器、VM 应该负责其余的工作。如果没有，那么您才开始寻找瓶颈，并开始使用 hacks。
那么是什么让程序变快呢？算法效率（至少如果 algorithm/data 结构设计不当，它往往会产生最大的差异）。这就是计算机科学家研究的内容。
假设您有 2 个数据结构。一个数组，一个单向链表。
数组以块的形式存储东西，一个接一个。
+-+-+-+-+-+-+-+
|1|3|2|7|4|6|1|
+-+-+-+-+-+-+-+
要检索索引 3 处的元素，只需转到第 4 个方块并检索它即可。你知道它在哪里，因为你知道它在第一个方格之后的 3。
单向链表会将东西存储在一个节点中，该节点可能不会连续存储在内存中，但是每个节点上都会有一个标记（指针，引用）告诉您列表中的下一个项目在哪里。
+-+ +-+ +-+ +-+ +-+ +-+ +-+
|1| -> |3| -> |2| -> |7| -> |4| -> |6| -> |1|
+-+ +-+ +-+ +-+ +-+ +-+ +-+
要检索索引为 3 的元素，您必须从第一个节点开始，然后转到连接的节点，即 1，然后转到 2，最后到达 3。都是因为你不知道他们在哪里，所以你沿着一条路找到他们。
现在假设你有一个数组和一个 SLL，它们都包含相同的数据，长度为 n，哪个更快？就看你怎么用了。
假设您在列表末尾进行了很多插入操作。算法（伪代码）将是：
Array:
array[list.length] = element to add
increment length field
SLL:
currentNode = first element of SLL
while currentNode has next node:
currentNode = currentNode's next element
currentNode's next element = new Node(element to add)
increment length field
如你所见，在数组算法中，数组的大小是多少并不重要。它总是需要恒定数量的操作。假设 a[list.length] 需要 1 次操作。分配它是另一个操作，递增字段并将其写入内存是 2 个操作。每次需要4次操作。但是如果你看看 SLL 算法，它至少需要 list.length 次操作才能找到列表中的最后一个元素。换句话说，随着 SLL 大小的增加，将一个元素添加到 SLL 末尾所花费的时间线性增加 t(n) = n，而对于数组，它更像是 t(n) = 4.
我建议阅读我的数据结构教授写的 free book。甚至有 C++ 和 Java
的工作代码
首先，有些吹毛求疵。你给这个问题起标题...
Putting a number to the efficiency of an algorithm
算法没有 "efficiency" 的实际可量化度量。效率（通常认为的）是相对于理想/完美的 "something" 的衡量标准；例如假设一个 100% 高效的蒸汽机会将燃烧的煤中的所有能量转化为有用的 "work"。但是对于软件来说，没有理想的衡量标准。 （或者如果有，我们不能确定它是理想的。）因此 "efficiency" 是错误的术语。
您的实际意思是衡量 "performance" 的...
算法是一个抽象的概念，其性能无法衡量。
您真正想要的是衡量算法特定实现的性能；即一些实际代码。
那么如何量化绩效？
好吧，最终只有一种合理的方法来量化绩效。你根据经验来衡量它。 （你如何做到这一点......以及限制......是我会谈到的问题。）
但是理论方法呢？
一种常见的理论方法是分析算法以衡量计算复杂性。经典的衡量标准是 Big-O 复杂性。这是一个非常有用的衡量标准，但不幸的是 Big-O 复杂性实际上根本无法衡量性能。相反，它是一种随着问题规模扩大而表征算法行为的方法。
为了说明，请考虑将这些 B 数相加的算法：
int sum(int[] input) {
int sum = 0;
for (int i = 0; i < input.size(); i++) {
sum += input[i];
}
return i;
}
int sum(int[] input) {
int tmp = p(1000); // calculates the 1000th prime number
int sum = 0;
for (int i = 0; i < input.size(); i++) {
sum += input[i];
}
return i;
}
根据公认的数学定义，我们可以证明 sum 的两个版本都具有 O(N) 的复杂度。然而很明显，第一个会比第二个更快......因为第二个也会进行大量（且毫无意义的）计算。
In short: Big-O Complexity is NOT a measure of Performance.
绩效的理论衡量标准如何？
嗯，据我所知，none 确实有效。问题在于实际性能（如完成所需的时间）取决于将代码编译为可执行文件时的各种复杂事物以及实际执行平台（硬件）的行为方式。进行可靠地预测实际性能的理论分析太复杂了。
那么您如何衡量绩效？
天真的答案是像这样进行基准测试：
- 进行时钟测量
- 运行代码
- 进行第二次时钟测量
- 从第二个测量值中减去第一个测量值...这就是您的答案。
但它不起作用。或者更准确地说，您得到的答案可能与您在现实世界环境中使用代码时表现出的性能截然不同.
为什么？
机器上可能正在发生或已经发生的其他事情影响了代码的执行时间。另一个程序可能是 运行ning。您可能将文件 pre-loaded 放入文件系统缓存中。您可能会受到 CPU 时钟缩放...或突发网络流量的影响。
编译器和编译器标志通常会对一段代码的速度产生很大影响 运行s.
输入的选择往往会产生很大的不同。
如果编译器很聪明，它可能会推断出您的部分或全部基准代码什么都不做"useful"（在上下文中）...并完全优化它。
对于 Java 和 C# 等语言，还有其他重要问题：
这些语言的实现通常在启动期间做很多工作来加载和link代码。
这些语言的实现通常是 JIT 编译的。这意味着语言 运行time 系统会在 运行time 将代码（例如字节码）最终翻译为本地代码。 JIT 编译后代码的性能特征发生巨大变化，编译所花费的时间可能很长......并且可能会扭曲您的时间测量。
这些语言的实现通常依赖垃圾收集堆来进行内存管理。一个堆的性能往往是参差不齐的，尤其是在启动时。
这些东西（可能还有其他东西）会导致我们称之为（在 Java 中）JVM 预热开销；特别是 JIT 编译。如果您在方法中不考虑这些开销，那么您的结果很可能会失真。
那么衡量 Java 代码性能的正确方法是什么？
比较复杂，但总的原则是运行基准代码在同一个JVM实例中多次执行，measurin每次迭代。应丢弃前几个测量值（在 JVM 预热期间），其余测量值应取平均值。
如今，推荐的 Java 基准测试方法是使用信誉良好的基准测试框架。两个主要候选人是 Caliper and Oracle's jmh tool.
您提到的性能测量的局限性是什么？
好吧，我在上面已经提到了它们。
性能测量可能会因执行平台上的各种环境因素而失真。
性能可能取决于输入...这可能无法通过简单的测量来揭示。
性能（例如 C/C++ 代码）可能取决于编译器和编译器开关。
性能可能取决于硬件；例如处理器速度、内核数量、内存架构等。
这些因素可能导致难以对特定代码段的性能做出一般陈述，也难以进行一般比较在同一代码的不同版本之间。通常，我们只能做出有限的陈述，例如 "on system X, with compiler Y and input set Z the performance measures are P, Q, R".
我已经使用 Java 开发了一段时间，并且总是努力以最有效的方式做某事。到目前为止，我主要是在尝试压缩我拥有的代码行数。但是当开始使用 2d 渲染时，更多的是计算一段代码需要多长时间，因为它每秒被调用多次。
我的问题：
有什么方法可以衡量在 Eclipse 中计算一段特定代码需要多长时间，Java，...？
一般来说，速度与代码行数并不是最有效的性能衡量标准，因为它在很大程度上取决于您的硬件和编译器。有一种叫做 Big Oh 表示法的东西，它给出了随着输入数量的增加算法 运行 的速度的图片。
例如，如果您的算法速度为 O(n)，那么代码 运行 所花费的时间与时间呈线性关系。如果你的算法速度是 O(1)，那么你的代码到 运行 所花费的时间将是恒定的。
我发现这种衡量性能的特殊方法很有用，因为您了解到影响速度的并不是真正的代码行，而是您的代码设计会影响速度。具有更有效处理问题方法的代码比具有 1/10 行代码的效率较低方法的代码更快。
行数与程序执行速度的相关性很小。
你的程序经过编译器处理后看起来会完全不同。通常，大型编译器会执行许多优化，例如循环展开、删除未使用的变量、删除死代码等等。
因此，不要尝试使用 short 代替 int，而是使用 char[] 代替 "squeeze" 从您的程序中取出 performance/memory 的最后一位String 或您认为 "optimize" （过早优化）您的程序的任何方法，只需使用对您有意义的对象或类型来执行，这样维护起来会更容易。您的编译器、解释器、VM 应该负责其余的工作。如果没有，那么您才开始寻找瓶颈，并开始使用 hacks。
那么是什么让程序变快呢？算法效率（至少如果 algorithm/data 结构设计不当，它往往会产生最大的差异）。这就是计算机科学家研究的内容。
假设您有 2 个数据结构。一个数组，一个单向链表。
数组以块的形式存储东西，一个接一个。
+-+-+-+-+-+-+-+
|1|3|2|7|4|6|1|
+-+-+-+-+-+-+-+
要检索索引 3 处的元素，只需转到第 4 个方块并检索它即可。你知道它在哪里，因为你知道它在第一个方格之后的 3。
单向链表会将东西存储在一个节点中，该节点可能不会连续存储在内存中，但是每个节点上都会有一个标记（指针，引用）告诉您列表中的下一个项目在哪里。
+-+ +-+ +-+ +-+ +-+ +-+ +-+
|1| -> |3| -> |2| -> |7| -> |4| -> |6| -> |1|
+-+ +-+ +-+ +-+ +-+ +-+ +-+
要检索索引为 3 的元素，您必须从第一个节点开始，然后转到连接的节点，即 1，然后转到 2，最后到达 3。都是因为你不知道他们在哪里，所以你沿着一条路找到他们。
现在假设你有一个数组和一个 SLL，它们都包含相同的数据，长度为 n，哪个更快？就看你怎么用了。
假设您在列表末尾进行了很多插入操作。算法（伪代码）将是：
Array:
array[list.length] = element to add
increment length field
SLL:
currentNode = first element of SLL
while currentNode has next node:
currentNode = currentNode's next element
currentNode's next element = new Node(element to add)
increment length field
如你所见，在数组算法中，数组的大小是多少并不重要。它总是需要恒定数量的操作。假设 a[list.length] 需要 1 次操作。分配它是另一个操作，递增字段并将其写入内存是 2 个操作。每次需要4次操作。但是如果你看看 SLL 算法，它至少需要 list.length 次操作才能找到列表中的最后一个元素。换句话说，随着 SLL 大小的增加，将一个元素添加到 SLL 末尾所花费的时间线性增加 t(n) = n，而对于数组，它更像是 t(n) = 4.
我建议阅读我的数据结构教授写的 free book。甚至有 C++ 和 Java
的工作代码首先，有些吹毛求疵。你给这个问题起标题...
Putting a number to the efficiency of an algorithm
算法没有 "efficiency" 的实际可量化度量。效率（通常认为的）是相对于理想/完美的 "something" 的衡量标准；例如假设一个 100% 高效的蒸汽机会将燃烧的煤中的所有能量转化为有用的 "work"。但是对于软件来说，没有理想的衡量标准。 （或者如果有，我们不能确定它是理想的。）因此 "efficiency" 是错误的术语。
您的实际意思是衡量 "performance" 的...
算法是一个抽象的概念，其性能无法衡量。
您真正想要的是衡量算法特定实现的性能；即一些实际代码。
那么如何量化绩效？
好吧，最终只有一种合理的方法来量化绩效。你根据经验来衡量它。 （你如何做到这一点......以及限制......是我会谈到的问题。）
但是理论方法呢？
一种常见的理论方法是分析算法以衡量计算复杂性。经典的衡量标准是 Big-O 复杂性。这是一个非常有用的衡量标准，但不幸的是 Big-O 复杂性实际上根本无法衡量性能。相反，它是一种随着问题规模扩大而表征算法行为的方法。
为了说明，请考虑将这些 B 数相加的算法：
int sum(int[] input) {
int sum = 0;
for (int i = 0; i < input.size(); i++) {
sum += input[i];
}
return i;
}
int sum(int[] input) {
int tmp = p(1000); // calculates the 1000th prime number
int sum = 0;
for (int i = 0; i < input.size(); i++) {
sum += input[i];
}
return i;
}
根据公认的数学定义，我们可以证明 sum 的两个版本都具有 O(N) 的复杂度。然而很明显，第一个会比第二个更快......因为第二个也会进行大量（且毫无意义的）计算。
In short: Big-O Complexity is NOT a measure of Performance.
绩效的理论衡量标准如何？
嗯，据我所知，none 确实有效。问题在于实际性能（如完成所需的时间）取决于将代码编译为可执行文件时的各种复杂事物以及实际执行平台（硬件）的行为方式。进行可靠地预测实际性能的理论分析太复杂了。
那么您如何衡量绩效？
天真的答案是像这样进行基准测试：
- 进行时钟测量
- 运行代码
- 进行第二次时钟测量
- 从第二个测量值中减去第一个测量值...这就是您的答案。
但它不起作用。或者更准确地说，您得到的答案可能与您在现实世界环境中使用代码时表现出的性能截然不同.
为什么？
机器上可能正在发生或已经发生的其他事情影响了代码的执行时间。另一个程序可能是 运行ning。您可能将文件 pre-loaded 放入文件系统缓存中。您可能会受到 CPU 时钟缩放...或突发网络流量的影响。
编译器和编译器标志通常会对一段代码的速度产生很大影响 运行s.
输入的选择往往会产生很大的不同。
如果编译器很聪明，它可能会推断出您的部分或全部基准代码什么都不做"useful"（在上下文中）...并完全优化它。
对于 Java 和 C# 等语言，还有其他重要问题：
这些语言的实现通常在启动期间做很多工作来加载和link代码。
这些语言的实现通常是 JIT 编译的。这意味着语言 运行time 系统会在 运行time 将代码（例如字节码）最终翻译为本地代码。 JIT 编译后代码的性能特征发生巨大变化，编译所花费的时间可能很长......并且可能会扭曲您的时间测量。
这些语言的实现通常依赖垃圾收集堆来进行内存管理。一个堆的性能往往是参差不齐的，尤其是在启动时。
这些东西（可能还有其他东西）会导致我们称之为（在 Java 中）JVM 预热开销；特别是 JIT 编译。如果您在方法中不考虑这些开销，那么您的结果很可能会失真。
那么衡量 Java 代码性能的正确方法是什么？
比较复杂，但总的原则是运行基准代码在同一个JVM实例中多次执行，measurin每次迭代。应丢弃前几个测量值（在 JVM 预热期间），其余测量值应取平均值。
如今，推荐的 Java 基准测试方法是使用信誉良好的基准测试框架。两个主要候选人是 Caliper and Oracle's jmh tool.
您提到的性能测量的局限性是什么？
好吧，我在上面已经提到了它们。
性能测量可能会因执行平台上的各种环境因素而失真。
性能可能取决于输入...这可能无法通过简单的测量来揭示。
性能（例如 C/C++ 代码）可能取决于编译器和编译器开关。
性能可能取决于硬件；例如处理器速度、内核数量、内存架构等。
这些因素可能导致难以对特定代码段的性能做出一般陈述，也难以进行一般比较在同一代码的不同版本之间。通常，我们只能做出有限的陈述，例如 "on system X, with compiler Y and input set Z the performance measures are P, Q, R".