Lucene系列(15)工具类之基数选择算法

Lucene 中对于选择算法，有两个实现，快速选择和基数选择.

上一篇文章讲了IntroSelector，这篇文章讲RadixSelector.

基数排序介绍

基数选择和基数排序非常类似，本文侧重点在于 Lucene 的实现，因此对于基数排序的详细原理就不解释了。

大概介绍下：

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼在打孔卡片制表机（Tabulation Machine）上的贡献 [1]。

它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。

实现原理的话比较好懂。快进到 Lucene 的代码。

org.apache.lucene.util.RadixSelector 源码分析

版本 8.7.0

带有注释的完整源码在：org.apache.lucene.util.RadixSelector 源码分析

因为org.apache.lucene.util.RadixSelector也是对Selector的实现，那么他的入口函数也是 select. 我们从 select 开始分析。

入口 select 方法

  @Override
  // k, 就是 topk 的那个 k
  public void select(int from, int to, int k) {
    // check
    checkArgs(from, to, k);
    // 在这个范围上比较所有值
    // k 使我们求的 topk 的 k
    // 每个值从第 0 个字符开始比较
    // 这是第一层的递归，用来检测递归太深了
    select(from, to, k, 0, 0);
  }

  // 又他妈的是递归吗？？？？
   // * @param d the character number to compare
  //　开始比较的字符的编号，也就是 index

   // * @param l the level of recursion
  private void select(int from, int to, int k, int d, int l) {
    // 如果数据很少了，或者已经递归的太多了，是不是就换个策略，不要再递归了呢
    // 数据变窄了，超过递归深度了，就使用备用的选择算法
    if (to - from <= LENGTH_THRESHOLD || d >= LEVEL_THRESHOLD) {
      getFallbackSelector(d).select(from, to, k);
    } else {
      // 继续递归
      radixSelect(from, to, k, d, l);
    }
  }

可以看到，实现自接口的select方法只是简单的做了一个转发，之后进入重载的select方法。之后的逻辑就是一个条件语句。

如果to-from<100，或者递归层级大于 8 层, 就是用备选的选择算法（快速选择算法）. 否则调用radixSelect.

以内部分为猜想，尚未证实

为什么要限制层数呢

这个问题我开始也百思不得其解。源码中对于这个的注释是：after that many levels of recursion we fall back to introselect anyway this is used as a protection against the fact that radix sort performs worse when there are long common prefixes (probably because of cache locality)

我不明白为什么太长的公共前缀会导致性能变差，在实现时，我们完全可以直接跳过所有的公共前缀长度。

后来猜想，所谓的最坏情况，并不是所有元素都有一个很长的公共前缀，而是递增式的。

  
     a
     a b
     a b c
     a b c d

形如途中所示的数据，会导致 badcase.

当我们开始排序时，第一轮排序 a 全部一样，
第二轮是三个 b 和一个空。因此只有两个桶，一个桶是 1. 一个桶是 all -1. 相当于没怎么排序
第三轮和第二轮一样差劲。这种情况就类似于快排里面的，每次都挑选到了最大的值。导致了最差劲的时间复杂度

但是对于快速选择算法，我们尚且有三者中位数法和中位数的中位数法来避免这一个问题，基数排序没有。因此只能设置阈值，当发现遇到了极端情况时，及时切换到快速选择算法上去。

radixSelect 方法

从方法的名字可以看出来，这是这个类的核心方法了。

2021-03-26-21-49-26

2021-03-26-21-36-59

这个我看了好久。所以注释够多了。

核心流程：

计算公共前缀长度，构建当前字节的直方图
如果有公共前缀，则跳到该位进行计算
如果没有，则将直方图中 k 所在的桶进行递归运算。

就可以找到对应的第 K 位啦。

computeCommonPrefixLengthAndBuildHistogram 方法

这是另外一个值得一提的方法，它的功能是：

