java - 搜索数组中元素的索引

Question

这个问题已经有答案了:

How to find the index of an element in an array in Java? (15 个回答)

已关闭 6 年前。

假设我们有一个对象数组，我想找到列表中特定对象的索引，通常我会使用该方法

public static int findIndex(Object[] arr, Object o) {
    int index = -1;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i].equals(o)) {
            index = i;
            break;
        }
    }
    return index;
}

但是，有没有一种更快的方法可以仅使用java.lang来做到这一点？包？

Answer 1

如果您对数据的顺序一无所知，则没有更有效的算法，这就是理论上的最佳算法。您可以使用一些技巧使其速度加快几个百分点。例如:

• 缓存数组的长度
• 执行立即返回而不是 break (就性能而言，休息被认为效率不高)。
• 使用o.equals而不是arr[i].equals 。智能编译器可以缓存vtable的o .

但编译器很可能已经可以自行导出一些优化。

因此，更有效的算法可能是:

public static int findIndex(Object[] arr, Object o) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        if (o.equals(arr[i])) {
            return i;
        }
    }
    return -1;
}

虽然差别不会那么大。如果一个tests两种实现方式，区别在于:

//question first
findIndex (question): 4s 209 469 827
findIndex (answer):   4s 078 955 465
//answer first
findIndex (question): 4s 256 345 171
findIndex (answer):   4s 488 112 895

(由于缓存的原因，首先调用的方法有所不同)。要点是，差异并没有那么大，并且可以通过操作系统调用、其他服务器任务来改变。因此，我们可以有把握地说，我们谈论的是毫秒级的实际性能差异。

但是，如果数据是有序的(通过某种顺序关系)，您可以执行 binary search .

如果您想要进行多次查找，您可以首先将元素插入 HashSet<T> 中。 。这个HashSet<T>平均查找时间为 O(1)(给定良好的哈希函数)。