算法(4th ed)(119):基础——背包、队列和栈 5.1.4

阅读数:5 2019 年 11 月 6 日 07:29

算法(4th ed)(119):基础——背包、队列和栈 5.1.4

(API:背包)

背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素(用例也可以检查背包是否为空或者获取背包中元素的数量)。迭代的顺序不确定且与用例无关。要理解背包的概念,可以想象一个非常喜欢收集弹子球的人。他将所有的弹子球都放在一个背包里,一次一个,并且会不时在所有的弹子球中寻找某一颗拥有某种特点的弹子球。使用Bag 的 API,用例可以将元素添加进背包并根据需要随时使用 foreach 语句访问所有的元素。用例也可以使用栈或是队列,但使用 Bag 可以说明元素的处理顺序不重要。下面代码框所示的 Stats 类是 Bag 的一个典型用例。它的任务是简单地计算标准输入中的所有 double 值的平均值和样本标准差。如果标准输入中有 $N$ 个数字,那么平均值为它们的和除以 $N$,样本标准差为每个值和平均值之差的平方之和除以 $N-1$ 之后的平方根。在这些计算中,数的计算顺序和结果无关,因此我们将它们保存在一个 Bag 对象中并使用 foreach 语法来计算每个和。注意:不需要保存所有的数也可以计算标准差(就像我们在 Accumulator 中计算平均值那样——请见练习 1.2.18)。用 Bag 对象保存所有数字是更复杂的统计计算所必需的。

算法(4th ed)(119):基础——背包、队列和栈 5.1.4

图 1.3.1 背包的操作

以下代码框列出的是常用的背包用例。

背包的典型用例

复制代码
public class Stats
{
public static void main(String[] args)
{
Bag<Double> numbers = new Bag<Double>();
while (!StdIn.isEmpty())
numbers.add(StdIn.readDouble());
int N = numbers.size();
double sum = 0.0;
for (double x : numbers)
sum += x;
double mean = sum/N;
sum = 0.0;
for (double x : numbers)
sum += (x - mean)*(x - mean);
double std = Math.sqrt(sum/(N-1));
StdOut.printf("Mean: %.2f\n", mean);
StdOut.printf("Std dev: %.2f\n", std);
}
}

使用方法

复制代码
% java Stats
100
99
101
120
98
107
109
81
101
90
Mean: 100.60
Std dev: 10.51

评论

发布