1. 算法基础

2019-10-10  本文已影响0人  璎珞纨澜

基础编程模型

描述和实现算法所用到的语言特性、软件库和操作系统称为基础编程模型

Java 程序的基本结构

原始数据类型和表达式

四种 Java 语言最基本的原始数据类型:

Java 程序控制用 标识符 命名 变量;用 表达式 实现对各种类型的操作;用运算符来指定操作;用字面量来表示具体的值。

Java程序的基本组成
原始数据类型

下表总结了 Java 的int、double、bolean和char类型的相关信息。

+、-、*、/ 运算符都是被 重载 过的,同样的运算符对不同的数据类型会执行不同的操作。例如,5/3 的值是1 而 5.0/3.0 的值是1.66666666666667,两者都很接近但是并不准确地等于5/3。

Java中的原始数据类型
Java中的原始数据类型(续)
表达式

当一个表达式包含一个以上运算符时,运算符优先级:

类型转换
比较运算符

比较运算符:相等( == )、不等( != )、小于( < )、小于等于( > )、大于( >= )、大于等于( <= )。

其他数据类型

64位整数 - long
16位整数 - short
16位字符 - char
8位整数 - byte
32位单精度实数 - float

语句

声明语句

声明语句将一个变量名和一个类型在编译时关联起来。Java是 强类型 语言,编译器会检查类型的一致性。

赋值语句

赋值语句将(由一个表达式定义的)某个数据类型的值和一个变量关联起来。

条件语句
循环语句
for (<initialize>; <boolean expression>; <increment>) 
{ 
  <block statements> 
}

等价于:

<initialize>
while ( <boolean expression>)
{
  <block statements>
  <increment>
}

单语句代码段:如果条件或循环的代码段只有一条语句,代码段的花括号可以省略。

调用和返回语句
break 和 continue 语句

数组

数组能够顺序存储相同类型的多个数据。除了存储数据,我们也希望能够访问数据。访问数据的某个元素的方法是将其编号然后索引

创建并初始化数组

创建数组的三步:

使用数组

典型的数组处理代码:

  1. 找出数组中最大的元素:
double max = a[0];
for (int i = 0; i < a.length; i++)
  if (a[i] > a[0]) max = a[i];
  1. 计算数组元素的平均值
int N = a.length;
double sum = 0.0;
for (int i = 0; i < N; i++)
  sum += a[i];
double average = sum / N;
  1. 复制数组
int N = a.length;
double[] b = new double[N];
for (int i = 0; i < N; i++)
  b[i] = a[i];
  1. 颠倒数组元素的顺序
int N = a.length
for (int i = 0; i < N; i++)
{
  double temp = a[i];
  a[i] = a[N-1-i];
  a[N-1-i] = temp;
}
  1. 矩阵相乘a[][]*b[][]=c[][]
int N = a.length;
double[][] c = new c[N][N];
for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
  {
    for (int k = 0; k < N; k++)
      c[i][j] = a[i][k] * b[k][j];
  }
起别名

数组名表示的是整个数组,如果我们将一个数组变量赋予另一个变量,那么两个变量将会指向同一个数组。
例如:

int[] a = new int[N];
a[i] = 1234;
int[] b = new a;
b[i] = 5678; // a[i] 的值也会变成 5678

这种情况叫做起别名。如果你想将数组复制一份,应该声明、创建并初始化一个新数组,然后将原数组中的元素挨个赋值给新数组。

二维数组

静态方法

静态方法封装了由一系列语句所描述的运算。方法需要参数(某种数据类型的值)并根据参数计算出某种数据类型的返回值(例如数学函数的结果)或者产生某种副作用(例如打印一个值)。静态方法与实例方法的区别是静态方法有static修饰符。

静态方法解析

典型的静态方法的实现:

  1. 计算一个整数的的绝对值:
public static int abs()
{
  if (x < 0) return -x;
  else return x;
}
  1. 计算一个浮点数的绝对值
public static double abs(double x)
{
  if (x < 0.0) return -x;
  else return x;
}
  1. 判断一个数是否是素数
public static boolean isPrime(int N)
{
  if (N < 2) return false;
  for (i = 0; i*i <= N; i++)
    if (N % i == 0) return false;
  return true;
}
  1. 计算平方根(牛顿迭代法)
public static double sqrt(double c)
{
  if (c < 0) return Double.NaN;
  double err = 1e-15;
  double t = c;
  while (Math.abs(t - c/t) > err * t)
    t = (c/t + t) / 2.0;
  return t;
}
  1. 计算直角三角形的斜边
public static double hypothenuse(double a, double b)
{
  return Math.sqrt(a*a + b*b);
}
  1. 计算调和级数
public static double H(int N)
{
  double sum = 0.0;
  for (int i = 1; i <= N; i++)
    sum += 1.0 / i;
  return sum;
}
方法的性质
递归

