喜迎
春节

蓄水池抽样算法：从大数据流中随机取样的优雅解决方案

PHP 算法 蓄水池抽样算法
算法
发布日期:   2025-11-20
文章字数:   1.5k
阅读时长:   5 分

如何在未知总量的数据流中公平地随机抽取样本？蓄水池抽样算法给出了完美的答案。

问题背景

在大数据时代，我们经常面临这样的挑战：需要从一个规模未知或极大的数据集中随机抽取少量样本。比如：

  • 从数十GB的日志文件中随机选取1万条记录进行分析
  • 在实时用户流中随机选择部分用户进行体验调研
  • 从海量搜索查询中抽样用于算法优化

传统方法需要先统计总数再计算抽样位置，这在数据流场景下几乎不可能实现。而蓄水池抽样(Reservoir Sampling) 算法以其简洁和高效完美解决了这一难题。

算法原理

蓄水池抽样的核心思想是维护一个大小为k的”蓄水池”，通过巧妙的概率设计，保证每个元素被选入最终样本的概率完全相等。

基本思路

  1. 初始化阶段：将数据流的前k个元素直接放入蓄水池
  2. 处理阶段：对后续每个元素，以适当的概率决定是否替换蓄水池中的元素
  3. 结果：处理完所有元素后，蓄水池中的k个元素就是均匀随机抽样结果

概率证明

为什么这个算法能保证公平性？关键在于概率设计：

  • 对于前k个元素，初始时被选中的概率为1
  • 当处理第i个元素(i>k)时，它以k/i的概率进入蓄水池
  • 已存在的元素被替换的概率也是精心计算的

最终每个元素被选中的概率都是k/n，其中n为数据流总大小。这种概率设计确保了绝对的公平性。

PHP实现

以下是蓄水池抽样算法的PHP实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
<?php

/**
 * 蓄水池抽样算法实现
 * 从大数据流中随机抽取k个样本
 */
class ReservoirSampling {
    
    /**
     * 从数据流中随机抽取k个样本
     * 
     * @param array $stream 数据流（数组形式）
     * @param int $k 需要抽取的样本数量
     * @return array 抽取的k个样本
     */
    public static function sample($stream, $k) {
        // 参数校验
        if ($k <= 0) {
            throw new InvalidArgumentException("抽样数量k必须大于0");
        }
        
        $n = count($stream);
        if ($n <= $k) {
            // 如果数据流大小不超过k，直接返回全部数据
            return $stream;
        }
        
        $reservoir = [];
        
        // 第一步：前k个元素直接放入蓄水池
        for ($i = 0; $i < $k; $i++) {
            $reservoir[$i] = $stream[$i];
        }
        
        // 第二步：后续元素按概率替换
        for ($i = $k; $i < $n; $i++) {
            // 生成 [0, i] 范围内的随机整数
            $j = random_int(0, $i);
            
            // 如果随机索引落在蓄水池范围内，则替换对应位置的元素
            if ($j < $k) {
                $reservoir[$j] = $stream[$i];
            }
        }
        
        return $reservoir;
    }
    
    /**
     * 验证算法正确性的测试方法
     * 通过多次抽样统计每个元素被选中的频率
     */
    public static function testCorrectness($stream, $k, $iterations = 10000) {
        $countMap = array_fill(0, count($stream), 0);
        $n = count($stream);
        
        for ($t = 0; $t < $iterations; $t++) {
            $samples = self::sample($stream, $k);
            foreach ($samples as $sample) {
                // 找到样本在原始流中的索引
                $index = array_search($sample, $stream);
                if ($index !== false) {
                    $countMap[$index]++;
                }
            }
        }
        
        echo "抽样验证结果 (迭代{$iterations}次):\n";
        $expectedProbability = $k / $n;
        for ($i = 0; $i < $n; $i++) {
            $actualProbability = $countMap[$i] / ($iterations * $k);
            echo "元素[{$i}]: 理论概率=" . number_format($expectedProbability, 4) . 
                 ", 实际概率=" . number_format($actualProbability, 4) . 
                 ", 误差=" . number_format(abs($expectedProbability - $actualProbability), 4) . "\n";
        }
    }
}

// 使用示例
echo "=== 蓄水池抽样算法示例 ===\n";

// 示例1：基础使用
$dataStream = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
$k = 3;

