Store porządkuje wyliczenia w Javie

Question

w Javie, EnumSet przechowuje elementy w nim zawarte w maską bitów/bitowym wektorem za pomocą long (RegularEnumSet) lub long[] (JumboEnumSet). Natrafiłem teraz na przypadek użycia, w którym mam wiele tysięcy obiektów domenowych (nazwijmy je Node), z których każdy pokaże wszystkie elementy enum (nazwijmy to Flag) w kolejności, która będzie się różnić w zależności od Obiektu.

Obecnie przechowuję Zakon jako Guava ImmutableSet, ponieważ gwarantuje to zachowanie zamówienia reklamowego. Jednak użyłem the methods explained on this page do porównania użycia pamięci w EnumSet<Flag>, ImmutableSet<Flag> i Flag[]. Oto wyniki, gdy a) Flaga ma 64 elementów typu wyliczeniowego oraz b) wszystkie trzy warianty zawierają wszystkie 64 pozycje:

EnumSet: 32 bajtów
ImmutableSet: 832 bajtów
tablicy: 272 bajtów

Moje pytanie brzmi: czy istnieje sprytny sposób na spakowanie uporządkowania wyliczeniowego w wartość liczbową, aby uzyskać ślad pamięci mniejszy niż tablica? Jeśli to robi różnicę: w moim przypadku użycia zakładam, że zamówienie zawsze zawiera wszystkie elementy Enum.

Aby wyjaśnić: moje wyliczenie jest znacznie mniejsze niż to i nie mam żadnych problemów z pamięcią jak na razie, ani nie jest prawdopodobne, że ta sytuacja kiedykolwiek spowoduje problemy z pamięcią. Tyle tylko, że ta nieskuteczność budzi mnie, nawet na tym mikroskopijnym poziomie.

Aktualizacja:

Po sugestii różnych odpowiedzi i komentarze wymyśliłem tej struktury danych, który wykorzystuje tablicę bajtów. Zastrzeżenie: Nie implementuje interfejsu Set (nie sprawdza unikatowych wartości) i nie będzie skalowany do dużych wartości wyliczeniowych poza to, co bajt może pomieścić. Ponadto, złożoność jest straszne, bo Enum.values ​​() musi być wielokrotnie (see here for a discussion of this problem) zapytaliśmy, ale tu idzie:

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

Ślad pamięci:

EnumOrdering: 104

To całkiem niezły wynik do tej pory, dzięki bestsss i JB Nizet!

Aktualizacja: Zmieniłem kod tylko do wprowadzania iterable, bo nic innego wymagałaby sensownych implementacje dla równymi/hashCode/zawiera itp

Answer 1

jest jakiś sprytny sposób zapakować kolejność enum do wartości liczbowej

Tak, można reprezentować kolejność postaci wartości liczbowej, chociaż go używać trzeba przekonwertować z powrotem do bajt/int array. A ponieważ jest ich 64! możliwe uporządkowania 64 wartości i 64! jest większy niż Long.MAX_VALUE, musisz zapisać numer w numerze BigInteger. Sądzę, że byłby to najbardziej efektywny sposób przechowywania pamięci w porządku, choć to, co zyskujesz w pamięci, tracisz w czasie z powodu konieczności zamiany liczby na tablicę.

Algorytmy do konwersji między reprezentacjami numer/tablica, zobacz this question.

Oto alternatywa dla powyższego, nie wiem, czy jest tak skuteczny jak na powyższym, i będziesz musiał przekonwertować kod z int na BigInteger, na podstawie, ale powinien wystarczyć, aby dać ci pomysł :

/** 
    * 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; 
    } 

Zasadniczo zacząć macierzy Init w swojej naturalnej kolejności, a następnie pętli nad ostatecznej tablicy, każdy obliczeniu czasu, który z pozostałych elementów powinny być umieszczone obok. Ta wersja "usuwa" elementy z tablicy init, ustawiając wartość na -1. Prawdopodobnie byłoby bardziej intuicyjnie korzystać z List lub LinkedList, właśnie wkleiłem to z jakiegoś starego kodu, który leżałem w pobliżu.

Z powyższych metod i z tego jak 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))); 
    } 
} 

uzyskać następujący wynik:

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.

Sądząc BigInteger.bitLength(), powinno być możliwe do przechowywania uporządkowanie 64 elementów w nie więcej niż 37 bajtów (oraz obciążania za pomocą instancji BigInteger). Nie wiem, czy to jest warte problemów, ale to jest przyjemne ćwiczenie!

Answer 2

Jeśli masz 64 wartości enum, można użyć tablicy bajtów, gdzie każdy bajt zawierałby porządek jednego z elementów wyliczających. Wymagałoby to 3 * (64 + 16) = 240 bajtów dla 3 tablic o długości 64 bajtów (16 bajtów to koszt tablicy bajtów, niezależnie od jej długości).

To nadal marnuje przestrzeń, ponieważ każdy bajt jest w stanie przechowywać 8 bitów, ale potrzebujesz tylko 6 do przechowywania liczb od 0 do 63. Więc możesz zastosować inteligentny algorytm pakowania, który użyje 3 bajty (24 bity) do przechowaj 4 numery porządkowe. Doprowadziłoby to do 3 * (64 * 3/4 + 16) = 192 bajtów.

Ssijam manipulacje bajtów, więc zostawię implementację jako ćwiczenie dla ciebie.