本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• Java中int、double、等基本类型的内存占用
• Java中对象的内存占用
• Java中数组的内存占用
• Java中字符串的内存占用

题目

1.4.13 根据正文中的假设分别给出表示以下数据类型的一个对象所需的内存量

1.4.13 Using the assumptions developed in the text, give the amount of memory needed to represent an object of each of the following types:

a.Accumulator
b.Transaction
c.FixedCapacityStackOfStrings with capacity C and N entries 
d.Point2D
e.Interval1D
f. Interval2D 
g. Double

分析

书中关于基本类型的内存占用是这么说的：

For example, since the Java int data type is the set of integer values between 2,147,483,648 and 2,147,483,647, a grand total of 232 different values, typical Java implementations use 32 bits
to represent int values. Similar considerations hold for other primitive types: typical Java implementations use 8-bit bytes, representing each char value with 2 bytes (16 bits), each int value with 4 bytes (32 bits), each double and each long value with 8 bytes (64 bits), and each boolean value with 1 byte (since computers typically access memory one byte at a time).

以上是讲基本类型的内存占用,下面讲地址引用的内存占用(就是指针对象)

For consistency, we assume that 8 bytes are needed to represent addresses, as is typical for 64-bit architectures that are now widely used, recognizing that many older machines use a 32-bit architecture that would involve just 4 bytes per machine address.

接下来是对象的内存占用

To determine the memory usage of an object, we add the amount of memory used by each instance variable to the overhead associated with each object, typically 16 bytes. The overhead includes a reference to the object’s class, garbage collection information, and synchronization information. Moreover, the memory usage is typically padded to be a multiple of 8 bytes (machine words, on a 64-bit machine). For example, an Integer object uses 24 bytes (16 bytes of overhead, 4 bytes for its int instance variable, and 4 bytes of padding).

了解了内存大小计算的原则，下面我们开始一一分析。

这几个类分散在书中的各个地方，让我们先把他们一个一个找出来
a.Accumulator
第一次出现是在92页（中译版是1.2.4.3），他的描述是这样的：

Accumulator. The accumulator API shown on the facing page defines an abstract data type that provides to clients the ability to maintain a running average of data values. For example, we use this data type frequently in this book to process experimental results (see Section 1.4). The implementation is straightforward: it maintains a int instance variable counts the number of data values seen so far and a double instance variable that keeps track of the sum of the values seen so far; to compute the average it divides the sum by the count. Note that the implementation does not save the data values—it could be used for a huge number of them (even on a device that is not capable of holding that many), or a huge number of accumulators could be used on a big system. This performance characteristic is subtle and might be specified in the API, because an implementation that does save the values might cause an application to run out of memory.

public class Accumulator {
    private double total;
    private int N;

    public void addDataValue(double val) {
        N++;
        total += val;
    }

    public double mean() {
        return total / N;
    }

    public String toString() {
        return "Mean (" + N + " values): " + String.format("%7.5f", mean());
    }
}

我们看到首先这个对象Accumulator 要占用16个字节，然后是实例变量total，8个字节，然后N是4个字节，所以一共是16+8+4 = 28，又因为内存的使用一般会被填充为8的倍数（64位计算机中的机器字）。所以需要加4个字节的填充字节，因此是32个字节。

b.Transaction
这个书中只给出了API列表，没有给出具体实现：

好在习题1.2.13需要我们给出实现，我们也在文章算法练习(25):Transaction类设计(1.2.13-1.2.14)中给出了分析。代码如下：

public class Transaction {
    private Date when;
    private String who;
    private double amount;
}

Transaction 类中有Date类，这里我们不用我们写的Date类，而是API中的Date类，有三个属性。

public class Date {
    private final int year;
    private final int month;
    private final int day;
}

Date本身的16字节的开销，再加上有3个int类型，大小是3*4 = 12个字节，再加上4个填充字节，所以Date的对象会占用32个字节。然后我们看String对象的内存占用：

We account for memory in Java’s String objects in the same way as for any other object, except that aliasing is common for strings. The standard String implementation has four instance variables: a reference to a character array (8 bytes) and three int values (4 bytes each). The first int value is an offset into the character ar- ray; the second is a count (the string length). In terms of the instance variable names in the drawing on the facing page, the string that is represented consists of the characters value[offset] through value[offset + count - 1].The third int value in String objects is a hash code that saves recomputation in certain circumstances that need not concern us now. Therefore, each String object uses a total of 40 bytes (16 bytes for object overhead plus 4 bytes for each of the three int instance variables plus 8 bytes for the array reference plus 4 bytes of padding).

由上可知，String对象占用40个字节。综上所述，Transaction占本身的16字节+32字节的Date+40个字节的String+8字节的Double = 96个字节，这里不需要补充字节，因为96是8的倍数。

c.FixedCapacityStackOfStrings
FixedCapacityStackOfStrings是一个我们非常熟悉的类了。在书中133页中有提起，其API表格及实现为：

public class FixedCapacityStackOfStrings
{
   private String[] a; // stack entries
   private int N;      // size
   public FixedCapacityStackOfStrings(int cap)
   {  a = new String[cap];  }
}

我们在习题1.3.1中也有涉及，对应的文章是算法练习(26):Stack概念(1.3.1-1.3.2)大家有兴趣可以温习一下。

d.Point2D
第一次出现在77页，其API为：

public class Point2D {
    public double x;
    public double y;
}

e.Interval1D
第一次出现在77页，其API为：

public class Interval1D {
    public double lo;
    public double hi;
}

f. Interval2D
第一次出现在77页，其API为：

public class Interval2D {
    public Interval1D x;
    public Interval1D y;    
}

g. Double
Double类型就是基础类型Double类型

答案

a.Accumulator //32字节
b.Transaction //96字节
c.FixedCapacityStackOfStrings with capacity C and N entries //
d.Point2D //
e.Interval1D //
f. Interval2D //
g. Double //

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。