Javaで列挙型の注文を格納する

Question

javaでは、EnumSetは、それに含まれる項目をlong（RegularEnumSet）またはlong[]（JumboEnumSet）を使用してビットマスク/ビットベクトルに格納します。私は今、多くの1000個のドメインオブジェクト（Nodeと呼ぶ）を持っているユースケースに出くわしました。各オブジェクトは、オブジェクトごとに異なる順序で列挙型のすべての項目を表示します（Flagとしましょう）。

現在、私はGuava ImmutableSetとして注文を保管しています。これは、その注文を保持するためです。しかし、EnumSet<Flag>、ImmutableSet<Flag>およびFlag[]のメモリ使用量を比較するのにthe methods explained on this pageを使用しました。

EnumSetの：32バイト
のImmutableSet：832バイト
アレイ：272バイト

）フラグ64の列挙項目を有し、b）は、3つのすべての変異体が全64の項目が含まれている場合、ここでの結果であります

だから私の質問は：列挙型の順序を数値にパックする巧妙な方法は、メモリのフットプリントを配列のそれよりも小さくするためですか？違いがある場合：私の使用例では、注文には常にすべてのEnumアイテムが含まれていると仮定します。

明確にする：私の列挙型はそれよりもはるかに小さく、今のところメモリの問題はなく、この状況が私に記憶上の問題を与える可能性もありません。この非効率性は、この微視的なレベルでさえも私には不具合があります。

アップデート：私はバイト配列を使用してこのデータ構造を思い付いた

様々な回答やコメントからの提案の後。警告：Setインターフェイスは実装されていません（一意の値はチェックされません）、バイトが保持できるものを超える大きな列挙型には拡大されません。

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

メモリフットプリントは、次のとおりです：

EnumOrdering：104

Enum.valuesは、（）（ see here for a discussion of this problem）を繰り返し照会する必要があるが、ここに行くのでまた、複雑さは、かなりひどいです

これまでのところ、bestsssとJB Nizetのおかげでかなり良い結果でした！

アップデート：私だけにコードを変更している何か他のものに等しい/のhashCodeのための賢明な実装を必要とするので、反復処理可能を実装/含まれているなど

Answer 1

あなたはバイトに戻って変換する必要があり、それを使用するものの、

はい、あなたは数値として順序を表すことができ数値に列挙順序をパックする巧妙な方法があります/ int配列そして、64があるので！ 64値の可能な順序、および64！がLong.MAX_VALUEより大きい場合は、番号をBigIntegerに保存する必要があります。私はこれが順序を格納する最もメモリ効率的な方法だろうと思うが、配列に数値を変換しなければならないためにメモリ内で何が得られるのか分からない。

数値/配列表現間の変換アルゴリズムについては、this questionを参照してください。

これは上記のような方法ですが、それが効率的であるかどうかわからない場合は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として：

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：あなたは、次の出力を得る

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

。

BigInteger.bitLength()で判断すると、37バイト以内の64要素の順序付け（プラスBigIntegerインスタンスの使用によるオーバーヘッド）が可能でなければなりません。私はそれが問題の価値があるかどうかわからないが、それは素晴らしい運動をする！

Answer 2

あなたは64の列挙値を持っている場合、あなたはどこ各バイト配列を使用することができますバイトには、列挙項目の1つの序数が入ります。これには、3バイトの64バイト（16バイトはその長さにかかわらずバイト配列のコストです）には3 * (64 + 16) = 240バイトが必要です。

これは、各バイトが8ビットを格納できるため、スペースが無駄になりますが、0から63までの数字を格納するのに6つしか必要ありません。したがって、3バイト（24ビット） 4つの列挙型を格納します。これにより、3 * (64 * 3/4 + 16) = 192バイトになります。

私はバイト操作で吸うので、実装を練習問題として残しておきます。