在Java中存储枚举的顺序 [英] Store an ordering of Enums in Java
问题描述
long （ RegularEnumSet ）将其包含的项目存储在位掩码/位向量中）或 long [] （ JumboEnumSet ）。我现在遇到一个用例，我有几千个域对象（让我们称之为 Node ），每个都将显示一个枚举的所有项目（让我们称之为标志）按照每个Object将有所不同的顺序。 目前我将订单存储为Guava ImmutableSet ，因为这保证了保留插入顺序。但是，我已经使用本页中介绍的方法比较 EnumSet< Flag> 中的内存使用情况， ImmutableSet< Flag> 和标志[] 。以下是a）Flag有64个枚举项目的结果，b）所有三个变体都包含所有64个项目：
EnumSet：32 bytes < br>
ImmutableSet：832 bytes
数组：272字节
所以我的问题是：是有一个聪明的方法来将枚举排序打包成一个数值，以获得比数组更小的内存占用空间？如果它有所不同：在我的用例中，我会认为排序总是包含所有枚举项。
要澄清：我的枚举比这个小得多，现在不存在任何记忆问题，也不可能这种情况会给我记忆力的问题。这只是这个无效率的错误，甚至在这个微观层面上。
更新：
各种答案和评论我想出了使用字节数组的数据结构。注意事项：它不实现Set接口（不检查唯一值），它不会扩展到超过一个字节可以容纳的大枚举。另外，复杂性是非常可怕的，因为必须重复地查询Enum.values（）（请参阅这里讨论这个问题），但是这里：
public class EnumOrdering< E extends Enum< E>>实现Iterable< E> {
private final Class< E>类型;
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（）;
}
};
}
}
内存占用是：
EnumOrdering：104
到目前为止这是一个非常好的结果，感谢bestsss和JB Nizet！
更新：我已经将代码更改为仅实现Iterable，因为任何其他操作都需要对于/ hashCode / contains等的明智实现。 / p>
有一个聪明的方法来将枚举排序打包成一个数值
是的，您可以将排序表示为数值，尽管使用它需要转换为byte / int数组。因为有64！可能排序64个值，64！大于 Long.MAX_VALUE ，则需要将号码存储在 BigInteger 中。我想这将是最有效率的存储顺序的方法，尽管您在内存中获得的收益是由于必须将数字转换为数组而导致的。
对于在数字/数组表示之间进行转换的算法，请参阅此问题。
这是上述的替代方法，不知道它是否与那个效率一样高，您必须将代码从 int 到 BigInteger ，但这应该足以让您有这样的想法：
/ **
*返回n个数字的排列[从，...，到]
*（注意n == to - from + 1）。
*排列从0到n！-1编号，如果我在
*范围之外，则被视为i％n！
* @param i
* @param from
* @param n
* @return
* /
public static int [] perm（long i ，int from，int to）
{
//方法规范号从0到n！-1的排列。
//如果你希望他们从1到n！编号，取消注释这一行。
// i - = 1;
int n = to - from + 1;
int [] initArr = new int [n]; // number [from，...，to]
int [] finalArr = new int [n]; //数组的排列[从，...，到]
//填充初始数组
（int k = 0; k
//计算返回数组，元素元素
（int k = 0; k
//从初始数组中找到index_th元素，
//将其值设置为-1
int m = convertIndex（initArr，index） ;
finalArr [k] = initArr [m];
initArr [m] = -1;
}
return finalArr;
}
/ **
*由perm使用的助手方法
*查找arr的index_th元素的索引，当跳过等于-1的值时。
*例如如果arr = [20，18，-1,19]，则convertIndex（arr，2）返回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数组删除元素。使用列表或 LinkedList 可能会更直观，我刚从一些旧代码粘贴已经躺在身边。
使用上述方法并将其作为 main ：
public static void main（String [] args）{
int n =（int）factorial（4）; （int i = 0; i
，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]
通过 BigInteger.bitLength（）判断，应该可以存储不超过37个字节的64个元素的排序（加上使用 BigInteger 实例）。我不知道这是否值得一试，但是这样做很好！
In java, an EnumSet stores the items it contains in a bitmask / bit vector using a long (RegularEnumSet) or long[] (JumboEnumSet). I have now come across a use case where I have many thousand domain Objects (let's call them Node), each of which will show all items of an enum (let's call that Flag) in an order that will vary per Object.
Currently I am storing the Order as Guava ImmutableSet, because that guarantees to retain insertion order. However, I have used the methods explained on this page to compare memory usage in an EnumSet<Flag>, an ImmutableSet<Flag> and a Flag[]. Here are the results when a) Flag has 64 enum items and b) all three variants contain all 64 items:
EnumSet: 32 bytes
ImmutableSet: 832 bytes
Array: 272 bytes
So my question is: is there a clever way to pack the enum ordering into a numeric value to get a memory footprint smaller than that of the array? If it makes a difference: in my use case I would assume that the ordering always contains all Enum items.
To clarify: my enum is much smaller than that and I don't have any memory problems as of now, nor is it likely that this situation will ever give me memory problems. It's just that this inefficiency bugs me, even on this microscopic level.
Update:
After suggestions from the various answers and comments I came up with this data structure that uses a byte array. Caveat: It doesn't implement the Set interface (doesn't check for unique values) and it won't scale to large enums beyond what a byte can hold. Also, the complexity is pretty awful, because Enum.values() has to be queried repeatedly (see here for a discussion of this problem), but here goes:
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();
}
};
}
}
The memory footprint is:
EnumOrdering:104
That's a pretty good result so far, thanks to bestsss and JB Nizet!
Update: I have changed the code to only implement Iterable, because anything else would require sensible implementations for equals / hashCode / contains etc.
is there a clever way to pack the enum ordering into a numeric value
Yes, you can represent an ordering as a numeric value, although to use it you need to convert back to a byte/int array. And since there are 64! possible orderings of 64 values, and 64! is bigger than Long.MAX_VALUE, you'd need to store the number in a BigInteger. I guess this would be the most memory-efficient way of storing the ordering, although what you gain in memory you lose in time due to having to convert the number to an array.
For algorithms to convert between number/array representations, see this question.
Here's an alternative to the above, don't know if it's as efficient as on that one, and you'll have to convert the code from int to BigInteger-based, but it should be enough to give you the idea:
/**
* 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;
}
Basically you start with your init array in its natural ordering, then loop over your final array, each time calculating which of the remaining elements should be placed next. This version "deletes" elements from the init array by setting the value to -1. It would probably be more intuitive to use a List or LinkedList, I've just pasted this from some old code I had lying around.
With the above methods and with this as main:
public static void main(String[] args) {
int n = (int) factorial(4);
for ( int i = 0; i < n; i++ ) {
System.out.format( "%d: %s\n", i, Arrays.toString( perm(i, 1, 4 ) ) );
}
}
You get the following output:
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]
Here is an executable version on ideone.
Judging by BigInteger.bitLength(), it should be possible to store an ordering of 64 elements in no more than 37 bytes (plus the overhead of using a BigInteger instance). I don't know if it's worth the trouble, but it makes a nice exercise!
这篇关于在Java中存储枚举的顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
