如何在以下代码中减少内存使用?

Question

import java.util.List; 
class Solution {
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
List<Boolean> result = new ArrayList<>();
int highest = 1;
for(int i = 0 ; i < candies.length ; i++){
if(candies[i] > highest)
highest = candies[i];
}
for(int i = 0 ; i < candies.length ; i++){
result.add((candies[i] + extraCandies) >= highest); 
}

return result;
}
}

我必须试着解决孩子们有最高糖果的问题。上面的代码显示了38.9 MB的内存使用。我如何进一步减少它。请帮助我了解这个过程是如何工作的。

Answer 1

您的代码已经足够紧凑了。你能做的只有两件事:

1. 使用BitSet
2. 使用Array代替List，因为你知道数组的大小。

解释:

1. booleanvsBitSet

---

boolean

为了存储和操作位数组，有人可能会认为我们应该使用boolean[]作为数据结构。乍一看，这似乎是一个合理的建议。

为了使问题更具体，让我们看看包含1024个元素的布尔[]占用了多少空间:

boolean[] bits = new boolean[1024];
System.out.println(ClassLayout.parseInstance(bits).toPrintable());

理想情况下，我们期望这个数组占用1024位内存。然而，Java对象布局(JOL)揭示了一个完全不同的现实:

[Z object internals:
OFFSET  SIZE      TYPE DESCRIPTION            VALUE
0     4           (object header)        01 00 00 00 (00000001 00000000 00000000 00000000) (1)
4     4           (object header)        00 00 00 00 (00000000 00000000 00000000 00000000) (0)
8     4           (object header)        7b 12 07 00 (01111011 00010010 00000111 00000000) (463483)
12     4           (object header)        00 04 00 00 (00000000 00000100 00000000 00000000) (1024)
16  1024   boolean [Z.                    N/A
Instance size: 1040 bytes

如果忽略对象头的开销，则数组元素消耗1024字节，而不是预期的1024位。这比我们预期的内存多了700%。

BitSet让我们将1024位的BitSet实例的内存占用与前面看到的布尔值[]进行比较:

BitSet bitSet = new BitSet(1024);
System.out.println(GraphLayout.parseInstance(bitSet).toPrintable());

这将打印BitSet实例的浅层大小及其内部数组的大小:

java.util.BitSet@75412c2fd object externals:
ADDRESS       SIZE TYPE             PATH         VALUE
70f97d208         24 java.util.BitSet              (object)
70f97d220        144 [J               .words       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

如上所示，在内部使用具有16个元素(16 * 64位= 1024位)的long[]。无论如何，这个实例总共使用了168字节，而布尔值[]使用了1024字节。

详情请点击这里。

2. ArrayListvsArray

---

数组内存在创建时分配。初始化数组时，它根据数组的大小和类型分配内存。它初始化所有的元素，对引用类型使用空值，对基本类型使用默认值。

ArrayList在增长时改变内存分配。当我们在初始化ArrayList时指定容量时，它会分配enough memory来存储该容量以内的对象。逻辑大小保持为0。当需要扩展容量时，将创建一个更大的新数组，并将值复制到该数组中。

所以，ArrayList(List)需要比简单数组更多的内存消耗。

详情请点击这里。

---

修改后的内存优化版本:

public BitSet kidsWithCandies(int[] candies, int extraCandies) {
BitSet bitSet = new BitSet(candies.length);
int highest = Integer.MIN_VALUE;

for(int i = 0 ; i < candies.length ; i++){
if(candies[i] > highest)
highest = candies[i];
}

for(int i = 0 ; i < candies.length ; i++){
bitSet.set(i,(candies[i] + extraCandies) >= highest );
}

return bitSet;
}