echo "数据流: " . implode(', ', $dataStream) . "\n";
echo "抽取 {$k} 个样本:\n";

$samples = ReservoirSampling::sample($dataStream, $k);
echo "抽样结果: " . implode(', ', $samples) . "\n\n";

// 示例2：验证算法正确性
echo "=== 算法正确性验证 ===\n";
ReservoirSampling::testCorrectness($dataStream, $k, 5000);

// 示例3：处理大规模数据流（模拟）
echo "\n=== 大规模数据流处理示例 ===\n";
$largeStream = [];
for ($i = 1; $i <= 1000; $i++) {
    $largeStream[] = "data_" . $i;
}

$largeSamples = ReservoirSampling::sample($largeStream, 10);
echo "从1000个元素中抽取10个样本:\n";
echo "抽样结果: " . implode(', ', $largeSamples) . "\n";

?>

算法优势

1. 空间效率

只需要O(k)的额外空间，与数据流总大小无关，适合处理海量数据。

2. 时间效率

单次遍历即可完成抽样，时间复杂度为O(n)，极其高效。

3. 数据流友好

不需要预知数据总量，适合实时数据流处理场景。

4. 完全随机

保证每个元素被选中的概率严格相等，满足统计抽样的要求。

实际应用场景

日志分析

1
2
3
4
// 从大型日志文件中随机抽样
$logEntries = readLargeLogFile('server.log');
$sampleLogs = ReservoirSampling::sample($logEntries, 1000);
analyzeLogs($sampleLogs);

用户抽样

1
2
3
4
// 从实时用户流中抽样调研
$userStream = getRealTimeUsers();
$surveyUsers = ReservoirSampling::sample($userStream, 100);
conductSurvey($surveyUsers);

A/B测试

1
2
3
4
// 公平地分配用户到实验组
$allUsers = getAllActiveUsers();
$testGroup = ReservoirSampling::sample($allUsers, 5000);
assignToExperiment($testGroup);

算法变体

加权蓄水池抽样

当不同元素具有不同权重时，可以使用加权版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class WeightedReservoirSampling {
    public static function sample($stream, $weights, $k) {
        $reservoir = [];
        $keyPool = [];
        
        // 前k个直接放入
        for ($i = 0; $i < $k; $i++) {
            $reservoir[$i] = $stream[$i];
            $keyPool[$i] = pow(rand(0, 1), 1 / $weights[$i]);
        }
        
        // 处理后续元素
        for ($i = $k; $i < count($stream); $i++) {
            $key = pow(rand(0, 1), 1 / $weights[$i]);
            $minKey = min($keyPool);
            $minIndex = array_search($minKey, $keyPool);
            
            if ($key > $minKey) {
                $reservoir[$minIndex] = $stream[$i];
                $keyPool[$minIndex] = $key;
            }
        }
        
        return $reservoir;
    }
}

总结

蓄水池抽样算法以其简洁性和高效性，在大数据处理领域占据了重要地位。它解决了数据流场景下的随机抽样难题，为日志分析、用户调研、A/B测试等应用提供了可靠的基础。

该算法的魅力在于：用简单的操作实现复杂的概率保证，这正是优秀算法的典型特征。无论是初学者还是资深工程师，理解并掌握蓄水池抽样都将对处理大数据问题大有裨益。

核心要点记住：维护一个固定大小的池子，用适当的概率进行替换，最终得到公平的随机样本。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/reservoir-sampling.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 蓄水池抽样算法
赏
评 论
 上一篇
加权随机算法：按权重控制的概率选择机制
加权随机算法：按权重控制的概率选择机制
如何让稀有物品掉落率低、普通物品掉落率高？加权随机算法提供了完美的概率控制方案。 问题背景在很多应用场景中，我们需要按照预设的概率分布来进行随机选择，而不是简单的均匀随机： 游戏开发：稀有装备1%概率，普通装备50%概率 推荐系统：热
2025-11-20 算法
PHP 算法 加权随机算法
下一篇 
Parquet 数据格式
Parquet 数据格式
1. Parquet 是什么？Apache Parquet 是一种开源的、列式存储的、为大规模数据分析而设计的文件格式。 它与我们熟悉的 CSV、JSON 等行式存储格式有根本性的不同。让我们通过一个比喻来理解： 行式存储（如 CSV、J
2025-10-16 数据分析
数据存储
PHP 算法 蓄水池抽样算法
算法
发布日期:   2025-11-20
文章字数:   1.5k
阅读时长:   5 分

