1. 真实场景：千万级请求ID的Top100实时排行榜

去年双11大促，我负责的抢购系统需要统计“当前请求量最大的Top100商品ID”。每个请求都会携带商品ID（正整数，范围1～1亿，ID不重复）。数据源是Kafka，消费进度大概是每秒5万条。我们需要在消费端实时维护一个Top100排行榜，供监控大屏和限流决策使用。

最初我用的是「小顶堆」方案，稳定但总觉得不够快。后来尝试了「快速选择」和「BitMap」两种方案，踩了不少坑。这篇文章将直接给出三种方案的完整PHP实现、压测数据对比，以及我掉进去过的坑。

2. 问题定义

输入：一个长度为N的整数数组，所有元素互不重复（方便BitMap对比），且数值范围已知为[1, MAX_INT]。输出：最大的K个元素，按升序或降序排列。

业务要求：实时性高，单次查询耗时<200ms，内存<1GB。本文以N=10,000,000，K=100，MAX_INT=100,000,000 为测试条件。

3. 方案一：小顶堆（Min-Heap）

3.1 原理

维护一个大小为K的小顶堆，遍历数组：当堆未满时直接插入；当堆已满时，若当前元素大于堆顶（最小值），则弹出堆顶并插入新元素。最终堆中即为最大的K个元素。

时间复杂度O(N log K)，空间复杂度O(K)。

3.2 PHP实现（PHP 8.3，使用SplMinHeap）

class TopKMinHeap {
    private \SplMinHeap $heap;
    private int $k;

    public function __construct(int $k) {
        $this->k = $k;
        $this->heap = new \SplMinHeap();
    }

    public function add(int $value): void {
        if ($this->heap->count() < $this->k) {
            $this->heap->insert($value);
        } elseif ($value > $this->heap->top()) {
            $this->heap->extract();
            $this->heap->insert($value);
        }
    }

    public function topK(): array {
        $result = [];
        while (!$this->heap->isEmpty()) {
            array_unshift($result, $this->heap->extract());
        }
        return $result;
    }
}

// 使用示例
$data = range(1, 10000000); // 生成1千万不重复整数
shuffle($data);
$heap = new TopKMinHeap(100);
foreach ($data as $v) {
    $heap->add($v);
}
$top = $heap->topK();

4. 方案二：快速选择（QuickSelect）

4.1 原理

快速选择是快速排序的变体，通过partition将数组分成两部分，并根据分界点的位置决定继续在左/右部分递归。平均时间复杂度O(N)，最坏O(N²)。

用于TopK时，可以找到第K大的元素，然后对前K个元素排序（或线性收集）。这里我们实现一个基于递归的版本，找到最大的K个元素（降序排列）。

4.2 PHP实现

function quickSelect(array &$arr, int $left, int $right, int $k): void {
    if ($left >= $right) return;

    // 三数取中法选pivot（避免最坏情况）
    $mid = $left + intdiv($right - $left, 2);
    if ($arr[$mid] < $arr[$left]) swap($arr, $left, $mid);
    if ($arr[$right] < $arr[$left]) swap($arr, $left, $right);
    if ($arr[$mid] < $arr[$right]) swap($arr, $mid, $right);

    $pivot = $arr[$right];
    $i = $left;
    for ($j = $left; $j < $right; $j++) {
        if ($arr[$j] >= $pivot) { // 降序排列，大于等于放左边
            swap($arr, $i++, $j);
        }
    }
    swap($arr, $i, $right);

    $count = $i - $left + 1;
    if ($count == $k) {
        return; // 前K个已经到位
    } elseif ($count > $k) {
        quickSelect($arr, $left, $i - 1, $k);
    } else {
        quickSelect($arr, $i + 1, $right, $k - $count);
    }
}

function swap(array &$arr, int $i, int $j): void {
    $tmp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $tmp;
}

// 使用示例
$data = range(1, 10000000);
shuffle($data);
$k = 100;
quickSelect($data, 0, count($data) - 1, $k);
$top = array_slice($data, 0, $k);
sort($top); // 可选：升序输出

5. 方案三：BitMap（位图）

5.1 原理

BitMap通常用于整数存在性判断。对于不重复整数数组，我们可以构建一个位图，将所有整数置1，然后从最大索引向低扫描，收集前K个。这种方法特别适用于数值范围小且内存可承受的场景：这里MAX_INT=1亿，需要1亿位≈12.5MB内存，非常小。

