tienda una ordenación de las enumeraciones en Java

Question

En Java, un EnumSet almacena los elementos que contiene en un vector de máscara de bits/bits utilizando un long (RegularEnumSet) o long[] (JumboEnumSet). Ahora he encontrado un caso de uso donde tengo muchos miles de objetos de dominio (llamémoslos Node), cada uno de los cuales mostrará todos los elementos de una enumeración (llamémoslo Flag) en un orden que variará por Objeto.

Actualmente estoy almacenando el pedido como Guava ImmutableSet, porque eso garantiza conservar el orden de inserción. Sin embargo, he usado the methods explained on this page para comparar el uso de memoria en un EnumSet<Flag>, un ImmutableSet<Flag> y un Flag[]. Estos son los resultados cuando a) la bandera tiene 64 elementos de enumeración y b) las tres variantes contiene los 64 artículos:

EnumSet: 32 bytes
ImmutableSet: 832 bytes
matriz: 272 bytes

Así que mi pregunta es: ¿hay una forma inteligente de empaquetar el orden enum en un valor numérico para obtener una huella de memoria más pequeña que la de la matriz? Si hace una diferencia: en mi caso de uso, supongo que el orden siempre contiene todos los elementos de Enum.

Para aclarar: mi enumeración es mucho más pequeña que eso y no tengo ningún problema de memoria a partir de ahora, ni es probable que esta situación alguna vez me dé problemas de memoria. Es solo que esta ineficiencia me molesta, incluso en este nivel microscópico.

Actualización:

Después de las sugerencias de las diversas respuestas y comentarios que ocurrió con esta estructura de datos que utiliza una matriz de bytes. Advertencia: no implementa la interfaz Set (no verifica valores únicos) y no se escalará a enumeraciones grandes más allá de lo que puede contener un byte. Además, la complejidad es bastante horrible, porque Enum.values ​​() tiene que ser consultado en varias ocasiones (see here for a discussion of this problem), pero aquí 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(); 
      } 
     }; 
    } 
} 

El consumo de memoria es:

EnumOrdering: 104

¡Es un resultado bastante bueno hasta ahora, gracias a bestsss y JB Nizet!

Actualización: Me han cambiado el código sólo para implementar Iterable, porque cualquier otra cosa sería necesario para implementaciones sensibles iguales/hashCode/etc contiene

Answer 1

hay una manera inteligente para empacar el orden de enumeración en un valor numérico

Sí, puede representar un ordenamiento como un valor numérico, aunque a usarla es necesario convertir de nuevo a un byte/int array. ¡Y ya que hay 64! posibles pedidos de 64 valores, y 64! es más grande que Long.MAX_VALUE, debe almacenar el número en un BigInteger. Supongo que esta sería la manera más eficiente de almacenar el orden en la memoria, aunque lo que gana en memoria lo pierde a tiempo debido a tener que convertir el número en una matriz.

Para algoritmos para convertir representaciones numéricas/matrices, consulte this question.

Aquí hay una alternativa a la anterior, no sé si es tan eficiente como en esa, y tendrás que convertir el código de int a BigInteger -basado en, pero debería ser suficiente para darte la 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; 
    } 

Básicamente se empieza con la matriz de inicio en su orden natural, a continuación, un bucle sobre la matriz final, cada cual calcular el tiempo de los elementos restantes se debe colocar al lado. Esta versión "borra" elementos de la matriz de inicio estableciendo el valor en -1. Probablemente sería más intuitivo usar un List o LinkedList, acabo de pegar esto de un código viejo que tenía por ahí.

Con los métodos anteriores y con esto como 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))); 
    } 
} 

Se obtiene el siguiente resultado:

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.

Juzgando por BigInteger.bitLength(), debe ser posible almacenar un pedido de 64 elementos en no más de 37 bytes (más la sobrecarga de usar una instancia de BigInteger). No sé si vale la pena, ¡pero es un buen ejercicio!

Answer 2

Si tiene 64 valores de enumeración, se puede utilizar una matriz de bytes que cada byte contendría el ordinal de uno de los ítems enum. Esto necesitaría 3 * (64 + 16) = 240 bytes para 3 matrices de 64 bytes (16 bytes es el costo de una matriz de bytes, independientemente de su longitud).

Esto todavía desperdicia espacio, ya que cada byte puede almacenar 8 bits, pero solo necesita 6 para almacenar números del 0 al 63. Así que podría aplicar un algoritmo de empaque inteligente que usaría 3 bytes (24 bits) para almacena 4 ordinales enum. Esto llevaría a 3 * (64 * 3/4 + 16) = 192 bytes.

Me molestan las manipulaciones de bytes, por lo que voy a dejar la implementación como un ejercicio para ti.