如何在未知总量的数据流中公平地随机抽取样本？蓄水池抽样算法给出了完美的答案。

问题背景

在大数据时代，我们经常面临这样的挑战：需要从一个规模未知或极大的数据集中随机抽取少量样本。比如：

  • 从数十GB的日志文件中随机选取1万条记录进行分析
  • 在实时用户流中随机选择部分用户进行体验调研
  • 从海量搜索查询中抽样用于算法优化

传统方法需要先统计总数再计算抽样位置，这在数据流场景下几乎不可能实现。而蓄水池抽样(Reservoir Sampling) 算法以其简洁和高效完美解决了这一难题。

算法原理

蓄水池抽样的核心思想是维护一个大小为k的”蓄水池”，通过巧妙的概率设计，保证每个元素被选入最终样本的概率完全相等。

基本思路

  1. 初始化阶段：将数据流的前k个元素直接放入蓄水池
  2. 处理阶段：对后续每个元素，以适当的概率决定是否替换蓄水池中的元素
  3. 结果：处理完所有元素后，蓄水池中的k个元素就是均匀随机抽样结果

概率证明

为什么这个算法能保证公平性？关键在于概率设计：

  • 对于前k个元素，初始时被选中的概率为1
  • 当处理第i个元素(i>k)时，它以k/i的概率进入蓄水池
  • 已存在的元素被替换的概率也是精心计算的

最终每个元素被选中的概率都是k/n，其中n为数据流总大小。这种概率设计确保了绝对的公平性。

PHP实现

以下是蓄水池抽样算法的PHP实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
<?php

/**
 * 蓄水池抽样算法实现
 * 从大数据流中随机抽取k个样本
 */
class ReservoirSampling {
    
    /**
     * 从数据流中随机抽取k个样本
     * 
     * @param array $stream 数据流（数组形式）
     * @param int $k 需要抽取的样本数量
     * @return array 抽取的k个样本
     */
    public static function sample($stream, $k) {
        // 参数校验
        if ($k <= 0) {
            throw new InvalidArgumentException("抽样数量k必须大于0");
        }
        
        $n = count($stream);
        if ($n <= $k) {
            // 如果数据流大小不超过k，直接返回全部数据
            return $stream;
        }
        
        $reservoir = [];
        
        // 第一步：前k个元素直接放入蓄水池
        for ($i = 0; $i < $k; $i++) {
            $reservoir[$i] = $stream[$i];
        }
        
        // 第二步：后续元素按概率替换
        for ($i = $k; $i < $n; $i++) {
            // 生成 [0, i] 范围内的随机整数
            $j = random_int(0, $i);
            
            // 如果随机索引落在蓄水池范围内，则替换对应位置的元素
            if ($j < $k) {
                $reservoir[$j] = $stream[$i];
            }
        }
        
        return $reservoir;
    }
    
    /**
     * 验证算法正确性的测试方法
     * 通过多次抽样统计每个元素被选中的频率
     */
    public static function testCorrectness($stream, $k, $iterations = 10000) {
        $countMap = array_fill(0, count($stream), 0);
        $n = count($stream);
        
        for ($t = 0; $t < $iterations; $t++) {
            $samples = self::sample($stream, $k);
            foreach ($samples as $sample) {
                // 找到样本在原始流中的索引
                $index = array_search($sample, $stream);
                if ($index !== false) {
                    $countMap[$index]++;
                }
            }
        }
        
        echo "抽样验证结果 (迭代{$iterations}次):\n";
        $expectedProbability = $k / $n;
        for ($i = 0; $i < $n; $i++) {
            $actualProbability = $countMap[$i] / ($iterations * $k);
            echo "元素[{$i}]: 理论概率=" . number_format($expectedProbability, 4) . 
                 ", 实际概率=" . number_format($actualProbability, 4) . 
                 ", 误差=" . number_format(abs($expectedProbability - $actualProbability), 4) . "\n";
        }
    }
}

// 使用示例
echo "=== 蓄水池抽样算法示例 ===\n";

// 示例1：基础使用
$dataStream = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
$k = 3;

