Базовые базы данных Сохранение всех перестановок

Я ищу несколько советов по сохранению всех возможных перестановок для базы данных шаблонов бахромы.

Итак, пятнадцатая проблема с черепицей имеет 16! возможные перестановки, однако сохраняя значения для fringe, так что 0 (пустая плитка), 3,7,11,12,13,14,15 составляет 16!/(16-8)!= 518,918,400 перестановок.

Я хочу сохранить все эти перестановки в структуре данных вместе со значением эвристической функции (которая просто увеличивается каждый раз при повторении первого поиска по ширине), пока я делаю это, но очень медленно и взял мне 5 минут, чтобы хранить 60 000, которых у меня нет времени!

На данный момент у меня есть структура, которая выглядит так.

Value Pos0 Pos3 Pos7 Pos11 Pos12 Pos13 Pos14 Pos15

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

Я довольно не уверен в этом. Состояние головоломки представлено примером массива:

int[] goalState = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

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

(Этот вопрос изначально был основан на хранении в базе данных, но теперь я хочу сохранить их в некоторой форме локальной структуры данных - при медленном извлечении из базы данных)

Ответ 1

Каждое число 0-15 - это 4-разрядное число. Вы должны представить 7 таких чисел, что составляет минимум 28 бит, что находится в пределах 31 подписанного битового пространства int. Таким образом, все перестановки могут быть назначены и получены из, int.

Чтобы вычислить это число, заданные переменные a через g:

int key = a | (b << 4) | (c << 8) | (d << 12) | (e << 16) | (f << 20) | (g << 24);

Чтобы декодировать (если вам нужно):

int a = key & 0xF;
int b = key & 0xF0;
int c = key & 0xF00; // etc

Хранение ints в базе данных очень эффективно и будет использовать минимальное дисковое пространство:

create table heuristics (
    key_value int not null,
    heuristic varchar(32) not null -- as small as you can, char(n) if all the same length
);

После ввода всех строк создайте индекс покрытия для быстрого быстрого поиска:

create unique index heuristics_covering heuristics(key_value, heuristic);

Если вы создадите этот индекс перед вставкой, вставки будут очень, очень медленными.

Создание данных и их вставка - относительно простое кодирование.

Ответ 2

Я не могу понять, какое особое значение имеет 0,3,7,11,12,13,14,15 в вашем случае. Является ли их позиция неизменной? Является ли их позиция достаточной для определения целого состояния головоломки?

В любом случае, вот общий подход, вы можете сузить его в любое время:

Поскольку у вас есть 16 возможных состояний в max, я бы попытался использовать шестнадцатеричные числа для представления ваших перестановок. Таким образом, состояние {1,2,3,6,5,4,7,8,9,10,11,12,13,14,15,0} будет выглядеть как 0x123654789ABCDEF0 = 1312329218393956080. Наибольшее возможное число будет 0xFEDCBA9876543210, которое по-прежнему может храниться в unsigned long (только с Java 8) или, альтернативно, в BigInteger (есть много примеров, я бы предпочел это). Такое число будет уникальным для каждой перестановки и может быть использовано в качестве первичного ключа, и если у вас есть все состояние, извлечение его из базы данных будет довольно быстрым.

//saving your permutation
String state = "0xFEDCBA9876543210";
BigInteger permutationForDatabase = new BigInteger(state, 16);
//and then you can insert it into database as a number

//reading your permutation
char searchedCharacter = 'A';//lets say you look for tile 10
BigInteger permutation = ...;//here you read the number from the database
int tilePosition = permutation.toString(16).indexOf(searchedCharacter);

Возможно, будет более элегантное/эффективное решение для получения позиции плитки (возможно, магия для нескольких бит).

Ответ 3

Итак, мое понимание правильное, что вы вычисляете эвристическое значение для каждого возможного состояния головоломки, и вы хотите, чтобы иметь возможность искать его позже, основываясь на заданном состоянии головоломки? Так что вам не нужно вычислять его на лету? Предположительно из-за времени, которое требуется для вычисления эвристической ценности.

Итак, вы повторяете все возможные состояния головоломки, вычисляя эвристику, а затем сохраняете этот результат. И для этого требуется много времени. Похоже, ваше предположение состоит в том, что для хранения значения требуется много времени, но что, если время ожидания, которое вы видите, - это не время, которое требуется для хранения значений в хранилище данных, а время, в течение которого оно принимает генерировать эвристические значения? Это кажется гораздо более вероятным для меня.

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

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

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

Если мое предположение неверно, что для генерации эвристических значений требуется много времени, то кажется, что вы делаете что-то крайне неоптимальное, когда идете хранить их. Например, при повторном подключении к удаленной базе данных каждый раз, когда вы храните значение. Это может объяснить 5 минут. И если вы будете снова подключаться каждый раз, когда будете искать ценность, это может объяснить, почему это слишком долго.

В зависимости от того, насколько велики ваши эвристические значения, хэш-таблица в памяти может оказаться непрактичной. Бинарный файл записей с произвольным доступом (с каждой записью, просто содержащей эвристическое значение) мог бы сделать то же самое, потенциально, но вам понадобится какой-то способ математического сопоставления домена хэш-ключа с доменом индекса записи (который состоит из последовательных целые числа). Если вы повторяете все возможные состояния головоломок, похоже, у вас уже есть способ отображения состояний головоломки в последовательные целые числа; вам просто нужно выяснить математику.

Использование локальной таблицы базы данных с каждой строкой, просто имеющей ключ и значение, не является необоснованным. Вы определенно сможете вставить 518 миллионов строк за несколько минут - вам просто нужно поддерживать соединение во время процесса загрузки данных и построить свой индекс после завершения загрузки данных. После того, как вы построили индекс на своем ключе, поиск с использованием индекса (кластерного первичного ключа) должен быть довольно быстрым, если вам не нужно повторно подключаться для каждого поиска.

Кроме того, если вы делаете строки в базе данных, вы не хотите фиксировать их после каждой строки, вы захотите зафиксировать каждую 1000 или 10 000 строк. Если вы выполняете запись после каждой строки, это существенно ухудшит производительность загрузки данных.