相关疑难解决方法(0)

是否有算法来估计值集的中值,模式,偏度和/或峰度,但这不需要一次将所有值存储在内存中？

我想计算基本的统计数据:

• 平均值:算术平均值
• 方差:平均偏差的平均值
• 标准差:方差的平方根
• 中位数:将较大一半的数字与较小的一半分开的值
• mode:在集合中找到最频繁的值
• 偏斜:tl; 博士
• 峰度:tl; 博士

计算任何这些的基本公式是小学算术,我知道它们.还有许多统计库可以实现它们.

我的问题是我正在处理的集合中的大量(数十亿)值:在Python中工作,我不能只使用数十亿个元素创建列表或哈希.即使我用C语言编写,十亿元素数组也不太实用.

数据未排序.它是由其他过程随机,即时生成的.每组的大小变化很大,并且不会提前知道大小.

我已经弄清楚如何很好地处理均值和方差,以任何顺序迭代集合中的每个值.(实际上,在我的情况下,我按照它们生成的顺序来看它们.)这是我正在使用的算法,礼貌http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm:

• 初始化三个变量:count,sum和sum_of_squares
• 对于每个值:
  • 增量计数.
  • 将值添加到sum.
  • 将值的平方添加到sum_of_squares.
• 按计数除以总和,作为变量均值存储.
• 将sum_of_squares除以count,存储为变量mean_of_squares.
• 平方均值,存储为square_of_mean.
• 从mean_of_squares中减去square_of_mean,存储为方差.
• 输出均值和方差.

这种"在线"算法存在缺陷(例如,精度问题,因为sum_of_squares快速增长大于整数范围或浮点精度),但它基本上给了我所需要的,而不必存储每个集合中的每个值.

但我不知道是否存在类似的技术来估计额外的统计数据(中位数,模式,偏度,峰度).只要处理N值所需的内存远小于O(N),我就可以使用有偏差的估计器,或者甚至是在一定程度上损害精度的方法.

如果库具有"在线"计算这些操作中的一个或多个的功能,那么将我指向现有的统计库也会有所帮助.

什么是scala中值的快速实现？

这是我在rosetta代码上找到的:

  def median(s: Seq[Double])  =
  {
    val (lower, upper) = s.sortWith(_<_).splitAt(s.size / 2)
    if (s.size % 2 == 0) (lower.last + upper.head) / 2.0 else upper.head
  }

我不喜欢它因为它做了一种.我知道有一些方法可以计算线性时间的中位数.

编辑:

我想有一组中间函数,我可以在各种场景中使用:

1. 快速,适当的中位数计算,可以在线性时间内完成
2. 平均一个流上工作,你可以遍历多次,但你只能保持O(log n)在内存中值是这样
3. 在流上工作的中位数,你可以O(log n)在内存中保存最多的值,你最多可以遍历一次流(这甚至可能吗？)

请仅发布编译并正确计算中位数的代码.为简单起见,您可以假设所有输入都包含奇数个值.