算法(4th ed)(94):基础——数据抽象 4.4.3

阅读数:12 2019 年 11 月 2 日 12:14

算法(4th ed)(94):基础——数据抽象 4.4.3

(更多抽象数据类型的实现:累加器)

表 1.2.13 中的累加器 API 定义了一种能够为用例计算一组数据的实时平均值的抽象数据类型。例如,本书中经常会使用该数据类型来处理实验结果(请见 1.4 节)。它的实现很简单:它维护一个 int 类型的实例变量来记录已经处理过的数据值的数量,以及一个double 类型的实例变量来记录所有数据值之和,将和除以数据数量即可得到平均值。请注意该实现并没有保存数据的值——它可以用于处理大规模的数据(甚至是在一个无法全部保存它们的设备上),而一个大型系统也可以大量使用累加器。这种性能特点很容易被忽视,所以也许应该在 API 中注明,因为一种存储所有数据值的实现可能会使调用它的应用程序用光所有内存。

表 1.2.13 一种能够累加数据的抽象数据类型

APIpublic class Accumulator
             Accumulator()创建一个累加器
       void  addDataValue(double val)添加一个新的数据值
     double  mean()所有数据值的平均值
     String  toString()对象的字符串表示
典型的用例
public class TestAccumulator
{
public static void main(String[] args)
{
int T = Integer.parseInt(args[0]);
Accumulator a = new Accumulator();
for (int t = 0; t < T; t++)
a.addDataValue(StdRandom.random());
StdOut.println(a);
}
}

使用方法
% java TestAccumulator 1000
Mean (1000 values): 0.51829
 
% java TestAccumulator 1000000
Mean (1000000 values): 0.49948
 
% java TestAccumulator 1000000
Mean (1000000 values): 0.50014

数据类型的实现
public class Accumulator
{
private double total;
private int N;
public void addDataValue(double val)
{
N++;
total += val;
}
public double mean()
{ return total/N; }
public String toString()
{ return "Mean (" + N + " values): "
+ String.format("%7.5f", mean()); }
}

评论

发布