递归就是方法调用自己。编写递归代码最重要有以下三点:

  1. 递归总有一个最简单的情况 —— 方法的第一条语句总是包含return的条件语句。
  2. 递归调用总是去尝试解决一个规模更小的子问题,这样递归才能手链到最简单的情况。在下面的代码中,第四个参数和第三个参数的差值一直在缩小。
  3. 递归调用的父问题和尝试解决的子问题之间不应该有交集。在下面的代码中,两个子问题各自操作的数组部分是不同的。

二分查找的递归实现:

public static int rank(int key, int[] a)
{
  rank(key, a, 0, a.length -1)
}
public static int rank(int key, int[] a, int lo, int hi)
{
  if (lo > hi) return -1;
  int mid = lo + (hi - lo) / 2;
  if (key < a[mid]) return rank(key, a, lo, mid - 1);
  else if (key > a[mid]) return rank(key, a, mid + 1,hi);
  else return mid;
}

违背以上三条的任意一条都可能得到错误的结果或是低效的代码。而坚持这些原则则能写出清晰、正确容易评估性能的程序。

基础编程模型

静态方法库 是定义一个 Java 类中的一组静态方法。类的声明是public class加上类名,以及用花括号包含的静态方法。存放类的文件的文件名和类名相同,扩展名是.java。Java开发的基本模式是编写一个静态方法库(包含一个main()方法)来完成一个任务。控制台输入 java 库名 参数就能调用库类中的main()方法,其参数为由输入的字符串组成的一个数组。

模块化编程

基础编程模型的最重要之处在于通过静态方法实现了模块化编程。我们可以构造许多个静态方法库,一个库中的静态方法也能够调用另一个库中定义的静态方法。
好处:

单元测试

Java编程的最佳实践之一就是每个静态方法库中都包含一个main()函数来测试库中所有的方法。(有些编程语言不支持多个main()方法,因此不支持这种方式)。
main() 方法可以用来:

外部库

API

模块化编程的重要组成部分就是记录库方法的用法并供他人参考的文档。我们会统一的使用应用程序编程接口(API)的方式列出书中使用的每个库方法名称、签名和简短的描述。

java.lang 中 Math 库 的 API
Java的数学函数库的API
Java 库

Arrays 库不在 java.lang 中,因此我们需要用 import 语句导入后才能使用它。


Java 的 Arrays 库节选(java.util.Arrays)
书中的标准库

《算法(第四版)》一书中提供了以下库来提供一些使用的功能,大多数用于处理输入输出,还有以下两个库用来测试和分析我们的实现:

  1. StdRandom 库扩展了Math.random()的方法。


    随机数静态方法库的 API

    StdRandom 的 initialize() 方法为随机数生成器提供种子,这样我们,这样我们就可以重复和随机数有关的实验。

  2. 各种统计计算的库。


    数据分析的静态方法库的 API

设计良好的方法库的好处:

StdRandom库的静态方法的实现:

  1. 随机返回[a,b)之间的一个double值:
public static double uniform(double a, double b)
{
  return a + StdRandom.random() * (b-a);
}
  1. 随机返回[0, N)之间的一个int值:
public static double uniform(int N)
{
  return (int) (StdRandom.random() * N);
}
  1. 随机返回[lo, hi) 之间的一个int值:
public static int uniform(lo, hi)
{
  return lo + StdRandom.unifom(hi - lo);
}
  1. 根据离散概率随机返回的int值(出现 i 的概率为a[i])
public static int discrete(double[] a)
{
  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;
}
  1. 将 double 数组中的元素打乱
public static void shuffle(double[] a)
{
  int N = a.length;
  for (int i = 0; i < N; i++)
  {
    int r = i + StdRandom.uniform(N-i);
    double temp = a[i];
    a[i] = a[r];
    a[r] = temp;
  }
}
自己编写的库

我们应该将自己编写的每一个程序都当做一个日后可以重用的库。

字符串

一个 String 类型的字面量包括一对双引号和其中的字符。String类型是 Java 的一个数据类型,但并不是原始数据类型。

字符串拼接

使用 + 运算符进行拼接。

类型转换

字符串的两个主要用途是将用户从键盘输入的内容转换成相应数据类型的值以及将各种数据类型的值转化成能够在屏幕上显示的内容。Java 的 String 类型为这些操作内置了相应的方法。


String 值和数字之间相互转换的 API
自动转换

如果加号的一个参数是字符串,那么Java会自动将其他类型都转换为字符串。

命令行参数

在 Java 中字符串的一个重要用途就是使程序能够接收从命令行传递来的信息。当输入在控制台命令java 库名 字符串1 字符串2 ...时,Java系统会调用库类中的main()方法将字符串1,字符串2等一系列字符串变成一个数组作为参数传递给main方法。我们在代码中常见的用法是当命令行参数表示的是数字的时候,用parseInt()和paseDouble()方法将其分别转换为整数和浮点数。
字符串的用法是现代程序的重要部分。

输入输出

命令和参数

Java类中都会包含一个静态方法 main(),它有一个String数组类型的参数 args[]。这个数组的内容就是我们输入的命令行参数,操作系统会将它传递给 Java。Java 和操作系统默认参数为字符串。如果我们需要某个参数是数字,我们会使用类似 Interger.parseInt() 的方法将其转换为适当的数据类型的值。


