Conservare un ordinamento di enumerazioni in Java

Question

In Java, un EnumSet memorizza gli elementi in esso contenuti in una maschera di bit/vettore di bit utilizzando un long (RegularEnumSet) o long[] (JumboEnumSet). Ora ho trovato un caso d'uso in cui ho molti oggetti di dominio (chiamiamoli Node), ognuno dei quali mostrerà tutti gli elementi di un enum (chiamiamolo Flag) in un ordine che varierà per Oggetto.

Attualmente sto memorizzando l'ordine come Guava ImmutableSet, perché ciò garantisce di mantenere l'ordine di inserimento. Tuttavia, ho utilizzato the methods explained on this page per confrontare l'utilizzo della memoria in uno EnumSet<Flag>, uno ImmutableSet<Flag> e uno Flag[]. Qui sono i risultati quando a) Flag ha 64 elementi enum e b) tutte e tre le varianti contiene tutti i 64 articoli:

EnumSet: 32 byte
ImmutableSet: 832 bytes
Array: 272 bytes

Quindi la mia domanda è: esiste un modo intelligente per impacchettare l'enumerazione in un valore numerico per ottenere un ingombro di memoria inferiore a quello dell'array? Se fa la differenza: nel mio caso d'uso suppongo che l'ordine contenga sempre tutti gli oggetti Enum.

Per chiarire: il mio enum è molto più piccolo di quello e non ho alcun problema di memoria al momento, né è probabile che questa situazione mi darà mai problemi di memoria. È solo che questa inefficienza mi infastidisce, anche a questo livello microscopico.

Aggiornamento:

Dopo i suggerimenti delle varie risposte e commenti mi si avvicinò con questa struttura dati che utilizza un array di byte. Avvertenza: non implementa l'interfaccia Set (non controlla i valori univoci) e non ridimensiona le enumerazioni di grandi dimensioni oltre ciò che un byte può contenere. Inoltre, la complessità è abbastanza terribile, perché Enum.values ​​() deve essere interrogato ripetutamente (see here for a discussion of this problem), ma qui va:

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

L'occupazione di memoria è:

EnumOrdering: 104

Questo è un buon risultato finora, grazie a bestsss e JB Nizet!

Aggiornamento: ho cambiato il codice per implementare solo Iterable, perché qualsiasi altra cosa richiederebbe implementazioni ragionevoli per equals/hashCode/contiene ecc

Answer 1

c'è un modo intelligente per confezionare l'ordinamento enum in un valore numerico

Sì, è possibile rappresentare un ordinamento come valore numerico, anche se per usarlo è necessario convertire di nuovo a un byte/array int. E dal momento che ci sono 64! possibili ordini di 64 valori e 64! è più grande di Long.MAX_VALUE, è necessario memorizzare il numero in un BigInteger. Immagino che questo sarebbe il modo più efficiente di memoria di memorizzare l'ordine, anche se ciò che si guadagna in memoria si perde nel tempo a causa della necessità di convertire il numero in un array.

Per gli algoritmi di conversione tra rappresentazioni numero/matrice, vedere this question.

Ecco un alternativa a quanto sopra, non so se è così efficace come su quello, e si dovrà convertire il codice da int a BigInteger-based, ma dovrebbe essere sufficiente per darvi l'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; 
    } 

Fondamentalmente si inizia con la matrice init nel suo ordinamento naturale, quindi si simulano l'array finale, ogni volta che calcolo degli elementi rimanenti dovrebbero essere posizionato accanto. Questa versione "elimina" elementi dall'array init impostando il valore su -1. Probabilmente sarebbe più intuitivo usare uno List o LinkedList, ho appena incollato questo codice da un vecchio codice che avevo in giro.

Con i metodi di cui sopra e con questo come 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))); 
    } 
} 

Si ottiene il seguente 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.

A giudicare dal BigInteger.bitLength(), dovrebbe essere possibile memorizzare un ordinamento di 64 elementi in non più di 37 byte (più il sovraccarico dell'utilizzo di un'istanza BigInteger). Non so se ne valga la pena, ma fa un bel esercizio!

Answer 2

Se si dispone di 64 valori enum, è possibile utilizzare un array di byte in cui ogni byte contiene l'ordinale di uno degli elementi enumerati. Ciò richiederebbe 3 * (64 + 16) = 240 byte per 3 matrici di 64 byte (16 byte sono il costo di un array di byte, indipendentemente dalla sua lunghezza).

Questo spreca ancora spazio, poiché ogni byte è in grado di memorizzare 8 bit, ma è necessario solo 6 per memorizzare numeri da 0 a 63. Quindi è possibile applicare un algoritmo di impacchettamento intelligente che utilizzi 3 byte (24 bit) per memorizzare 4 ordinali enum. Ciò porterebbe a 3 * (64 * 3/4 + 16) = 192 byte.

Succhio le manipolazioni dei byte, quindi lascerò l'implementazione come esercizio per te.