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

Posted1 by 呼延十 on March 26, 2021 Hot:

前言

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

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

核心流程:

  1. 计算公共前缀长度,构建当前字节的直方图
  2. 如果有公共前缀,则跳到该位进行计算
  3. 如果没有,则将直方图中 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;
  }

代码的核心路径是:

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

第 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. 这是正确的吗?

  1. 从注释上看,l 才是递归的深度。
  2. d 过大并不会影响效率,而且 d 最终一定会很大。
    aaaaaaaaaaac
    aaaaaaaaaaab
    

    这两个字符串,我们通过一次求解就跳跃到了倒数第一位来进行比较,此时 d 已经大于 8 了。但是程序的时间复杂度很好。

  3. 这个值的错误,不会导致编译错误,或者程序结果错误。甚至都不会导致性能极度变差。

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

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

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

思考题答案

经过一番思考,我确认了这就是个bug.在Jira上提交给官方后,提交patch修复了这个bug.

Jira链接

Fix-Commit链接

参考文章

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


完。

联系我

最后,欢迎关注我的个人公众号【 呼延十 】,会不定期更新很多后端工程师的学习笔记。 也欢迎直接公众号私信或者邮箱联系我,一定知无不言,言无不尽。


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

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

联系邮箱:huyanshi2580@gmail.com

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