为什么二分查找数组比二分查找树稍微快一些？

Question

我使用这两个函数从一个非常大的数据集中搜索查询。它们的速度在开始时大致相同，但当大小变得非常大时，二分查找数组的速度会稍微快一些。这是因为缓存效应吗？数组具有连续的。树有这样的吗？

int binary_array_search(int array[], int length, int query){
//the array has been sorted

  int left=0, right=length-1;
  int mid;
  while(left <= right){
    mid = (left+right)/2;
    if(query == array[mid]){
      return 1;
    }
    else if(query < array[mid]){
      right = mid-1;
    }
    else{
      left = mid+1;
    }
  }
  return 0;
}

// Search a binary search tree
int binary_tree_search(bst_t *tree, int ignore, int query){
  node_t *node = tree->root;
  while(node != NULL){
    int data = node->data;
    if(query < data){
      node = node->left;
    }
    else if(query > data){
      node =node->right;
    }
    else{
      return 1;
    }
  }
  return 0;
}

以下是一些结果：

LENGTH   SEARCHES    binary search  array    binary search tree

 1024       10240        7.336000e-03            8.230000e-03
 2048       20480        1.478000e-02           1.727900e-02
 4096       40960        3.001100e-02           3.596800e-02
 8192       81920        6.132700e-02          7.663800e-02
 16384       163840      1.251240e-01          1.637960e-01

Answer 1

数组可能更快，也应该更快，有几个原因：

由于left和right指针的原因，树中的节点至少比数组中的项大3倍。

例如，在32位系统上，你有12个字节，而不是4个字节，这12个字节很可能被填充到16个字节中，或者在16个字节上对齐。在64位系统上，我们得到8和24到32个字节。

这意味着，对于一个数组，可以在L1缓存中加载3到4倍以上的项。

树中的节点是在堆上分配的，根据分配顺序，这些节点可能在内存中的任何位置(此外，堆可能会被分成碎片)-与可能的数组一次性分配相比，创建这些节点(使用new或alloc)也会花费更多时间-但这可能不是这里速度测试的一部分。

要访问数组中的单个值，只需进行一次读取，对于树，我们需要两个：left或right指针和值。

当达到较低级别的搜索时，要比较的项将在数组中靠近(并且可能已经在L1缓存中)，而它们可能分散在树的内存中。

大多数情况下，由于locality of reference，数组的速度会更快。

Answer 2

是因为缓存效应吗？

当然，这是主要原因。在现代CPU上，缓存透明地用于在内存中读/写数据。

高速缓存比主内存(DRAM)快得多。仅从一个角度来看，访问一级缓存中的数据需要大约4个CPU周期，而访问同一CPU上的DRAM需要大约200个CPU周期，即速度快50倍。

高速缓存对称为高速缓存线的小块进行操作，高速缓存线通常是64字节长。

更多信息：https://en.wikipedia.org/wiki/CPU_cache

数组已按顺序。树有这样的吗？

数组是单个数据块。数组的每个元素都与其相邻元素相邻，即：

+-------------------------------+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------------------------------+
  block of 32 bytes (8 times 4)

每次数组访问获取一个高速缓存线，即64字节或16个整数值。因此，对于数组，下一次访问将在同一缓存行内的可能性相当高(特别是在二进制搜索结束时)，因此将不需要内存访问。

另一方面，树节点是逐个分配的：

                      +------------------------------------------------+
+------------------+  | +------------------+    +------------------+   |
| 0 | left | right | -+ | 2 | left | right | <- | 1 | left | right | <-+
+------------------+    +------------------+    +------------------+
 block 0 of 24 bytes     block 2 of 24 bytes     block 1 of 24 bytes

正如我们所看到的，为了存储3个值，我们使用的内存是上面数组中存储8个值的2倍。因此，树结构更加稀疏，并且在统计上每个64字节的高速缓存线具有更少的数据。

此外，每次内存分配都会返回内存中的一个块，该块可能与先前分配的树节点不相邻。

同样，分配器将每个内存块对齐到至少8个字节(在64位CPU上)，因此会浪费一些字节。更不用说我们需要在每个节点中存储这些left和right指针……

因此，每个树访问，即使在排序的最后，也需要获取一个高速缓存线，即比数组访问慢。

那么，为什么数组在测试中会稍微快一点呢？这是由于二进制搜索造成的。在排序开始时，我们相当随机地访问数据，并且每次访问都与以前的访问相去甚远。所以数组结构在排序的末尾得到了提升。

为了好玩，试着将数组中的线性搜索(即基本搜索循环)与树中的二进制搜索进行比较。我打赌你会对结果感到惊讶;)