计算公共前缀，并填充直方图。

  /** Build a histogram of the number of values per {@link #getBucket(int, int) bucket}
   *  and return a common prefix length for all visited values.
   *  @see #buildHistogram */
  // 构建一个每个桶的值的数量的直方图
  // 返回所有值的公共前缀长度
  // 这里的 k 变了，　这里的 k 是每个值从第 x 位开始比较
  private int computeCommonPrefixLengthAndBuildHistogram(int from, int to, int k, int[] histogram) {
    // 公共前缀
    final int[] commonPrefix = this.commonPrefix;
    // 所以刚开始认为公共前缀的长度，　要么是原有的，要么就是最大长度减去 k, 其实就是要比的除了 k 位之外的，都是公共前缀
    // 这是估计出来的
    int commonPrefixLength = Math.min(commonPrefix.length, maxLength - k);
    for (int j = 0; j < commonPrefixLength; ++j) {
      // 第一个元素的，k+j 个字节
      final int b = byteAt(from, k + j);
      // 公众前缀的数组，在这里其实等于等一个值的 k 位及以后
      commonPrefix[j] = b;
      // 说明第一个长度不够了。即第一个元素全放进去，还没到你预估的公共前缀长度。
      // 说明你算错了，那么真正的公共前缀长度就是第一个元素的值
      if (b == -1) {
        commonPrefixLength = j + 1;
        break;
      }
    }

    // 所有的事情都是从 k 位开始的，　因此之前的位都在以前的递归里面解决了。
    // 上面是进行了假设，假设公共前缀是第一个值的 k 位及以后。
    // 那么公共前缀长度就是 k 位以后的位数
    // 公共前缀是从 k 位开始

    int i;
    // 这轮遍历，是数组上的全部遍历
    // 不算第一个数，因为第一个数已经放到公共前缀里面了，大家都和他比较呢。
    // 假设最后算出来的公共前缀是 3. 那么说明 k->k+3 这期间大家都一样。
    outer: for (i = from + 1; i < to; ++i) {
      for (int j = 0; j < commonPrefixLength; ++j) {
        // 这个我看不懂了啊
        // 这里拿到第二个数字的 k+0 位，k+1 位之类
        final int b = byteAt(i, k + j);
        // 去和公共前缀里面比较，公共前缀里面放的是第一个数字的对应的位
        // 等于就好说，继续算公共前缀
        // 不等于的话，就说明有某一个值的某一个位和第一个值的对应位置不一样了，那就不公共了。
        if (b != commonPrefix[j]) {
          // 公共前缀最长也只能有第一个值那么长
          commonPrefixLength = j;
          if (commonPrefixLength == 0) { // we have no common prefix
            // 如果公共前缀长度为 0，那就没必要继续后面的操作了，
            // 比如第二个值和第一个值完全不一样，那就说明不会有公共前缀了
            // 如果所有的数字没有公共前缀，那么第一个值的第一位，有 i-from 个。
            // 比如我计算到第 8 个的时候，发现大家完全没有公共前缀，但是我既然能到第 8 个。说明前面 7 个值的第一位肯定是一样
            // 那么第一个值的第 k 位的个数就是 7
            histogram[commonPrefix[0] + 1] = i - from;
            // 当前这个值的 k 为至少也有一个。我都遍历到这里了，当然有一个了。
            histogram[b + 1] = 1;
            // 跳出，没有公共前缀，不算了
            break outer;
          }
          // 如果公共前缀还不是 0，那就说明还有的玩。就继续下一个值来进行比较，一直到求到了真正的公共前缀
          break;
        }
      }
    }
    // 上面是一个完整的算公共前缀的过程，要么算完，要么知道发现没有公共前缀
    // 在计算的过程中，根据已有的信息，顺手写了一点点直方图。主要是写了第一位相同的有多少个。以及在我判断挂掉的那一瞬间，那个值有一个。

    if (i < to) {
      // the loop got broken because there is no common prefix
      // 说明上面的循环是跳出了，所以应该没有公共前缀
      assert commonPrefixLength == 0;
      buildHistogram(i + 1, to, k, histogram);
    } else {
      // 有公共前缀
      assert commonPrefixLength > 0;
      // 只要有公共前缀，那么第一个值的第 k 位，大家肯定都是一样的了
      // 我就可以写这个第 k 位这个值，有 to-from 个一样的。
      histogram[commonPrefix[0] + 1] = to - from;
    }

    // 返回公共前缀的长度
    return commonPrefixLength;
  }

