12

longJavaでは、EnumSetは、 （RegularEnumSet）またはlong[]（ ）を使用して、含まれるアイテムをビットマスク/ビットベクトルに格納しますJumboEnumSet。私は今、何千ものドメインオブジェクト（それらを呼びましょう）を持っているユースケースに出くわしました。それぞれがオブジェクトごとに異なる順序でNode列挙型のすべてのアイテムを表示します（それを呼びましょう）。Flag

現在、注文をGuavaとして保存していImmutableSetます。これは、挿入注文を保持することが保証されているためです。ただし、このページで説明されている方法EnumSet<Flag>を使用して、、、ImmutableSet<Flag>およびのメモリ使用量を比較しましたFlag[]。a）フラグに64個の列挙型アイテムがあり、b）3つのバリアントすべてに64個のアイテムすべてが含まれている場合の結果は次のとおりです。

EnumSet：32バイト
ImmutableSet：832バイト
配列：272バイト

だから私の質問は：列挙型の順序を数値にパックして、配列のメモリフットプリントよりも小さいメモリフットプリントを取得する賢い方法はありますか？違いが生じる場合：私のユースケースでは、順序には常にすべての列挙型アイテムが含まれていると想定します。

明確にするために：私の列挙型はそれよりもはるかに小さく、現在のところメモリの問題はありません。また、この状況でメモリの問題が発生する可能性もありません。この非効率性は、この微視的なレベルでさえ、私を悩ませているだけです。

アップデート：

さまざまな回答やコメントからの提案の後、バイト配列を使用するこのデータ構造を思いつきました。警告：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();
            }
        };
    }
}

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

EnumOrdering：104

これまでのところ、bestsssとJB Nizetのおかげで、これはかなり良い結果です。

更新：コードを変更してIterableのみを実装しました。これは、equals / hashCode/containsなどに適切な実装が必要になるためです。

4

2 に答える 2

6

列挙型の順序を数値にパックする賢い方法はありますか

はい、順序を数値として表すことができますが、それを使用するには byte/int 配列に戻す必要があります。そして、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: %s\n", 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 で実行可能なバージョンです。

から判断すると、64 個の要素の順序を 37 バイト以内 (およびインスタンスBigInteger.bitLength()を使用するオーバーヘッド) に格納できるはずです。BigInteger苦労する価値があるかどうかはわかりませんが、いい運動になります。

于 2012-06-27T17:16:52.173 に答える
2

64 個の列挙値がある場合、各バイトに列挙項目の 1 つの序数が含まれるバイト配列を使用できます。これには3 * (64 + 16) = 240、64 バイトの 3 つの配列のバイトが必要です (長さに関係なく、16 バイトはバイト配列のコストです)。

各バイトは 8 ビットを格納できるため、これでもスペースが無駄になりますが、0 から 63 までの数値を格納するには 6 ビットしか必要ありません。したがって、3 バイト (24 ビット) を使用して 4 つの列挙序数を格納する巧妙なパッキング アルゴリズムを適用できます。 . 3 * (64 * 3 / 4 + 16) = 192これはバイトにつながります。

私はバイト操作が苦手なので、実装は演習として残しておきます。

于 2012-06-27T14:19:33.983 に答える