存储枚举在Java中的排序 [英] Store an ordering of Enums in Java
问题描述
在Java中，一个EnumSet店它包含一个位掩码/位向量使用的项目的长（RegularEnumSet <$ C C $> ）或者长[] （ JumboEnumSet ）。现在我所遇到的一个用例，我有好几千的域对象（我们姑且称之为节点），每个将显示一个枚举所有（我们称之为的顺序，将每个对象有所不同标志）。
目前我储存的顺序番石榴<一个href="http://docs.guava-libraries.google$c$c.com/git/javadoc/com/google/common/collect/ImmutableSet.html"><$c$c>ImmutableSet,因为，保证保留插入顺序。不过，我已经使用方法在此页面解释在 EnumSet＆LT比较内存使用情况;旗＆GT; ，一个 ImmutableSet＆LT;旗＆GT; 和标志[] 。下面是结果时）标志有64枚举项目和b）所有三种型号包含了所有64项：
EnumSet：32字节
ImmutableSet：832字节
阵列：272字节
所以我的问题是：有一个聪明的方法来包装枚举排序成一个数值来获得内存占用比阵列小？如果它的确与众不同：在我的使用情况下，我会假设顺序总是包含所有枚举项
要澄清：我的枚举比小得多，我没有任何内存问题，截至目前，它也不是很有可能，这种情况永远不会给我的记忆问题。只是，这种低效率的错误我，即使是在这种微观水平。
更新：
在从不同的答案和意见建议，我想出了一个使用一个字节数组这种数据结构。警告：它没有实现Set接口（不检查唯一值），它会不会扩展到超过一个字节可以容纳什么大的枚举。此外，复杂度为pretty的可怕，因为Enum.values（）必须重复查询（在这里看到这个问题的讨论），但这里有云：
公共类EnumOrdering＆LT; e扩展Enum＆LT; E＆GT;＆GT;实现了Iterable＆LT; E＆GT; {
私人最终类别＆LT; E＆GT;类型;
私人最终byte []的顺序;
公共EnumOrdering（final类＆LT; E＆GT;类型，最后收集和LT; e基序）{
this.type =类型;
this.order =新的字节[order.size（）];
INT偏移= 0;
对于（最终项目而：顺序）{
this.order [偏移++] =（字节）item.ordinal（）;
}
}
@覆盖
公共迭代器＆LT; E＆GT;迭代（）{
返回新AbstractIterator＆LT; E＆GT;（）{
私人INT偏移= -1;
私人最终E [] enumConstants = type.getEnumConstants（）;
@覆盖
保护ËcomputeNext（）{
如果（偏移所述; order.length - 1）{
返回enumConstants [为了[++偏移];
}
返回endOfData（）;
}
};
}
}
的内存占用是：
EnumOrdering：104
这是一个pretty的好成绩，到目前为止，由于bestsss和JB Nizet！
更新：我已经改变了code只实现Iterable，因为别的需要合理的实现等号/散列code /载等
有一个聪明的方法来包装枚举排序成数值
是的，你可以重新present排序为数值，但使用它，你需要转换回一个字节/ int数组。并且，因为有64！ 64个值和64的可能的顺序！大于为Long.MAX_VALUE ，你需要存储在的BigInteger 的数量。我想这将是存储排序的大多数内存，有效的方式，但你在内存中获得你失去的时间，由于无需将数字转换为一个数组。
有关算法，数字/阵列之间进行转换再presentations，请参阅<一href="http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms">this问题。
下面是一个替代上面，不知道这是否是一样有效，在那一个，你就必须从 INT 转换code以的BigInteger 为主，但应足以给你的想法：
/ **
*返回n个数的第i个排列[从...到]
*（其中，n ==至 - 从+ 1）。
*排列的编号从0到n！-1，如果我是超出此
*范围内它被当作I％N！
* @参数我
*从@param
* @参数ñ
* @返回
* /
公共静态INT []烫发（长的我，从int，int值）
{
//方法规范的数字排列，从0到n！-1。
//如果你希望他们从1到n !,取消注释此行。
// I - = 1;
INT N =来 - 从+ 1;
INT [] initArr =新INT [N]; //号[从...到]
INT [] finalArr =新INT [N]; //数字排列[从...到]
//填充初始阵列
为（中间体K = 0; K＆n种; k ++）
initArr [K] =从K +;
//计算回报数组，逐个元素
为（中间体K = 0; K＆n种; k ++）{
INT指数=（int）的（（ⅰ％阶乘（NK））/阶乘（NK-1））;
//找到从初始阵列的index_th元件，和
//删除就被它的值设置为-1
INT M = convertIndex（initArr，索引）;
finalArr [K] = initArr [M]。
initArr [米] = -1;
}
返回finalArr;
}
/ **
*使用的烫发Helper方法。
*找到改编的index_th元素，当值等于-1被跳过的索引。
* 例如。如果ARR = [20，18，-1，19]，然后convertIndex（ARR，2）返回3。
* /
私有静态诠释convertIndex（INT []改编，INT指数）
{
INT米= -1;
而（索引＆gt; = 0）{
M +;
如果（ARR [M]！= -1）
指数 - ;
}
返回米;
}
基本上你开始你的初始化数组中的自然排序，然后遍历最终数组，每次计算剩余元素应放在旁边。这个版本的删除，从初始化数组元素设置为-1的值。或许，这将是更直观地使用列表或的LinkedList ，我刚刚粘贴此从一些老code我已经躺在附近。
通过上述方法，并以此为主：
公共静态无效的主要（字串[] args）{
INT N =（int）的阶乘（4）;
的for（int i = 0;我n种;我++）{
System.out.format（％D：％S \ N，我，Arrays.toString（烫发（我，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判断（），系统应该是可以存储64个元素的排序在不超过37字节（加上使用的开销的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屋！
