时间戳

首页 > 解决方案 > 如何减少以下代码中的内存使用量？

java - 如何减少以下代码中的内存使用量？

问题描述

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 的内存使用情况。我怎样才能进一步减少它。请帮助我了解这个过程是如何工作的。

标签： java

解决方案

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

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

解释：

  1. boolean对比BitSet

boolean

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

为了使事情更具体，让我们看看具有 1024 个元素的 boolean[] 消耗了多少空间：

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 实例的内存占用与我们之前看到的 boolean[] 进行比较：

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 个字节，而 boolean[] 使用了 1024 个字节。

更多详情请点击这里。

  1. ArrayList对比Array

数组内存在创建时分配。当我们初始化一个数组时，它会根据数组的大小和类型来分配内存。它使用引用类型的空值和原始类型的默认值初始化所有元素。

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;
}

推荐阅读