有可能比线性搜索更快的算法？

Question

我听说没有比线性搜索更快的算法(对于未排序的数组),但是,当我运行这个算法(线性)时:

public static void search(int[] arr, int value){
    for(int i = 0; i < arr.length; i++){
        if(arr[i] == value) return;
    }
}

使用长度为1000000的随机数组,查找值的平均时间为75ns,但使用此算法:

public static void skipSearch(int[] arr, int value){
    for(int i = 0; i < arr.length; i+=2){
        if(arr[i] == value) return;
    }
    for(int i = 1; i < arr.length; i+=2){
        if(arr[i] == value) return;
    }
}

我得到一个更短的平均值,68ns？

编辑:很多人说我没有做适当的基准测试,这是侥幸的,但我运行了1000000次这些功能并得到了平均值.每次运行1000000次函数时,第一个算法得到75-76ns,第二个算法得到67-69ns.

我用java System.nanoTime() 来测量它.

码:

int[] arr = new int[1000];
Random r = new Random();
for(int i = 0; i < arr.length; i++){
    arr[i] = r.nextInt();
}
int N = 1000000;
long startTime = System.nanoTime();
for(int i = 0; i < N; i++){
    search(arr, arr[(int) Math.floor(Math.random()*arr.length)]);
}
System.out.println("Average Time: "+(System.nanoTime()-startTime)/(float)N+"ns");
startTime = System.nanoTime();
for(int i = 0; i < N; i++){
    skipSearch(arr, arr[(int) Math.floor(Math.random()*arr.length)]);
}
System.out.println("Average Skip Search Time: "+(System.nanoTime()-startTime)/(float)N+"ns");

Answer 1

很可能,因为你的search()方法没有返回任何东西,并且循环中没有任何动作,JVM中的JIT编译器会优化代码 - 换句话说,在将字节代码加载到JVM之前修改字节代码,以便你的search()方法很可能不会(几乎)做任何事情.哪个是最重要的,它可能也完全消除了循环.JIT优化是非常聪明,它可以找出很多的情况下,当它不需要加载任何代码转换成JVM(但是代码是在字节码.class文件).

然后你只测量随机数 - 而不是你的方法的实时复杂性.

阅读例如如何确保没有jvm和编译器优化发生,应用它并再次运行您的基准测试.

也改变你的search()方法,使它们返回索引 - 从而使优化器的生命更难.但是,有时创建一个无法优化的代码却非常困难:)关闭优化(如上面的链接)更可靠.

通常,对未经优化的代码进行基准测试是没有意义的.然而,在这种情况下,OP想要测量理论算法.他想测量实际的传球次数.他必须确保实际执行循环.这就是他应该关闭优化的原因.

OP认为他所测量的是算法的速度,而事实上算法根本没有机会运行.在这种特殊情况下关闭JIT优化可以修复基准.

Answer 2

这就是为什么我们不关心字面上计算执行时间需要多长时间,以及随着输入复杂性的增加,事物的规模增长.看看渐近运行时分析:

https://en.wikipedia.org/wiki/Analysis_of_algorithms

Answer 3

什么是统计数据value？在你的情况下,它很可能甚至是值.很明显,对于这两种情况,算法的复杂性O(n)和O(n/2) + O(n/2)几乎相同 - 线性时间

Answer 4

它只是偶然的"更快".您可能注意到的是,您的值更常出现在偶数索引上,而不是奇数索引上.