Есть ли способ вычисления индексов, генерируемых вложенными циклами?

Question

В настоящее время я думаю о том, как хранить часто используемые данные. Он предназначен для хранения в массиве и в настоящее время создается следующим образом.

public static void generateData() { 

    int index = 0; 
    for(int a1 = 0; a1 < 52; a1++) { 
     for(int a2 = a1 + 1; a2 < 52; a2++) { 
      for(int a3 = a2 + 1; a3 < 52; a3++) { 
       for(int a4 = a3 + 1; a4 < 52; a4++) { 
        for(int a5 = a4 + 1; a5 < 52; a5++) { 
         for(int a6 = a5 + 1; a6 < 52; a6++) { 
          for(int a7 = a6 + 1; a7 < 52; a7++) { 
           data[index++] = compute(a1,a2,a3,a4,a5,a6,a7); 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
} 

Моя проблема заключается в том, чтобы быстро получить доступ к вычисленным данным с использованием параметров a1-a7. Единственный подход, который я мог думать о том, чтобы перебирать подобно тому, как во время итерации, пока параметры не являются такими же, как этот

public static int getIndex(int i1, int i2, int i3, int i4, int i5, int i6, int i7) { 
    int index = 0; 
    for(int a1 = 0; a1 < 52; a1++) { 
     for(int a2 = a1 + 1; a2 < 52; a2++) { 
      for(int a3 = a2 + 1; a3 < 52; a3++) { 
       for(int a4 = a3 + 1; a4 < 52; a4++) { 
        for(int a5 = a4 + 1; a5 < 52; a5++) { 
         for(int a6 = a5 + 1; a6 < 52; a6++) { 
          for(int a7 = a6 + 1; a7 < 52; a7++) { 

           if(a1 == i1 && a2 == i2 && a3 == i3 && a4 == i4 && a5 == i5 && a6 == i6 && a7 == i7) { 
            return index; 
           } else { 
            index++; 
           } 

          } 
         } 
        } 
       } 
      } 
     } 
    } 

    throw new IllegalArgumentException(); 
} 

Однако этот подход работает только в линейном времени, который не достаточно быстро, учитывая количество данные. Из-за этого мне было интересно, есть ли способ вычислить индекс в постоянном или логарифмическом времени. Как мой вопрос может показаться довольно расплывчатым. Я сохраняю все возможные результаты каждой возможной руки Texas hold'em, чтобы провести некоторое дополнительное тестирование.

Answer 1

В вашем случае index можно рассматривать как число в Combinatorial number system, где переменный цикл a1 ... a7 являются цифрами этого числа.

Вот функция, которая вычисляет индекс из заданных переменных цикла.

public static int getIndex(int a1, int a2, int a3, int a4, int a5, int a6, int a7) { 
    return 133784559 - (C7[a1] + C6[a2] + C5[a3] + C4[a4] + C3[a5] + C2[a6] + (51 - a7)); 
} 

static final int[] C2 = Ck(2), C3 = Ck(3), C4 = Ck(4), C5 = Ck(5), C6 = Ck(6), C7 = Ck(7); 

// Creates a cache of C(51-i, k) for 0 <= i < 52 
static int[] Ck(int k) { 
    int[] result = new int[52]; 
    for (int i = 0; i < 52; i++) { 
     result[i] = (int) C(51 - i, k); 
    } 
    return result; 
} 

// Computes binomial coefficient C(n, k) 
static long C(int n, int k) { 
    long C = 1; 
    for (int i = 0; i < k; i++) { 
     C = C * (n - i)/(i + 1); 
    } 
    return C; 
} 

getIndex метод довольно быстро и требует лишь около 1К дополнительной статической памяти.

Answer 2

Вы можете рассмотреть возможность хранения параметров в виде строкового ключа на карте в нужном вам индексе. Поэтому вы можете объявить Map<String,Integer> indexMap = new HashMap<>(); в своем классе.

Затем в методе generateData вы можете сохранить параметры как один большой строковый ключ.

indexMap.put(Integer.toString(a1)+Integer.toString(a2)+ ... + 
    Integer.toString(a7),index); 

Просто убедитесь, что вы сохранили индекс, прежде чем увеличивать его. Это позволит вам затем сделать

return indexMap.get(Integer.toString(a1)+Integer.toString(a2)+ ... + 
    Integer.toString(a7)); 

Вы должны сделать проверку ошибок для ключа не найдена ошибка, но это позволит вам получить индекс вы хотите гораздо быстрее.

Answer 3

Я бы использовал HashMap, чтобы сохранить a1..a7 -> compute value, так как я не уверен, есть ли эффективный алгоритм для извлечения индекса от a1 ... a7 в разумные сроки. Но я хотел бы использовать Long в качестве ключа карты и построить его следующим способ

long key = (((((a1 * 100L + a2) * 100 + a3) * 100 + a4) * 100 + a5) * 100 + a6) * 100 + a7 

или как функция

public static long getKey(int ... array) { 
    if (array.length != 7) { 
     throw new IllegalArgumentException(); 
    } 
    long value = 0; 
    for (int item : array) { 
     value = value * 100 + item; 
    } 
    return value; 
} 

Это должно сделать поиск, генерации ключей и потребление пространства эффективного (Карта будет содержать 133784560 записи).

Примечание, что a1 умножается на 100L, в противном случае результат будет неправильным, так как он не подходит диапазон Integer.