获取输入文件或标准输出数据流中行数的近似计数的最快方法是什么？顺便提一下，这是一个概率算法，我在网上找不到很多例子。

数据可能只是来自awk脚本或csv文件的一两列！假设我想对其中一列进行近似分组。我会使用数据库的分组功能，但行数超过60-70亿。我希望在3到4秒内得到第一个近似结果。然后在对先验做出决定后运行贝叶斯或其他方法。你对非常粗略的初始分组计数有什么想法吗？

如果你能提供Python或Java中的算法示例，那将非常有帮助。

回答：

@[隐藏人名]的回答是一个很好的方法，如果你想计算总行数。由于你提到了贝叶斯和先验，我将在这个方向上增加一个答案来计算不同组的百分比。（请看我对你问题的评论。我猜如果你是想知道总数，并且想做一个groupby，估计不同组的百分比会更有意义）。

递归贝叶斯更新：

我将从假设你只有两个组开始（可以扩展以适用于多个组，稍后会解释），group1和group2。

对于你处理的前n行（行）中的m个group1，我们将事件记为M(m,n)。显然，你会看到n-m个group2，因为我们假设它们是仅有的两个可能的组。所以你知道给定group1的百分比（s）的条件下事件M(m,n)的概率，由n次试验的二项分布给出。我们试图以贝叶斯方式估计s。

二项分布的共轭先验是Beta分布。为了简单起见，我们选择Beta(1,1)作为先验（当然，你可以在这里选择自己的alpha和beta参数），这是一个在(0,1)上的均匀分布。因此，对于这个Beta分布，alpha=1和beta=1。

二项分布+贝叶斯先验的递归更新公式如下：

if group == 'group1':    alpha = alpha + 1else:    beta = beta + 1

s的后验实际上也是一个Beta分布：

                s^(m+alpha-1) (1-s)^(n-m+beta-1)p(s| M(m,n)) = ----------------------------------- = Beta (m+alpha, n-m+beta)                      B(m+alpha, n-m+beta)

其中B是Beta函数。要报告估计结果，你可以依赖Beta分布的均值和方差，其中：

mean = alpha/(alpha+beta)var = alpha*beta/((alpha+beta)**2 * (alpha+beta+1))

Python代码：groupby.py

所以几行Python代码来处理你的stdin数据并估计group1的百分比会是这样的：

import sysalpha = 1.beta = 1.for line in sys.stdin:    data = line.strip()    if data == 'group1':        alpha += 1.    elif data == 'group2':        beta += 1.    else:        continue    mean = alpha/(alpha+beta)    var = alpha*beta/((alpha+beta)**2 * (alpha+beta+1))    print 'mean = %.3f, var = %.3f' % (mean, var)

样本数据

我向代码输入了几行数据：

group1group1group1group1group2group2group2group1group1group1group2group1group1group1group2  

近似估计结果

这是我得到的结果：

mean = 0.667, var = 0.056mean = 0.750, var = 0.037mean = 0.800, var = 0.027mean = 0.833, var = 0.020mean = 0.714, var = 0.026mean = 0.625, var = 0.026mean = 0.556, var = 0.025mean = 0.600, var = 0.022mean = 0.636, var = 0.019mean = 0.667, var = 0.017mean = 0.615, var = 0.017mean = 0.643, var = 0.015mean = 0.667, var = 0.014mean = 0.688, var = 0.013mean = 0.647, var = 0.013

结果显示，根据我们的Beta(1,1)先验，group1在处理到第15行时估计占64.7%。你可能会注意到方差随着观察点的增加而不断缩小。

多个组

现在如果你有超过2个组，只需将底层分布从二项分布改为多项分布，然后相应的共轭先验将是Dirichlet分布。其余的你只需做类似的更改。

进一步说明

你说你希望在3-4秒内得到近似估计。在这种情况下，你只需抽取一部分数据并将输出输入到上述脚本中，例如，

head -n100000 YOURDATA.txt | python groupby.py

就这样。希望对你有帮助。