在Java中,EnumSet使用long
(RegularEnumSet
)或long[]
(JumboEnumSet
)将其包含的项目存储在位掩码/位向量中。我现在遇到了一个用例,其中我有数千个域对象(我们称它们为 Node
),每个对象都将显示枚举的所有项目(我们称之为Flag
),顺序会因对象而异。
目前,我将订单存储为番石榴ImmutableSet
,因为这可以保证保留广告订单。但是,我使用此页面上解释的方法来比较EnumSet<Flag>
,ImmutableSet<Flag>
和Flag[]
中的内存使用情况。以下是 a) 标志有 64 个枚举项和 b) 所有三个变体都包含所有 64 个项时的结果:
枚举集:32 字节
不可变集:832 字节
数组:272 字节
所以我的问题是:有没有一种聪明的方法将枚举排序打包成一个数值,以获得小于数组的内存占用?如果它有所作为:在我的用例中,我会假设排序始终包含所有 Enum 项目。
澄清一下:我的枚举比这小得多,到目前为止我没有任何记忆问题,这种情况也不太可能给我带来记忆问题。只是这种低效率让我烦恼,即使在这个微观层面上也是如此。
更新:
根据各种答案和评论的建议,我想出了这个使用字节数组的数据结构。警告:它不实现 Set 接口(不检查唯一值),并且不会扩展到超出字节可以容纳的大枚举。此外,复杂性非常糟糕,因为 Enum.values() 必须反复查询(有关此问题的讨论,请参阅此处),但这里是:
public class EnumOrdering<E extends Enum<E>> implements Iterable<E> {
private final Class<E> type;
private final byte[] order;
public EnumOrdering(final Class<E> type, final Collection<E> order) {
this.type = type;
this.order = new byte[order.size()];
int offset = 0;
for (final E item : order) {
this.order[offset++] = (byte) item.ordinal();
}
}
@Override
public Iterator<E> iterator() {
return new AbstractIterator<E>() {
private int offset = -1;
private final E[] enumConstants = type.getEnumConstants();
@Override
protected E computeNext() {
if (offset < order.length - 1) {
return enumConstants[order[++offset]];
}
return endOfData();
}
};
}
}
内存占用量为:
枚举排序:104
到目前为止,这是一个相当不错的结果,感谢bestsss和JB Nizet!
更新:我已经将代码更改为仅实现可迭代,因为其他任何事情都需要对等号/哈希码/包含等进行合理的实现。
有没有一种聪明的方法将枚举排序打包成一个数值
是的,您可以将排序表示为数值,尽管要使用它,您需要转换回字节/整数数组。既然有64个!64 个值和 64 个值的可能排序!大于Long.MAX_VALUE
,您需要将数字存储在BigInteger
中。我想这将是存储排序的最节省内存的方式,尽管您在内存中获得的内容由于必须将数字转换为数组而及时丢失。
有关在数字/数组表示之间转换的算法,请参阅此问题。
这是上述的替代方案,不知道它是否像那个一样有效,您必须将代码从 int
转换为基于 BigInteger
,但它应该足以给你这个想法:
/**
* Returns ith permutation of the n numbers [from, ..., to]
* (Note that n == to - from + 1).
* permutations are numbered from 0 to n!-1, if i is outside this
* range it is treated as i%n!
* @param i
* @param from
* @param n
* @return
*/
public static int[] perm(long i, int from, int to)
{
// method specification numbers permutations from 0 to n!-1.
// If you wanted them numbered from 1 to n!, uncomment this line.
// i -= 1;
int n = to - from + 1;
int[] initArr = new int[n]; // numbers [from, ..., to]
int[] finalArr = new int[n]; // permutation of numbers [from, ..., to]
// populate initial array
for (int k=0; k<n; k++)
initArr[k] = k+from;
// compute return array, element by element
for (int k=0; k<n; k++) {
int index = (int) ((i%factorial(n-k)) / factorial(n-k-1));
// find the index_th element from the initial array, and
// "remove" it by setting its value to -1
int m = convertIndex(initArr, index);
finalArr[k] = initArr[m];
initArr[m] = -1;
}
return finalArr;
}
/**
* Helper method used by perm.
* Find the index of the index_th element of arr, when values equal to -1 are skipped.
* e.g. if arr = [20, 18, -1, 19], then convertIndex(arr, 2) returns 3.
*/
private static int convertIndex(int[] arr, int index)
{
int m=-1;
while (index>=0) {
m++;
if (arr[m] != -1)
index--;
}
return m;
}
基本上,你从自然排序的 init 数组开始,然后遍历最终数组,每次计算接下来应该放置哪些剩余元素。此版本通过将值设置为 -1 来"删除"init 数组中的元素。使用List
或LinkedList
可能会更直观,我刚刚从我周围的一些旧代码中粘贴了它。
使用上述方法并以此作为main
:
public static void main(String[] args) {
int n = (int) factorial(4);
for ( int i = 0; i < n; i++ ) {
System.out.format( "%d: %sn", i, Arrays.toString( perm(i, 1, 4 ) ) );
}
}
您将获得以下输出:
0: [1, 2, 3, 4]
1: [1, 2, 4, 3]
2: [1, 3, 2, 4]
3: [1, 3, 4, 2]
4: [1, 4, 2, 3]
5: [1, 4, 3, 2]
6: [2, 1, 3, 4]
7: [2, 1, 4, 3]
8: [2, 3, 1, 4]
9: [2, 3, 4, 1]
10: [2, 4, 1, 3]
11: [2, 4, 3, 1]
12: [3, 1, 2, 4]
13: [3, 1, 4, 2]
14: [3, 2, 1, 4]
15: [3, 2, 4, 1]
16: [3, 4, 1, 2]
17: [3, 4, 2, 1]
18: [4, 1, 2, 3]
19: [4, 1, 3, 2]
20: [4, 2, 1, 3]
21: [4, 2, 3, 1]
22: [4, 3, 1, 2]
23: [4, 3, 2, 1]
这是 ideone 上的可执行版本。
从BigInteger.bitLength()
来看,应该可以在不超过 37 个字节(加上使用 BigInteger
实例的开销)中存储 64 个元素的顺序。我不知道这是否值得麻烦,但它是一个很好的练习!
如果您有 64 个枚举值,则可以使用字节数组,其中每个字节将包含其中一个枚举项的序号。对于 3 个 64 字节的数组,这将需要 3 * (64 + 16) = 240
个字节(16 字节是字节数组的成本,无论其长度如何)。
这仍然浪费空间,因为每个字节能够存储 8 位,但您只需要 6 位即可存储从 0 到 63 的数字。因此,您可以应用一种聪明的打包算法,该算法将使用 3 个字节(24 位)来存储 4 个枚举序数。这将导致 3 * (64 * 3 / 4 + 16) = 192
字节。
我不喜欢字节操作,所以我将把实现留给你一个练习。