我目前正在上数据结构类(class)，正如您所料，我们必须做的其中一件事就是编写一些常见的排序。在编写我的插入排序算法时，我注意到运行速度明显快于我导师的算法(对于 400000 个数据点，我的算法花费了大约 30 秒，他的算法花费了大约 90 秒)。我通过电子邮件将我的代码发给他，当它们都在同一台机器上运行时，结果相同。我们设法浪费了 40 多分钟，慢慢地将他的排序方法改为我的排序方法，直到完全一样，逐字逐句，除了一个看似随意的事情。首先，这是我的插入排序代码:
public static int[] insertionSort(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
此时他的代码与我的代码完全相同，除了我们交换 A[j] 和 A[j - 1] 的行。他的代码做了以下事情:
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
我们发现这 3 行是罪魁祸首。因此，我的代码运行速度明显加快。困惑的是，我们运行 javap -c 来获取一个简单程序的字节码，该程序只有一个 main，其中包含一个数组声明，一个 int j 的变量声明 和我写的和他写的交换的 3 行代码。这是我的交换方法的字节码:
Compiled from "me.java"
public class me {
public me();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: sipush 10000
3: newarray int
5: astore_1
6: bipush 10
8: istore_2
9: aload_1
10: iload_2
11: iaload
12: istore_3
13: aload_1
14: iload_2
15: aload_1
16: iload_2
17: iconst_1
18: isub
19: iaload
20: iastore
21: aload_1
22: iload_2
23: iconst_1
24: isub
25: iload_3
26: iastore
27: return
}
还有我导师方法的字节码:
Compiled from "instructor.java"
public class instructor {
public instructor();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: sipush 10000
3: newarray int
5: astore_1
6: bipush 10
8: istore_2
9: aload_1
10: iload_2
11: iconst_1
12: isub
13: iaload
14: istore_3
15: aload_1
16: iload_2
17: iconst_1
18: isub
19: aload_1
20: iload_2
21: iaload
22: iastore
23: aload_1
24: iload_2
25: iload_3
26: iastore
27: return
}
我看不出这些字节码之间有什么真正的区别。 是什么导致了这种奇怪的行为(我的代码运行速度仍然比他的快 3 倍，而且正如我们预料的那样，当我们为算法提供更大的数组时，这种差异会变得更加剧烈)？这只是 Java 的一个奇怪怪癖吗？此外，这是否发生在您的计算机上？作为引用，这是在 2014 年年中的 MacBook Pro 上运行的，我的代码与此处显示的完全相同，他的代码被推断为与此处显示的代码完全相同，除了那些3 行。
[编辑]这是我的测试类:
public class Tester1 {
public static void main(String[] args){
int[] A = new int[400000];
for(int i = 0; i < A.length; i++){
A[i] = (int) (Math.random() * Integer.MAX_VALUE);
}
double start = System.currentTimeMillis();
insertionSort(A);
System.out.println("My insertion sort took " + (System.currentTimeMillis() - start) + " milliseconds.");
}
public static int[] insertionSort(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
}
第二个文件:
public class Tester2 {
public static void main(String[] args){
int[] A = new int[400000];
for(int i = 0; i < A.length; i++){
A[i] = (int) (Math.random() * Integer.MAX_VALUE);
}
double start = System.currentTimeMillis();
otherInsertion(A);
System.out.println("Other insertion sort took " + (System.currentTimeMillis() - start) + " milliseconds.");
}
public static int[] otherInsertion(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
j--;
}
}
return A;
}
}
以及输出(没有参数，只有 java Tester1 和 java Tester2):
My insertion sort took 37680.0 milliseconds.
Other insertion sort took 86358.0 milliseconds.
这些在 2 个不同的 JVM 中作为 2 个单独的文件运行。
最佳答案
这是loop unrolling优化和common的效果 子表达式消除。根据数组访问指令的顺序，JIT 可以在一种情况下消除冗余加载，但在另一种情况下则不能。
让我详细解释一下。在这两种情况下，JIT 都会展开内部循环的 4 次迭代。
例如对于你的情况:
while (j > 3) {
if (A[j - 1] > A[j]) {
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp; \
} A[j - 1] loaded immediately after store
if (A[j - 2] > A[j - 1]) { /
int temp = A[j - 1];
A[j - 1] = A[j - 2];
A[j - 2] = temp; \
} A[j - 2] loaded immediately after store
if (A[j - 3] > A[j - 2]) { /
int temp = A[j - 2];
A[j - 2] = A[j - 3];
A[j - 3] = temp; \
} A[j - 3] loaded immediately after store
if (A[j - 4] > A[j - 3]) { /
int temp = A[j - 3];
A[j - 3] = A[j - 4];
A[j - 4] = temp;
}
j -= 4;
}
然后JIT消除了冗余的数组加载，生成的程序集看起来像
0x0000000002d53a70: movslq %r11d,%r10
0x0000000002d53a73: lea 0x0(%rbp,%r10,4),%r10
0x0000000002d53a78: mov 0x10(%r10),%ebx ; ebx = A[j]
0x0000000002d53a7c: mov 0xc(%r10),%r9d ; r9d = A[j - 1]
0x0000000002d53a80: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53a83: jle 0x0000000002d539f3
0x0000000002d53a89: mov %r9d,0x10(%r10) ; A[j] = r9d
0x0000000002d53a8d: mov %ebx,0xc(%r10) ; A[j - 1] = ebx
; }
0x0000000002d53a91: mov 0x8(%r10),%r9d ; r9d = A[j - 2]
0x0000000002d53a95: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53a98: jle 0x0000000002d539f3
0x0000000002d53a9e: mov %r9d,0xc(%r10) ; A[j - 1] = r9d
0x0000000002d53aa2: mov %ebx,0x8(%r10) ; A[j - 2] = ebx
; }
0x0000000002d53aa6: mov 0x4(%r10),%r9d ; r9d = A[j - 3]
0x0000000002d53aaa: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53aad: jle 0x0000000002d539f3
0x0000000002d53ab3: mov %r9d,0x8(%r10) ; A[j - 2] = r9d
0x0000000002d53ab7: mov %ebx,0x4(%r10) ; A[j - 3] = ebx
; }
0x0000000002d53abb: mov (%r10),%r8d ; r8d = A[j - 4]
0x0000000002d53abe: cmp %ebx,%r8d ; if (r8d > ebx) {
0x0000000002d53ac1: jle 0x0000000002d539f3
0x0000000002d53ac7: mov %r8d,0x4(%r10) ; A[j - 3] = r8
0x0000000002d53acb: mov %ebx,(%r10) ; A[j - 4] = ebx
; }
0x0000000002d53ace: add $0xfffffffc,%r11d ; j -= 4
0x0000000002d53ad2: cmp $0x3,%r11d ; while (j > 3)
0x0000000002d53ad6: jg 0x0000000002d53a70
循环展开后您的讲师的代码看起来会有所不同:
while (j > 3) {
if (A[j - 1] > A[j]) {
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp; <-- another store instruction between A[j - 1] access
}
if (A[j - 2] > A[j - 1]) {
int temp = A[j - 2];
A[j - 2] = A[j - 1];
A[j - 1] = temp;
}
...
JVM 不会消除 A[j - 1] 的后续加载，因为在上一次加载 A[j - 1] 之后还有另一条存储指令 (尽管在这种特殊情况下，这种优化在理论上是可行的)。
所以，汇编代码的加载指令会比较多，性能会变差:
0x0000000002b53a00: cmp %r8d,%r10d ; if (r10d > r8d) {
0x0000000002b53a03: jle 0x0000000002b53973
0x0000000002b53a09: mov %r8d,0xc(%rbx) ; A[j - 1] = r8d
0x0000000002b53a0d: mov %r10d,0x10(%rbx) ; A[j] = r10d
; }
0x0000000002b53a11: mov 0xc(%rbx),%r10d ; r10d = A[j - 1]
0x0000000002b53a15: mov 0x8(%rbx),%r9d ; r9d = A[j - 2]
0x0000000002b53a19: cmp %r10d,%r9d ; if (r9d > r10d) {
0x0000000002b53a1c: jle 0x0000000002b53973
0x0000000002b53a22: mov %r10d,0x8(%rbx) ; A[j - 2] = r10d
0x0000000002b53a26: mov %r9d,0xc(%rbx) ; A[j - 1] = r9d
; }
0x0000000002b53a2a: mov 0x8(%rbx),%r8d ; r8d = A[j - 2]
0x0000000002b53a2e: mov 0x4(%rbx),%r10d ; r10d = A[j - 3]
请注意，如果您在禁用循环展开优化 (-XX:LoopUnrollLimit=0) 的情况下运行 JVM，则两种情况的性能将相同。
P.S. 可以完全反汇编这两种方法 here , 获得使用
-XX:CompileOnly=Test -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly
关于java - 排序时非常奇怪的效率怪癖，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39927189/
我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/
我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www
我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我
什么是ruby的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht
这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/
HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候
遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg
我基本上来自Java背景并且努力理解Ruby中的模运算。(5%3)(-5%3)(5%-3)(-5%-3)Java中的上述操作产生，2个-22个-2但在Ruby中，相同的表达式会产生21个-1-2.Ruby在逻辑上有多擅长这个？模块操作在Ruby中是如何实现的？如果将同一个操作定义为一个web服务，两个服务如何匹配逻辑。 最佳答案 在Java中，模运算的结果与被除数的符号相同。在Ruby中，它与除数的符号相同。remainder()在Ruby中与被除数的符号相同。您可能还想引用modulooperation.
Java的Collections.unmodifiableList和Collections.unmodifiableMap在Ruby标准API中是否有等价物？ 最佳答案 使用freeze应用程序接口(interface):Preventsfurthermodificationstoobj.ARuntimeErrorwillberaisedifmodificationisattempted.Thereisnowaytounfreezeafrozenobject.SeealsoObject#frozen?.Thismethodretur
Rails相对较新。我正在尝试调用一个API，它应该向我返回一个唯一的URL。我的应用程序中捆绑了HTTParty。我已经创建了一个UniqueNumberController，并且我已经阅读了几个HTTParty指南，直到我想要什么，但也许我只是有点迷路，真的不知道该怎么做。基本上，我需要做的就是调用API，获取它返回的URL，然后将该URL插入到用户的数据库中。谁能给我指出正确的方向或与我分享一些代码？ 最佳答案 假设API为JSON格式并返回如下数据:{"url":"http://example.com/unique-url"