echo "数据流: " . implode(', ', $dataStream) . "\n";
echo "抽取 {$k} 个样本:\n";

$samples = ReservoirSampling::sample($dataStream, $k);
echo "抽样结果: " . implode(', ', $samples) . "\n\n";

// 示例2：验证算法正确性
echo "=== 算法正确性验证 ===\n";
ReservoirSampling::testCorrectness($dataStream, $k, 5000);

// 示例3：处理大规模数据流（模拟）
echo "\n=== 大规模数据流处理示例 ===\n";
$largeStream = [];
for ($i = 1; $i <= 1000; $i++) {
    $largeStream[] = "data_" . $i;
}

$largeSamples = ReservoirSampling::sample($largeStream, 10);
echo "从1000个元素中抽取10个样本:\n";
echo "抽样结果: " . implode(', ', $largeSamples) . "\n";

?>

算法优势

1. 空间效率

只需要O(k)的额外空间，与数据流总大小无关，适合处理海量数据。

2. 时间效率

单次遍历即可完成抽样，时间复杂度为O(n)，极其高效。

3. 数据流友好

不需要预知数据总量，适合实时数据流处理场景。

4. 完全随机

保证每个元素被选中的概率严格相等，满足统计抽样的要求。

实际应用场景

日志分析

1
2
3
4
// 从大型日志文件中随机抽样
$logEntries = readLargeLogFile('server.log');
$sampleLogs = ReservoirSampling::sample($logEntries, 1000);
analyzeLogs($sampleLogs);

用户抽样

1
2
3
4
// 从实时用户流中抽样调研
$userStream = getRealTimeUsers();
$surveyUsers = ReservoirSampling::sample($userStream, 100);
conductSurvey($surveyUsers);

A/B测试

1
2
3
4
// 公平地分配用户到实验组
$allUsers = getAllActiveUsers();
$testGroup = ReservoirSampling::sample($allUsers, 5000);
assignToExperiment($testGroup);

算法变体

加权蓄水池抽样

当不同元素具有不同权重时，可以使用加权版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class WeightedReservoirSampling {
    public static function sample($stream, $weights, $k) {
        $reservoir = [];
        $keyPool = [];
        
        // 前k个直接放入
        for ($i = 0; $i < $k; $i++) {
            $reservoir[$i] = $stream[$i];
            $keyPool[$i] = pow(rand(0, 1), 1 / $weights[$i]);
        }
        
        // 处理后续元素
        for ($i = $k; $i < count($stream); $i++) {
            $key = pow(rand(0, 1), 1 / $weights[$i]);
            $minKey = min($keyPool);
            $minIndex = array_search($minKey, $keyPool);
            
            if ($key > $minKey) {
                $reservoir[$minIndex] = $stream[$i];
                $keyPool[$minIndex] = $key;
            }
        }
        
        return $reservoir;
    }
}

总结

蓄水池抽样算法以其简洁性和高效性，在大数据处理领域占据了重要地位。它解决了数据流场景下的随机抽样难题，为日志分析、用户调研、A/B测试等应用提供了可靠的基础。

该算法的魅力在于：用简单的操作实现复杂的概率保证，这正是优秀算法的典型特征。无论是初学者还是资深工程师，理解并掌握蓄水池抽样都将对处理大数据问题大有裨益。

核心要点记住：维护一个固定大小的池子，用适当的概率进行替换，最终得到公平的随机样本。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/reservoir-sampling.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 蓄水池抽样算法
赏
评 论
 上一篇
加权随机算法：按权重控制的概率选择机制
加权随机算法：按权重控制的概率选择机制
如何让稀有物品掉落率低、普通物品掉落率高？加权随机算法提供了完美的概率控制方案。 问题背景在很多应用场景中，我们需要按照预设的概率分布来进行随机选择，而不是简单的均匀随机： 游戏开发：稀有装备1%概率，普通装备50%概率 推荐系统：热
2025-11-20 算法
PHP 算法 加权随机算法
下一篇 
Parquet 数据格式
Parquet 数据格式
1. Parquet 是什么？Apache Parquet 是一种开源的、列式存储的、为大规模数据分析而设计的文件格式。 它与我们熟悉的 CSV、JSON 等行式存储格式有根本性的不同。让我们通过一个比喻来理解： 行式存储（如 CSV、J
2025-10-16 数据分析
数据存储
PHP 算法 蓄水池抽样算法
算法
发布日期:   2025-11-20
文章字数:   1.5k
阅读时长:   5 分

