获取数据时循环和二进制搜索之间的性能

Question

假设我有 n 条记录（键，值）。

现在我想寻找 x 个键来获取它们的值。

清楚地看到，如果 x 很小，二分查找比遍历所有记录以查找正确的键更有效。 BinarySearch 是 Java 8 中数组的一部分。假设我的数组在执行搜索之前已经排序。

所以我的时间复杂度是O(XlogN) + O(X )
解释：

O(logN) 是二分查找的复杂度
O(X) 是获取价值动作的复杂度
O(XlogN) 由于我要查找的记录数

但在某些时候，如果x变得太大（接近n的值），似乎只执行1单遍历我的所有记录，然后与我需要的所有键进行比较以获取值更有效...

for(Record record : records){

    //Since the columns that I look for start with a specific prefix.          
    //This one is one of the factor that makes me confused 
    //when checking the performance.

    if(record.key.startWith(key-family){ 

       switch(record.key){
          case key 0:
            getvalue
            break;

          .......

          case key x:
            getvalue
            break;
       }
     }
}

对于这个解决方案，我的复杂度是 O(N) + O(NX)
解释：

O(N) 是for循环的复杂度
O(NX) 是 switch 语句的复杂性和获取值（最坏情况）直到循环完成。

考虑到record的key的外观不统一。与其他记录集合相比，某些记录集合在以我的密钥系列开头的密钥数量上会有显着差异。

我的问题是：

当x过大导致二分查找效率低下时如何定义？
有什么我可以向你学习的吗？ :)

谢谢。

Answer 1

二分查找需要对输入进行排序，所以这不是一个有效的解决方案。假设您的输入未排序。
循环确实需要遍历所有记录。
键的散列是您可以用来提高比较和获取操作性能的东西。

恕我直言，当我们根据 space、时间复杂度和所涉及的权衡进行比较时，选项 3 要好得多。在 Java 中，您可以在大多数情况下使用 HashMap（假设您不处理大数据中的问题）。

Answer 2

如果 X 接近 N，则对 X 键的二分查找变为 O(N log N)。

X 键的 switch 语句的线性搜索似乎是 N。如果switch实现为纯跳转table。 Java 使用 tableswitch and tablelookup 的智能组合：立即跳转 table 和（较慢的）值数组中的查找。人们可能必须让开关的成本也为 O(log X)，因此总共也为 N(log N)。

现在可以通过使用N个值作为索引来自己完成一个巨大的切换。如果数字在 N（或 4N）范围内，那将是可行的；那就是数组不会太稀疏。

然后你可以制作一个BitSet。然而，现实生活很少如此美好。

看到"record"这个词我什至会说，留给数据库吧

但是有一个很好的解决方案

如果对 X 键进行排序，则对第 i^个键的二进制搜索可以从 (i-1)[=35 的 found/insert 位置开始=]th 键。因此它不是 O(N log N) 而是更少。

ix = Arrays.binarySearch(array, ix, array.length, key);
if (ix < 0) { // Not found, insert position is -x-1 or ~x
    ix = ~ix; // Make it the insert position (x ^= -1; would do too)
}

由于存在不对称性：在不断减小的范围内进行二进制搜索，我进行了对称递归二进制二进制搜索。不是为了性能，而是为了算法。

/**
 * @param array sorted
 * @param keys sorted
 * @return found keys
 */
static Set<Integer> search(int[] array, int[] keys) {
    Set<Integer> foundKeys = new HashSet<>();
    find(foundKeys, array, 0, array.length, keys, 0, keys.length);
    return foundKeys
}

private static find(Set<Integer> foundKeys,
        int[] array, int a0, int an,
        int[] keys, int k0, int kn) {
    if (k0 < kn) {
        int k = (k0 + kn) / 2;
        int key = keys[k];
        int a = Arrays.binarySearch(array, a0, an, key);
        if (a >= 0) {
            foundKeys.add(key);
        } else {
            a = ~a;
        }
        find(foundKeys, array, a0, a, keys, k0, k);
        find(foundKeys, array, a, an, keys, k + 1, kn);
        // The overlap at a / repetition of a is due to:
        // - not found
        // - found but keys theoretically might contain doubles
    }
}

（然而，对键进行排序会花费 O(X log X)，但编译器会做同样的事情。）

获取数据时循环和二进制搜索之间的性能

Performance between loop and binary search when getting data

java

loops

binary-search