Сохранение большого массива для более быстрого доступа

Question

У меня есть 5-мерный массив, где все показатели варьируются от 2 до 14. Он содержит все возможные перестановки последовательности из 5 чисел. Этот массив содержит 525720 перестановок, на вычисление которых уходит довольно много времени. (5-7 секунд на моем MacBook Pro). Его следует использовать в качестве справочной таблицы, чтобы получить доступ к значению в постоянное время или, более конкретно, к значению определенной покерной руки:

array[2][3][4][5][7] // 1
array[5][5][5][5][14] // 2000

Есть ли более быстрый способ создать этот массив? Я думал о том, чтобы как-то сохранить массив, а затем загружать его каждый раз, когда запускается моя программа, но есть ли эффективные способы сделать это?

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

Answer 1

Я бы начал со свертывания ваших размеров для индексации:

при условии, что у вас есть набор индексов (из вашего первого примера, допустимые значения от 2 до 14):

 i1 = 2
 i2 = 3
 i3 = 5
 i4 = 6
 i5 = 7

и создал ваш массив с

 short array[] = new short[13 * 13 * 13 * 13 * 13];
 ...

тогда доступ к каждому элементу становится

 array[(i1 - 2) * 13 * 13 * 13 * 13 + (i2 - 2) * 13 * 13 * 13 + (i3 - 2)
     * 13 * 13 + (i4 - 2) * 13 + (i5 - 2)]

Этот массив займет намного меньше памяти, поскольку вам не нужно создавать дополнительный слой объектов вдоль каждого измерения, и вы можете легко сохранить все содержимое в файле и загрузить его в один список.

Также будет быстрее проходить этот массив, потому что вы будете выполнять 1/5 поиска в массиве.

Кроме того, сокращение количества элементов в каждом измерении сэкономит значительную память.

Чтобы сохранить ваш код в чистоте, этот массив должен быть скрыт внутри объекта с помощью метода get и set, который принимает пять индексов.

Answer 2

Не прямой ответ на ваш оригинальный вопрос, но ...

Если вы пытаетесь провести быструю оценку покерных рук, вы должны убедиться, что вы прочитали Сводка новостей по покерным рукам Great *

В частности: Оценщик покерных рук Кактуса Кева .

Я принимал участие в длительной дискуссии о проведении максимально быстрых оценок покера в 5 и 7 рук, откуда берутся большинство этих вещей. Честно говоря, я не вижу, как эти оценки будут идти быстрее, пока вы не сможете хранить все значения C (52,5) или 2 598 960 в справочной таблице.

Answer 3

Запишите это через MappedByteBuffer. Создайте достаточно большой файл, отобразите его, получите asIntBuffer (), введите свои числа.

Затем вы можете отобразить его позже и получить к нему доступ через IntBuffer.get (Очевидное математическое представление).

Это намного быстрее сериализации.

Answer 4

^{Я не уверен, что ваши перестановки в покерных комбинациях верны, но в любом случае ...}

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

Сначала вычислите значение для руки. Допустим, у вас есть пять карт (с1, с2, с3, с4, с5):

handValue = EvaluateHand(c1, c2, c3, c4, c5);

// Store the pre-calculated hand value in a table for faster lookup
hand[c1][c2][c3][c4][c5] = handValue;

Затем присвойте handValue всем перестановкам этой руки (т.е. порядок карт карт не меняет handValue).

hand[c1][c2][c3][c5][c4] = handValue;
hand[c1][c2][c4][c3][c5] = handValue;
hand[c1][c2][c4][c5][c3] = handValue;
hand[c1][c2][c5][c3][c4] = handValue;
hand[c1][c2][c5][c4][c3] = handValue;
:
etc.
:
hand[c5][c4][c3][c2][c1] = handValue;

Answer 5

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

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

Поскольку эти значения, по-видимому, изменятся только в случае изменения вашего алгоритма оценки покерной руки, будет достаточно просто отправить сериализованный файл. Размер файла должен быть разумным, если данные, которые вы храните в каждом элементе массива, не слишком велики (например, если это 16-разрядное целое число, размер файла будет около 1 МБ).

Answer 6

Прежде всего, спасибо за ваш энтузиазм!

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

О MappedByteBuffer ... Правильно ли понято, что это позволяет загрузить часть сериализованного массива? Поэтому я загружаю нужные мне значения во время выполнения вместо загрузки всего массива при запуске?

@ Jennie Костюмы хранятся в другом массиве. Я не уверен, что это лучший способ, так как есть много вещей, чтобы рассмотреть эту конкретную проблему. Флеш - это, в основном, старшая рука с другим значением ... Так что у меня нет реальной причины хранить одни и те же перестановки (старшие карты) дважды, но сейчас это способ сделать это. Я думаю, что путь - это хеш-функция, поэтому я могу легко конвертировать старшие значения в сбрасываемые значения, но я не слишком много думал об этом.

Что касается признаков, вы, конечно, правы. Это только сейчас. Мне проще проверить значение «2 3 4 5 6», просто введя значения карт на данный момент ... Позже я урежу массив!

Answer 7

Несколько вещей:

Если это для покерных рук, вы не можете просто хранить 2-14. Вам также необходимо хранить костюм. Это действительно означает, что вам нужно хранить 0-51. В противном случае вы не сможете узнать, является ли array[2][3][4][5][6] стрит или стрит-флеш.

Если вам на самом деле не нужно хранить костюмы для вашего приложения, и вы действительно хотите сделать это в массиве, используйте индексы 0-12, а не 2-14. Это позволит вам использовать массив 13 × 13 × 13 × 13 × 13 (371 293 члена) вместо массива 15 × 15 × 15 × 15 × 15 (759 375 членов). Всякий раз, когда вы обращаетесь к массиву, вам просто нужно вычесть 2 из каждого индекса. (Я не уверен, где вы получили ваш счет 525 720 ...)