时间复杂度：构建位图O(N)，扫描位图O(MAX_INT/word_size)。整体O(N + MAX_INT)。

5.2 PHP实现（使用GMP整数模拟位图）

function topKByBitMap(array $data, int $maxInt, int $k): array {
    $bits = 0; // GMP整数
    foreach ($data as $v) {
        gmp_setbit($bits, $v, 1);
    }
    $result = [];
    for ($i = $maxInt; $i >= 0 && count($result) < $k; $i--) {
        if (gmp_testbit($bits, $i)) {
            $result[] = $i;
        }
    }
    return $result;
}

// 使用示例
$data = range(1, 10000000);
shuffle($data);
$top = topKByBitMap($data, 100000000, 100);

6. 效果数据对比

6.1 测试环境

• CPU: Intel Xeon Platinum 8260 @ 2.40GHz (8核)
• 内存: 64GB
• PHP: 8.3.9 (JIT enabled with tracing mode)
• 数据: 10,000,000个不重复随机整数，范围[1, 100,000,000]，K=100
• 内存限制: 不限制，但记录峰值

6.2 执行时间对比

每种方案运行10次取中位数，单位毫秒。

补充说明：快速选择需要将整个数组加载到内存（约380MB，因为10M个整数 + PHP数组开销），堆和BitMap都只需常数量内存。BitMap的22ms中，构建位图用了18ms，扫描用4ms。

6.3 扩展性测试

当N=50,000,000，MAX_INT=1亿时，BitMap仍然稳定在32ms（建图30ms），而快选内存暴涨到2.1GB（PHP数组索引开销巨大），堆方案耗时380ms。BitMap在范围可控时优势巨大。

7. 避坑指南

坑1：快速选择的递归导致栈溢出

对1000万数据直接递归，PHP默认递归深度只有256，会抛出“Maximum function nesting level reached”。解决方案：编写迭代版本，或使用三数取中选pivot减少递归深度。我的迭代版本如下：

function quickSelectIterative(array &$arr, int $k): void {
    $left = 0;
    $right = count($arr) - 1;
    while ($left < $right) {
        // partition略...
        // 根据count调整left/right
    }
}

但迭代版代码复杂度翻倍，且仍需注意尾递归优化。

坑2：BitMap的数值范围过大

如果MAX_INT=10亿，位图需要125MB内存，加上PHP的GMP内部表示会更重。测试发现GMP处理2^32位（512MB）时，建图耗时约3秒，远不如堆。所以BitMap只适合范围不超过1亿的场景。另注意整数的类型：GMP默认使用有符号整数，setbit超过32位需要同时修改二进制表示，务必保证$maxInt在gmp_init范围之内。

坑3：堆方案中SplHeap的性能陷阱

SplHeap内部使用PHP对象操作，每次insert/extract都会触发自动调整，在1000万数据下表现良好。但如果换成数组手动维护堆（如自己写heapify），性能可能更优但代码变长。实测数组手动堆比SplHeap快约15%，但代码量翻倍。选型时需权衡维护成本。

// 手动实现小顶堆（仅片段）
$heap = [];
foreach($data as $v) {
    if (count($heap) < $k) {
        $heap[] = $v;
        // 上浮
    } else {
        if ($v > $heap[0]) {
            $heap[0] = $v;
            // 下沉
        }
    }
}

坑4：数据重复时的处理

本文的BitMap方案假设数据不重复。如果存在重复元素，BitMap只能记录存在性，无法统计频次。此时需要先用Hash表统计频次，然后对频次进行TopK，这又回到了“频次统计+堆”的方案。切勿直接用BitMap处理重复数据。

8. 总结

三种方案各有适用场景：

• 堆：最通用，数据量极大且K较小时最稳定，内存可控，适合流式数据。
• 快速选择：追求极致速度且内存充足（能一次装下数据）时首选，注意递归导致的栈溢出。
• BitMap：数值范围已知且不大（≤1亿）且数据不重复时，性能碾压其他方案，内存优势明显。

在实际业务中，我最终采用了“堆方案 + 热点数据预计算”的混合策略。如果你也遇到类似场景，建议先评估数据特征，不要盲目选“最快”的算法。