代码的核心路径是：

将第一个值全部放在公共前缀里面，此时公共前缀就是第一个值
从第二个开始遍历，逐个字节开始与第一个值进行比较，如果遇到不相等的值，减少公共前缀的长度
根据是否有公共前缀，构建第 K 字节上的值的直方图，一个字节最大值是 256. 加上一个 null 值，直方图共 257 位。
返回公共前缀和直方图。

第 1，2 步骤，就是一个标准的多个字符串求最长公共前缀的算法，与其刷题，不如看源码，到处都是原题呢～.

在org.apache.lucene.util.RadixSelector.select(int, int, int, int, int)方法中，

  private void select(int from, int to, int k, int d, int l) {
    // 如果数据很少了，或者已经递归的太多了，是不是就换个策略，不要再递归了呢
    // 数据变窄了，超过递归深度了，就使用备用的选择算法
    if (to - from <= LENGTH_THRESHOLD || d >= LEVEL_THRESHOLD) {
      getFallbackSelector(d).select(from, to, k);
    } else {
      // 继续递归
      radixSelect(from, to, k, d, l);
    }
  }

比较递归最大深度的时候，使用的是d而不是l. 这是正确的吗？

从注释上看，l 才是递归的深度。
d 过大并不会影响效率，而且 d 最终一定会很大。
```
aaaaaaaaaaac
aaaaaaaaaaab
```
这两个字符串，我们通过一次求解就跳跃到了倒数第一位来进行比较，此时 d 已经大于 8 了。但是程序的时间复杂度很好。
这个值的错误，不会导致编译错误，或者程序结果错误。甚至都不会导致性能极度变差。

那么他导致的是什么呢？导致的是，很多本可以在基数选择的 O(3n) 的时间复杂度下解决的问题，被放到了快速选择的 O(5n) 下去解决。

导致的是平均的线性时间复杂度的常量变大了。

这是我的猜测，我也不知道对不对，还在思考哈哈哈哈。

https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F

最后，欢迎关注我的个人公众号【呼延十】，会不定期更新很多后端工程师的学习笔记。也欢迎直接公众号私信或者邮箱联系我，一定知无不言，言无不尽。 %E6%89%AB%E7%A0%81_%E6%90%9C%E7%B4%A2%E8%81%94%E5%90%88%E4%BC%A0%E6%92%AD%E6%A0%B7%E5%BC%8F-%E6%A0%87%E5%87%86%E8%89%B2%E7%89%88.png

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：[email protected]

更多学习笔记见个人博客或关注微信公众号 < 呼延十 >——>呼延十

Previous
Lucene系列(14)工具类之快速选择算法

基数排序介绍

org.apache.lucene.util.RadixSelector 源码分析

入口 select 方法

radixSelect 方法

computeCommonPrefixLengthAndBuildHistogram 方法

Recommend

不选择使用Lucene的6大原因

Lucene系列(14)工具类之快速选择算法

Lucene系列(17)工具类之bkd树的源码实现

Lucene系列(16)工具类之kdb Bkd树原理概述

经典十大排序算法（含升序降序，基数排序含负数排序）【Java版完整代码】【建议收藏系...

手写基数排序算法

五种常用基数估计算法效果实验及实践建议

老狗啃骨头之算法-基数排序

Python编程：集合工具类之计数器（Counter）详解与实践

【基数排序算法详解】Java/Go/Python/JS/C不同语言实现 - 刀法如飞

About Joyk