算法(4th ed)(40):基础——基础编程模型 3.7.3

阅读数:9 2019 年 10 月 30 日 06:52

算法(4th ed)(40):基础——基础编程模型 3.7.3

(API:我们的标准库)

为了介绍 Java 编程、为了科学计算以及算法的开发、学习和应用,我们也开发了若干库来提供一些实用的功能。这些库大多用于处理输入输出。我们也会使用以下两个库来测试和分析我们的实现。第一个库扩展了Math.random() 方法(见表 1.1.8),以根据不同的概率密度函数得到随机值;第二个库则支持各种统计计算(见表 1.1.9)。

表 1.1.8 我们的随机数静态方法库的 API

public class StdRandom
     static    void setSeed(long seed)设置随机生成器的种子
     static  double random()01 之间的实数
     static     int uniform(int N)0N-1 之间的整数
     static     int uniform(int lo, int hi)lohi-1 之间的整数
     static  double uniform(double lo, double hi)lohi 之间的实数
     static boolean bernoulli(double p)返回真的概率为 p
     static  double gaussian()正态分布,期望值为 0,标准差为 1
     static  double gaussian(double m, double s)正态分布,期望值为 m,标准差为 s
     static     int discrete(double[] a)返回 i 的概率为 a[i]
     static    void shuffle(double[] a)将数组 a 随机排序

注:库中也包含为其他原始类型和 Object 对象重载的 shuffle() 函数。

表 1.1.9 我们的数据分析静态方法库的 API

public class StdStats
     static double max(double[] a)最大值
     static double min(double[] a)最小值
     static double mean(double[] a)平均值
     static double var(double[] a)采样方差
     static double stddev(double[] a)采样标准差
     static double median(double[] a)中位数

StdRandom 的 setSeed() 方法为随机数生成器提供种子,这样我们就可以重复和随机数有关的实验。以上一些方法的实现请参考表 1.1.10。有些方法的实现非常简单,为什么还要在方法库中实现它们?设计良好的方法库对这个问题的标准回答如下。

  • 这些方法所实现的抽象层有助于我们将精力集中在实现和测试本书中的算法,而非生成随机数或是统计计算。每次都自己写完成相同计算的代码,不如直接在用例中调用它们要更简洁易懂。
  • 方法库会经过大量测试,覆盖极端和罕见的情况,是我们可以信任的。这样的实现需要大量的代码。例如,我们经常需要使用的各种数据类型的实现,又比如 Java 的 Arrays 库针对不同数据类型对 sort() 进行了多次重载。

这些是 Java 模块化编程的基础,不过在这里可能有些夸张。但这些方法库的方法名称简单、实现容易,其中一些仍然能作为有趣的算法练习。因此,我们建议你到本书的网站上去学习一下 StdRandom.java 和 StdStats.java 的源代码并好好利用这些经过验证了的实现。使用这些库(以及检验它们)最简单的方法就是从网站上下载它们的源代码并放入你的工作目录。网站上讲解了在各种系统上使用它们的配置目录的方法。

表 1.1.10 StdRandom 库中的静态方法的实现

期望的结果 实现
随机返回 [a,b) 之间的一个 double
public static double uniform(double a, double b)
{ return a + StdRandom.random() * (b-a); }
随机返回 [0..N) 之间的一个 int
public static int uniform(int N)
{ return (int) (StdRandom.random() * N); }
随机返回 [lo,hi) 之间的一个 int
public static int uniform(int lo, int hi)
{ return lo + StdRandom.uniform(hi - lo); }
根据离散概率随机返回的 int 值(出现 i 的概率为 a[i]
public static int discrete(double[] a)
{ // a[] 中各元素之和必须等于 1
double r = StdRandom.random();
double sum = 0.0;
for (int i = 0; i < a.length; i++)
{
sum = sum + a[i];
if (sum >= r) return i;
}
return -1;
}
随机将 double 数组中的元素排序(请见练习 1.1.36)
public static void shuffle(double[] a)
{
int N = a.length;
for (int i = 0; i < N; i++)
{ // 将 a[i] 和 a[i…N-1] 中任意一个元素交换
int r = i + StdRandom.uniform(N-i);
double temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}

评论

发布