如何在未知总量的数据流中公平地随机抽取样本？蓄水池抽样算法给出了完美的答案。

问题背景

在大数据时代，我们经常面临这样的挑战：需要从一个规模未知或极大的数据集中随机抽取少量样本。比如：

  • 从数十GB的日志文件中随机选取1万条记录进行分析
  • 在实时用户流中随机选择部分用户进行体验调研
  • 从海量搜索查询中抽样用于算法优化

传统方法需要先统计总数再计算抽样位置，这在数据流场景下几乎不可能实现。而蓄水池抽样(Reservoir Sampling) 算法以其简洁和高效完美解决了这一难题。

算法原理

蓄水池抽样的核心思想是维护一个大小为k的”蓄水池”，通过巧妙的概率设计，保证每个元素被选入最终样本的概率完全相等。

基本思路

  1. 初始化阶段：将数据流的前k个元素直接放入蓄水池
  2. 处理阶段：对后续每个元素，以适当的概率决定是否替换蓄水池中的元素
  3. 结果：处理完所有元素后，蓄水池中的k个元素就是均匀随机抽样结果

概率证明

为什么这个算法能保证公平性？关键在于概率设计：

  • 对于前k个元素，初始时被选中的概率为1
  • 当处理第i个元素(i>k)时，它以k/i的概率进入蓄水池
  • 已存在的元素被替换的概率也是精心计算的

最终每个元素被选中的概率都是k/n，其中n为数据流总大小。这种概率设计确保了绝对的公平性。

PHP实现

以下是蓄水池抽样算法的PHP实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
<?php

/**
 * 蓄水池抽样算法实现
 * 从大数据流中随机抽取k个样本
 */
class ReservoirSampling {
    
    /**
     * 从数据流中随机抽取k个样本
     * 
     * @param array $stream 数据流（数组形式）
     * @param int $k 需要抽取的样本数量
     * @return array 抽取的k个样本
     */
    public static function sample($stream, $k) {
        // 参数校验
        if ($k <= 0) {
            throw new InvalidArgumentException("抽样数量k必须大于0");
        }
        
        $n = count($stream);
        if ($n <= $k) {
            // 如果数据流大小不超过k，直接返回全部数据
            return $stream;
        }
        
        $reservoir = [];
        
        // 第一步：前k个元素直接放入蓄水池
        for ($i = 0; $i < $k; $i++) {
            $reservoir[$i] = $stream[$i];
        }
        
        // 第二步：后续元素按概率替换
        for ($i = $k; $i < $n; $i++) {
            // 生成 [0, i] 范围内的随机整数
            $j = random_int(0, $i);
            
            // 如果随机索引落在蓄水池范围内，则替换对应位置的元素
            if ($j < $k) {
                $reservoir[$j] = $stream[$i];
            }
        }
        
        return $reservoir;
    }
    
    /**
     * 验证算法正确性的测试方法
     * 通过多次抽样统计每个元素被选中的频率
     */
    public static function testCorrectness($stream, $k, $iterations = 10000) {
        $countMap = array_fill(0, count($stream), 0);
        $n = count($stream);
        
        for ($t = 0; $t < $iterations; $t++) {
            $samples = self::sample($stream, $k);
            foreach ($samples as $sample) {
                // 找到样本在原始流中的索引
                $index = array_search($sample, $stream);
                if ($index !== false) {
                    $countMap[$index]++;
                }
            }
        }
        
        echo "抽样验证结果 (迭代{$iterations}次):\n";
        $expectedProbability = $k / $n;
        for ($i = 0; $i < $n; $i++) {
            $actualProbability = $countMap[$i] / ($iterations * $k);
            echo "元素[{$i}]: 理论概率=" . number_format($expectedProbability, 4) . 
                 ", 实际概率=" . number_format($actualProbability, 4) . 
                 ", 误差=" . number_format(abs($expectedProbability - $actualProbability), 4) . "\n";
        }
    }
}

// 使用示例
echo "=== 蓄水池抽样算法示例 ===\n";

// 示例1：基础使用
$dataStream = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
$k = 3;

echo "数据流: " . implode(', ', $dataStream) . "\n";
echo "抽取 {$k} 个样本:\n";

