# 練習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`的性能測試。使它為可選的，并且運行基準測試作為一系列樣本，之后報告結果。 + 編寫它的另一個語言的版本。確保這個版本基于我的數據正確執行。 + 編寫一個小型程序，它能從文件讀取所有數字，并執行這些統計。 + 使程序接收一個數據表，其中第一行是表頭，剩下的行含有任意數量空格分隔的數值。你的程序應該按照表頭中的名稱，打印出每一列的統計值。