算法(4th ed)(192):基础——算法分析 6.9.5

阅读数:3 2019 年 11 月 9 日 15:44

算法(4th ed)(192):基础——算法分析 6.9.5

(内存:字符串的值和子字符串)

一个长度为 $N$ 的String 对象一般需要使用 40 字节(String 对象本身)加上($24+2N$)字节(字符数组),总共($64+2N$)字节。但字符串处理经常会和子字符串打交道,所以 Java 对字符串的表示希望能够避免复制字符串中的字符。当你调用 substring() 方法时,就创建了一个新的 String 对象(40 字节),但它仍然重用了相同的 value[] 数组,因此该字符串的子字符串只会使用 40 字节的内存。含有原始字符串的字符数组的别名存在于子字符串中,子字符串对象的偏移量和长度域标记了子字符串的位置。换句话说,一个子字符串所需的额外内存是一个常数,构造一个子字符串所需的时间也是常数,即使字符串和子字符串的长度极大也是这样。某些简陋的字符串表示方法在创建子字符串时需要复制其中的字符,这将需要线性的时间和空间。确保子字符串的创建所需的空间(以及时间)和其长度无关是许多基础字符串处理算法的效率的关键所在。字符串的值与子字符串示例如图 1.4.10 所示。

算法(4th ed)(192):基础——算法分析 6.9.5

图 1.4.10 一个 String 对象和一个子字符串

这些基础机制能够有效帮助我们估计大量程序对内存的使用情况,但许多复杂的因素仍然会使这个任务变得更加困难。我们已经提到了别名可能产生的潜在影响。另外,当涉及函数调用时,内存的消耗就变成了一个复杂的动态过程,因为 Java 系统的内存分配机制扮演一个重要的角色,而这套机制又和 Java 的实现有关。例如,当你的程序调用一个方法时,系统会从内存中的一个特定区域为方法分配所需要的内存(用于保存局部变量),这个区域叫做(Java 系统的下压栈)。当方法返回时,它所占用的内存也被返回给了系统栈。因此,在递归程序中创建数组或是其他大型对象是很危险的,因为这意味着每一次递归调用都会使用大量的内存。当通过 new 创建对象时,系统会从内存的另一块特定区域为该对象分配所需的内存(这里的和我们将在 2.4 节学习的二叉堆数据结构不同)。而且,你要记住所有对象都会一直存在,直到对它的引用消失为止。此时系统的垃圾回收进程会将它所占用的内存收回到堆中。这种动态过程使准确估计一个程序的内存使用变得极为困难。

评论

发布