$samples = ReservoirSampling::sample($dataStream, $k);
echo "抽样结果: " . implode(', ', $samples) . "\n\n";

// 示例2：验证算法正确性
echo "=== 算法正确性验证 ===\n";
ReservoirSampling::testCorrectness($dataStream, $k, 5000);

// 示例3：处理大规模数据流（模拟）
echo "\n=== 大规模数据流处理示例 ===\n";
$largeStream = [];
for ($i = 1; $i <= 1000; $i++) {
    $largeStream[] = "data_" . $i;
}

$largeSamples = ReservoirSampling::sample($largeStream, 10);
echo "从1000个元素中抽取10个样本:\n";
echo "抽样结果: " . implode(', ', $largeSamples) . "\n";

?>

算法优势

1. 空间效率

只需要O(k)的额外空间，与数据流总大小无关，适合处理海量数据。

2. 时间效率

单次遍历即可完成抽样，时间复杂度为O(n)，极其高效。

3. 数据流友好

不需要预知数据总量，适合实时数据流处理场景。

4. 完全随机

保证每个元素被选中的概率严格相等，满足统计抽样的要求。

实际应用场景

日志分析

1
2
3
4
// 从大型日志文件中随机抽样
$logEntries = readLargeLogFile('server.log');
$sampleLogs = ReservoirSampling::sample($logEntries, 1000);
analyzeLogs($sampleLogs);

用户抽样

1
2
3
4
// 从实时用户流中抽样调研
$userStream = getRealTimeUsers();
$surveyUsers = ReservoirSampling::sample($userStream, 100);
conductSurvey($surveyUsers);

A/B测试

1
2
3
4
// 公平地分配用户到实验组
$allUsers = getAllActiveUsers();
$testGroup = ReservoirSampling::sample($allUsers, 5000);
assignToExperiment($testGroup);

算法变体

加权蓄水池抽样

当不同元素具有不同权重时，可以使用加权版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class WeightedReservoirSampling {
    public static function sample($stream, $weights, $k) {
        $reservoir = [];
        $keyPool = [];
        
        // 前k个直接放入
        for ($i = 0; $i < $k; $i++) {
            $reservoir[$i] = $stream[$i];
            $keyPool[$i] = pow(rand(0, 1), 1 / $weights[$i]);
        }
        
        // 处理后续元素
        for ($i = $k; $i < count($stream); $i++) {
            $key = pow(rand(0, 1), 1 / $weights[$i]);
            $minKey = min($keyPool);
            $minIndex = array_search($minKey, $keyPool);
            
            if ($key > $minKey) {
                $reservoir[$minIndex] = $stream[$i];
                $keyPool[$minIndex] = $key;
            }
        }
        
        return $reservoir;
    }
}

总结

蓄水池抽样算法以其简洁性和高效性，在大数据处理领域占据了重要地位。它解决了数据流场景下的随机抽样难题，为日志分析、用户调研、A/B测试等应用提供了可靠的基础。

该算法的魅力在于：用简单的操作实现复杂的概率保证，这正是优秀算法的典型特征。无论是初学者还是资深工程师，理解并掌握蓄水池抽样都将对处理大数据问题大有裨益。

核心要点记住：维护一个固定大小的池子，用适当的概率进行替换，最终得到公平的随机样本。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/reservoir-sampling.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 算法 蓄水池抽样算法
赏
评 论
 上一篇
加权随机算法：按权重控制的概率选择机制
加权随机算法：按权重控制的概率选择机制
如何让稀有物品掉落率低、普通物品掉落率高？加权随机算法提供了完美的概率控制方案。 问题背景在很多应用场景中，我们需要按照预设的概率分布来进行随机选择，而不是简单的均匀随机： 游戏开发：稀有装备1%概率，普通装备50%概率 推荐系统：热
2025-11-20 算法
PHP 算法 加权随机算法
下一篇 
Parquet 数据格式
Parquet 数据格式
1. Parquet 是什么？Apache Parquet 是一种开源的、列式存储的、为大规模数据分析而设计的文件格式。 它与我们熟悉的 CSV、JSON 等行式存储格式有根本性的不同。让我们通过一个比喻来理解： 行式存储（如 CSV、J
2025-10-16 数据分析
数据存储
  目录
  目录
  目录
hexo