算法(4th ed)(187):基础——算法分析 6.9

阅读数:6 2019 年 11 月 9 日 15:38

算法(4th ed)(187):基础——算法分析 6.9

(内存)

和运行时间一样,一个程序对内存的使用也和物理世界直接相关:计算机中的电路很大一部分的作用就是帮助程序保存一些值并在稍后取出它们。在任意时刻需要保存的值越多,需要的电路也就越多。你可能知道计算机能够使用的内存上限(知道这一点的人应该比知道运行时间限制的人要多)因为你很可能已经在内存上花了不少额外的支出。

计算机上的 Java 对内存的使用经过了精心的设计(程序的每个值在每次运行时所需的内存量都是一样的),但实现了 Java 的设备非常多,而内存的使用是和实现相关的。简单起见,我们用典型这个词暗示和机器相关的值。

Java 最重要的特性之一就是它的内存分配系统。它的任务是把你从对内存的操作之中解脱出来。显然,你肯定已经知道应该在适当的时候利用这个功能,但是你也应该(至少是大概)知道程序对内存的需求在何时会成为解决问题的障碍。

分析内存的使用比分析程序所需的运行时间要简单得多,主要原因是它所涉及的程序语句较少(只有声明语句)且在分析中我们会将复杂的对象简化为原始数据类型,而原始数据类型的内存使用是预先定义好的,而且非常容易理解:只需将变量的数量和它们的类型所对应的字节数分别相乘并汇总即可。例如,因为 Java 的int 数据类型是 -2 147 483 648 到 2 147 483 647 之间的整数值的集合,即总数为 232 个不同的值,典型的 Java 实现使用 32 位来表示 int 值。其他原始数据类型的内存使用也是基于类似的考虑:典型的 Java 实现使用 8 位表示字节,用 2 字节(16 位)表示一个char 值,用 4 字节(32 位)表示一个 int 值,用 8 字节(64 位)表示一个 double 或者 long 值,用 1 字节表示一个 boolean 值(因为计算机访问内存的方式都是一次 1 字节),见表 1.4.10。根据可用内存的总量就能够计算出保存这些值的极限数量。例如,如果计算机有 1 GB 内存(10 亿字节),那么同一时间最多能在内存中保存 2.56 亿万个 int 值或是 1.28 亿万个 double 值。

表 1.4.10 原始数据类型的常见内存、需求

类型 字节
boolean 1
byte 1
char 2
int 4
float 4
long 8
double 8

从另一方面来说,对内存使用的分析和硬件以及 Java 的不同实现中的各种差异有关,因此我们举出的这个特定的例子并不是一成不变的,你应该以它为参考来学习在条件允许的情况下如何分析内存的使用。例如,许多数据结果都涉及对机器地址的表示,而在各种计算机中一个机器地址所需的内存又各有不同。为了保持一致,我们假设表示机器地址需要 8 字节,这是现在广泛使用的 64 位构架中的典型表示方式,许多老式的 32 位构架只使用 4 字节表示机器地址。

评论

发布