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

  @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);
    }
  }

     a
     a b
     a b c
     a b c d

  /** 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;
  }

  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);
    }
  }