# 练习43：一个简单的统计引擎
> 原文：[Exercise 43: A Simple Statistics Engine](http://c.learncodethehardway.org/book/ex43.html)
> 译者：[飞龙](https://github.com/wizardforcel)
这是一个简单的算法，我将其用于“联机”（不储存任何样本）收集概要统计。我在任何需要执行一些统计，比如均值、标准差和求和中使用它，但是其中我并不会储存所需的全部样本。我只需要储存计算出的结果，它们仅仅含有5个数值。
## 计算标准差和均值
首先你需要一系列样本。它可以使任何事情，比如完成一个任务所需的时间，某人访问某个东西的次数，或者甚至是网站的评分。是什么并不重要，只要你能得到一些数字，并且你想要知道它们的下列概要统计值：
`sum`
对所有数字求和。
`sumsq`（平方和）
对所有数字求平方和。
`count(n)`
求出样本数量。
`min`
求出样本最小值。
`max`
求出样本最大值。
`mean`
求出样本的均值。它类似于但又不是中位数，但可作为中位数的估计。
`stddev`
使用`$sqrt(sumsq - (sum * mean) / (n - 1) )`来计算标准差，其中`sqrt`为`math.h`头文件中的平方根。
我将会使用R来验证这些计算，因为我知道R能够计算正确。
```r
> s <- runif(n=10, max=10)
> s
[1] 6.1061334 9.6783204 1.2747090 8.2395131 0.3333483 6.9755066 1.0626275
[8] 7.6587523 4.9382973 9.5788115
> summary(s)
Min. 1st Qu. Median Mean 3rd Qu. Max.
0.3333 2.1910 6.5410 5.5850 8.0940 9.6780
> sd(s)
[1] 3.547868
> sum(s)
[1] 55.84602
> sum(s * s)
[1] 425.1641
> sum(s) * mean(s)
[1] 311.8778
> sum(s * s) - sum(s) * mean(s)
[1] 113.2863
> (sum(s * s) - sum(s) * mean(s)) / (length(s) - 1)
[1] 12.58737
> sqrt((sum(s * s) - sum(s) * mean(s)) / (length(s) - 1))
[1] 3.547868
>
```
你并不需要懂得R，只需要看着我拆分代码来解释如何检查这些运算：
lines 1-4
我使用`runit`函数来获得“随机形式”的数字分布，之后将它们打印出来。我会在接下来的单元测试中用到它。
lines 5-7
这个就是概要，便于你看到R如何计算它们。
lines 8-9
这是使用`sd`函数计算的`stddev`。
lines 10-11
现在我开始手动进行这一计算，首先计算`sum`。
lines 12-13
`stddev`公式中的下一部分是`sumsq`，我可以通过`sum(s * s)`来得到，它告诉R将整个`s`列表乘以其自身，之后计算它们的`sum`。R的可以在整个数据结构上做运算，就像这样。
lines 14-15
观察那个公式，我之后需要`sum`乘上`mean`，所以我执行了`sum(s) * mean(s)`。
lines 16-17
我接着将`sumsq`参与运算，得到`sum(s * s) - sum(s) * mean(s)`。
lines 18-19
还需要除以`n - 1`，所以我执行了`(sum(s * s) - sum(s) * mean(s)) / (length(s) - 1)`。
lines 20-21
随后，我使用`sqrt`算出平方根，并得到3.547868，它符合R通过`sd`的运算结果。
## 实现
这就是计算`stddev`的方法，现在我可以编写一些简单的代码来实现这一计算。
```c
#ifndef lcthw_stats_h
#define lctwh_stats_h
typedef struct Stats {
double sum;
double sumsq;
unsigned long n;
double min;
double max;
} Stats;
Stats *Stats_recreate(double sum, double sumsq, unsigned long n, double min, double max);
Stats *Stats_create();
double Stats_mean(Stats *st);
double Stats_stddev(Stats *st);
void Stats_sample(Stats *st, double s);
void Stats_dump(Stats *st);
#endif
```
这里你可以看到我将所需的统计量放入一个struct，并且创建了用于处理样本和获得数值的函数。实现它只是转换数字的一个练习：
```c
#include <math.h>
#include <lcthw/stats.h>
#include <stdlib.h>
#include <lcthw/dbg.h>
Stats *Stats_recreate(double sum, double sumsq, unsigned long n, double min, double max)
{
Stats *st = malloc(sizeof(Stats));
check_mem(st);
st->sum = sum;
st->sumsq = sumsq;
st->n = n;
st->min = min;
st->max = max;
return st;
error:
return NULL;
}
Stats *Stats_create()
{
return Stats_recreate(0.0, 0.0, 0L, 0.0, 0.0);
}
double Stats_mean(Stats *st)
{
return st->sum / st->n;
}
double Stats_stddev(Stats *st)
{
return sqrt( (st->sumsq - ( st->sum * st->sum / st->n)) / (st->n - 1) );
}
void Stats_sample(Stats *st, double s)
{
st->sum += s;
st->sumsq += s * s;
if(st->n == 0) {
st->min = s;
st->max = s;
} else {
if(st->min > s) st->min = s;
if(st->max < s) st->max = s;
}
st->n += 1;
}
void Stats_dump(Stats *st)
{
fprintf(stderr, "sum: %f, sumsq: %f, n: %ld, min: %f, max: %f, mean: %f, stddev: %f",
st->sum, st->sumsq, st->n, st->min, st->max,
Stats_mean(st), Stats_stddev(st));
}
```
下面是` stats.c`中每个函数的作用：
Stats_recreate
我希望从一些数据中加载这些数据，这和函数让我重新创建`Stats`结构体。
Stats_create
只是以全0的值调用`Stats_recreate`。
Stats_mean
使用`sum`和`n`计算均值。
Stats_stddev
实现我之前的公式，唯一的不同就是我使用`t->sum / st->n`来计算均值，而不是调用`Stats_mean`。
Stats_sample
它用于在`Stats`结构体中储存数值。当你向它提供数值时，它看到`n`是0，并且相应地设置`min`和`max`。之后的每次调用都会使`sum`、`sumsq`和`n`增加，并且计算出这一新的样本的`min`和`max`值。
Stats_dump
简单的调试函数，用于转储统计量，便于你看到它们。
我需要干的最后一件事，就是确保这些运算正确。我打算使用我的样本，以及来自于R会话中的计算结果创建单元测试，来确保我会得到正确的结果。
```c
#include "minunit.h"
#include <lcthw/stats.h>
#include <math.h>
const int NUM_SAMPLES = 10;
double samples[] = {
6.1061334, 9.6783204, 1.2747090, 8.2395131, 0.3333483,
6.9755066, 1.0626275, 7.6587523, 4.9382973, 9.5788115
};
Stats expect = {
.sumsq = 425.1641,
.sum = 55.84602,
.min = 0.333,
.max = 9.678,
.n = 10,
};
double expect_mean = 5.584602;
double expect_stddev = 3.547868;
#define EQ(X,Y,N) (round((X) * pow(10, N)) == round((Y) * pow(10, N)))
char *test_operations()
{
int i = 0;
Stats *st = Stats_create();
mu_assert(st != NULL, "Failed to create stats.");
for(i = 0; i < NUM_SAMPLES; i++) {
Stats_sample(st, samples[i]);
}
Stats_dump(st);
mu_assert(EQ(st->sumsq, expect.sumsq, 3), "sumsq not valid");
mu_assert(EQ(st->sum, expect.sum, 3), "sum not valid");
mu_assert(EQ(st->min, expect.min, 3), "min not valid");
mu_assert(EQ(st->max, expect.max, 3), "max not valid");
mu_assert(EQ(st->n, expect.n, 3), "max not valid");
mu_assert(EQ(expect_mean, Stats_mean(st), 3), "mean not valid");
mu_assert(EQ(expect_stddev, Stats_stddev(st), 3), "stddev not valid");
return NULL;
}
char *test_recreate()
{
Stats *st = Stats_recreate(expect.sum, expect.sumsq, expect.n, expect.min, expect.max);
mu_assert(st->sum == expect.sum, "sum not equal");
mu_assert(st->sumsq == expect.sumsq, "sumsq not equal");
mu_assert(st->n == expect.n, "n not equal");
mu_assert(st->min == expect.min, "min not equal");
mu_assert(st->max == expect.max, "max not equal");
mu_assert(EQ(expect_mean, Stats_mean(st), 3), "mean not valid");
mu_assert(EQ(expect_stddev, Stats_stddev(st), 3), "stddev not valid");
return NULL;
}
char *all_tests()
{
mu_suite_start();
mu_run_test(test_operations);
mu_run_test(test_recreate);
return NULL;
}
RUN_TESTS(all_tests);
```
这个单元测试中没什么新东西，除了`EQ`宏。我比较懒，并且不想查询比较两个`double`值的标准方法，所以我使用了这个宏。`double`的问题是等性不是完全相等，因为我使用了两个不同的系统，并带有不同的四舍五入的位数。解决方案就是判断两个数“乘以10的X次方是否相等”。
我使用`EQ`来计算数字的10的幂，之后使用`round`函数来获得证书。这是个简单的方法来四舍五入N位小数，并以整数比较结果。我确定有数以亿计的其它方法能做相同的事情，但是现在我就用这种。
预期结果储存在`Stats` `struct`中，之后我只是确保我得到的数值接近R给我的数值。
## 如何使用
你可以使用标准差和均值来决定一个新的样本是否是“有趣”的，或者你可以使用它们计算统计量的统计量。前者对于人们来说更容易理解，所以我用登录的例子来做个简短的解释。
假设你在跟踪人们花费多长时间在一台服务器上，并且你打算用统计来分析它。每次有人登录进来，你都对它们在这里的时长保持跟踪，之后调用`Stats_sample`函数。我会寻找停留“过长”时间的人，以及“过短”的人。
比起设定特殊的级别，我更倾向于将一个人的停留时间与`mean (plus or minus) 2 * stddev`这个范围进行比较。我计算出`mean`和`2 * stddev`，并且如果它们在这个范围之外，我就认为是“有趣”的。由于我使用了联机算法来维护这些统计量，所以它非常快，并且我可以使软件标记在这个范围外的用户。
这不仅仅用于找出行为异常的用户，更有助于标记一些潜在的问题，你可以查看它们来观察发生了什么。它基于所有用户的行为来计算，这也避免了你任意挑出一个数值而并不基于实际情况的问题。
你可以从中学到的通用规则是，`mean (plus or minus) 2 * stddev`是90%的值预期所属的范围预测值，任何在它之外的值都是有趣的。
第二种利用这些统计量的方式就是继续将其用于其它的`Stats`计算。基本上像通常一样使用`Stats_sample`，但是之后在`min`、`max`、`n`、`mean`和`stddev`上执行`Stats_sample`。这会提供二级的度量，并且让你对比样本的样本。
被搞晕了吗？我会以上面的例子基础，并且假设你拥有100台服务器，每台都运行一个应用。你已经在每个应用服务器上跟踪了用户的登录时长，但是你想要比较所有的这100和应用，并且标记它们当中任何登录时间过长的用户。最简单的方式就是每次有人登录进来时，计算新的登录统计量，之后将`Stats structs`的元素添加到第二个`Stats`中。
你最后应该会得到一些统计量，它们可以这样命名：
均值的均值
这是一个`Stats struct`，它向你提供所有服务器的均值的`mean`和`stddev`。你可以用全局视角来观察任何在此之外的用户或服务器。
标准差的均值
另一个`Stats struct`，计算这些服务器的分布的统计量。你之后可以分析每个服务器并且观察是否它们中的任何服务器具有异常分散的分布，通过将它们的`stddev`和这个`mean of stddevs`统计量进行对比。
你可以计算出全部统计量，但是这两个是最有用的。如果你打算监视服务器上的移除登录时间，你可以这样做：
+ 用户John登录并登出服务器A。获取服务器A的统计量，并更新它们。
+ 获取`mean of means`统计量，计算出A的均值并且将其加入样本。我叫它`m_of_m`。
+ 获取`mean of stddev`统计量，将A的标准差添加到样本中。我叫它` m_of_s`。
+ 如果A的`mean`在`m_of_m.mean + 2 * m_of_m.stddev`范围外，标记它可能存在问题。
+ 如果A的`stddev`在`m_of_s.mean + 2 * m_of_s.stddev`范围外，标记它可能存在行为异常。
+ 最后，如果John的登录时长在A的范围之外，或A的`m_of_m`范围之外，标记为有趣的。
通过计算“均值的均值”，或者“标准差的均值”，你可以以最小的执行和储存总量，有效地跟踪许多度量。
## 附加题
+ 将`Stats_stddev` 和 `Stats_mean`转换为`static inline`函数，放到`stats.h`文件中，而不是`stats.c`文件。
+ 使用这份代码来编写`string_algos_test.c`的性能测试。使它为可选的，并且运行基准测试作为一系列样本，之后报告结果。
+ 编写它的另一个语言的版本。确保这个版本基于我的数据正确执行。
+ 编写一个小型程序，它能从文件读取所有数字，并执行这些统计。
+ 使程序接收一个数据表，其中第一行是表头，剩下的行含有任意数量空格分隔的数值。你的程序应该按照表头中的名称，打印出每一列的统计值。
- 笨办法学C 中文版
- 前言
- 导言：C的笛卡尔之梦
- 练习0：准备
- 练习1：启用编译器
- 练习2：用Make来代替Python
- 练习3：格式化输出
- 练习4：Valgrind 介绍
- 练习5：一个C程序的结构
- 练习6：变量类型
- 练习7：更多变量和一些算术
- 练习8：大小和数组
- 练习9：数组和字符串
- 练习10：字符串数组和循环
- 练习11：While循环和布尔表达式
- 练习12：If，Else If，Else
- 练习13：Switch语句
- 练习14：编写并使用函数
- 练习15：指针，可怕的指针
- 练习16：结构体和指向它们的指针
- 练习17：堆和栈的内存分配
- 练习18：函数指针
- 练习19：一个简单的对象系统
- 练习20：Zed的强大的调试宏
- 练习21：高级数据类型和控制结构
- 练习22：栈、作用域和全局
- 练习23：认识达夫设备
- 练习24：输入输出和文件
- 练习25：变参函数
- 练习26：编写第一个真正的程序
- 练习27：创造性和防御性编程
- 练习28：Makefile 进阶
- 练习29：库和链接
- 练习30：自动化测试
- 练习31：代码调试
- 练习32：双向链表
- 练习33：链表算法
- 练习34：动态数组
- 练习35：排序和搜索
- 练习36：更安全的字符串
- 练习37：哈希表
- 练习38：哈希算法
- 练习39：字符串算法
- 练习40：二叉搜索树
- 练习41：将 Cachegrind 和 Callgrind 用于性能调优
- 练习42：栈和队列
- 练习43：一个简单的统计引擎
- 练习44：环形缓冲区
- 练习45：一个简单的TCP/IP客户端
- 练习46：三叉搜索树
- 练习47：一个快速的URL路由
- 后记：“解构 K&R C” 已死
- 捐赠名单