操作系统常用命令
标准输出

《算法(第四版)》一书中将标准输入输出封装为StdIn和StdOut库。


StdOut库

我们来看看这个StdOut标准输出库的代码实现:

package edu.princeton.cs.algs4;

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.Locale;

public final class StdOut {

    // force Unicode UTF-8 encoding; otherwise it's system dependent
    private static final String CHARSET_NAME = "UTF-8";

    // assume language = English, country = US for consistency with StdIn
    private static final Locale LOCALE = Locale.US;

    private static PrintWriter out;

    // this is called before invoking any methods
    static {
        try {
            out = new PrintWriter(new OutputStreamWriter(System.out, CHARSET_NAME), true);
        }
        catch (UnsupportedEncodingException e) {
            System.out.println(e);
        }
    }

    // don't instantiate
    private StdOut() { }

    public static void println() {
        out.println();
    }

    public static void println(Object x) {
        out.println(x);
    }

    public static void println(boolean x) {
        out.println(x);
    }

    public static void println(char x) {
        out.println(x);
    }

    public static void println(double x) {
        out.println(x);
    }

    public static void println(float x) {
        out.println(x);
    }

    public static void println(int x) {
        out.println(x);
    }

    public static void println(long x) {
        out.println(x);
    }

    public static void println(short x) {
        out.println(x);
    }

    public static void println(byte x) {
        out.println(x);
    }

    public static void print() {
        out.flush();
    }

    public static void print(Object x) {
        out.print(x);
        out.flush();
    }

    public static void print(boolean x) {
        out.print(x);
        out.flush();
    }

    public static void print(char x) {
        out.print(x);
        out.flush();
    }

    public static void print(double x) {
        out.print(x);
        out.flush();
    }

    public static void print(float x) {
        out.print(x);
        out.flush();
    }

    public static void print(int x) {
        out.print(x);
        out.flush();
    }

    public static void print(long x) {
        out.print(x);
        out.flush();
    }

    public static void print(short x) {
        out.print(x);
        out.flush();
    }

    public static void print(byte x) {
        out.print(x);
        out.flush();
    }

    public static void printf(String format, Object... args) {
        out.printf(LOCALE, format, args);
        out.flush();
    }

    public static void printf(Locale locale, String format, Object... args) {
        out.printf(locale, format, args);
        out.flush();
    }

    public static void main(String[] args) {
        // write to stdout
        StdOut.println("Test");
        StdOut.println(17);
        StdOut.println(true);
        StdOut.printf("%.6f\n", 1.0/7.0);
    }

}

在冯诺依曼体系结构中,计算机由控制器、运算器、存储器、输入设备、输出设备五部分组成。其中运算器、控制器(还有一些寄存器)是CPU的组成成分。存储器则分为内存储器(内存)和外存储器(外存)。输入输出设备主要用来完成系统的I/O操作。I/O操作主要对硬盘的数据进行读和取。CPU不能直接访问外存(硬盘),而需要借助内存来完成对硬盘数据的读/取操作。由于CPU的运算速度远远大于I/O操作,因此当一个进程需要产生许多I/O操作时,会耗费许多系统资源,同时也不利于进程之间的资源竞争,导致系统资源利用率下降。

JAVA中的输入/输出流在默认的情况下是不被缓存区缓存的,因此,每发生一次read()方法和write()方法都需要请求操作系统再分发/接收一个字节,这样程序的运行效率必然会降低,相比之下,请求一个数据块并将其置于缓冲区中会显得更加高效。我们考虑可以将硬盘中的数据事先添加到预定义范围(大小合适)的缓冲池中来预存数据,待CPU产生I/O操作时,可以从这个缓存池中来读取数据,这样便减少了CPU的I/O的次数,提高了程序的运行效率。事实上JAVA也正是采取这种方式,通过为基本流添加处理流(缓冲机制)来减少I/O操作的次数。

read()方法和write()方法是线程阻塞的,也就是说,当某个线程试图向另一端网络节点读取或写入数据时,有可能会发生网络连接异常或者是服务器短期没有响应,同样的,在无数据状态进行读取,数据已满进行写操作时,同样会发生阻塞,这时,其他线程抢占资源后继续执行。如果出现此现状,读取到缓冲池中的数据不能够及时的发送到另一端的网络节点,需要该线程再次竞争到CPU资源才可正常发送。

还有一种情况,当我们将数据预存到缓冲池中时,当数据的长度满足缓冲池中的大小后,才会将缓冲池中的数据成块的发送,若数据的长度不满足缓冲池中的大小,最终导致这部分的数据停留在缓冲池无法发送。

这时,就需要我们在write()方法后,手动调用flush()方法,强制刷出缓冲池中的数据(即使数据长度不满足缓冲池的大小)从而保证数据的正常发送。当然,当我们调用流的close()方法后,系统也会自动将缓冲区的数据刷出,同时可保证流的物理资源被回收。


OutputStream抽象基类中的方法
上一篇 下一篇

猜你喜欢

热点阅读