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

Question

По моей проблеме вы выбираете до 24 предметов из пула, возможно, 5-10 000 предметов. Другими словами, мы генерируем конфигурации.

Номер 24 относится к категориям товаров, каждый элемент связан с определенным местом установки, элемент из местоположения 1 не может быть установлен в местоположении 10, поэтому я организовал свой ассоциативный массив для организации данных группами. Каждый элемент выглядит следующим образом:

$items[9][] = array("id" => "0", "2" => 2, "13" => 20); 

Если первый параметр ($item[9]) говорит вам расположение это разрешено в случае, если вы хотите, это нормально, чтобы думать о том, что вы не можете установить шину на месте для выхлопа. труба.

Элементы хранятся в базе данных mySQL. Пользователь может указать ограничения на решение, например, атрибут 2 должен иметь конечное значение 25 или более. Они могут иметь несколько конкурирующих ограничений. Запросы извлекают элементы, которые имеют какое-либо значение для рассматриваемых атрибутов (неуказанные атрибуты сохраняются, но мы не делаем с ними никаких вычислений). Сценарий PHP затем выделяет любые избыточные варианты (например: если элемент 1 имеет значение атрибута 3, а элемент 2 имеет значение атрибута 5, в отсутствие другого ограничения вы никогда не выберете пункт 1).

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

$items[10][] = array("id" => "3", "2" => 2, "13" => 100); 
$items[10][] = array("id" => "4", "2" => 3, "13" => 50); 
$items[9][] = array("id" => "0", "2" => 2, "13" => 20); 
$items[9][] = array("id" => "1", "2" => -1, "13" => 50); 

Я разместил полный пример набора данных на this pastebin link. Существует причина полагать, что я могу быть более ограничительным на том, что я принимаю в набор данных, но даже при ограничении 2 элемента на один вариант есть проблема.

В значении array() идентификатор является ссылкой на индекс элемента в массиве, а остальные значения - это пары идентификаторов и значений атрибутов. Таким образом, $items[10][] = array("id" => "3", "2" => 2, "13" => 100); означает, что в местоположении 10 есть элемент с id 3, который как значение 2 в атрибуте 2 и значение 100 в атрибуте 13. Если он помогает думать об элементе, идентифицированном парой, например (10,0) является позицией 0 в местоположении 10.

Я знаю, что я не являюсь конкретным, есть 61 атрибут, и я не думаю, что он меняет структуру проблемы с тем, что они представляют. Если мы хотим, мы можем считать атрибут 2 как вес и атрибут 13 как стоимость. Проблема, которую пользователь хочет решить, может состоять в том, чтобы создать конфигурацию, где вес равен 25, а стоимость минимизирована.

Задняя часть конверта соответствует приблизительной оценке, если было всего 2 варианта на каждое место, это 2^24 варианта x размера записи. Предполагая, что 32-битное целое число может быть закодировано для представления одной записи, мы рассматриваем 16 777 216 * 4 = 67 108 864 байт памяти (полностью игнорируя служебные данные структуры данных), и нет оснований полагать, что любое из этих предположений будет допустим, хотя алгоритм с верхней памятью, связанный в области 67 мегабайт, будет приемлемым размером памяти.

Нет особых оснований придерживаться этого представления, я использовал ассоциативные массивы, так как у меня есть переменное количество атрибутов, которые нужно использовать, и подумал, что это позволит мне избежать большого разреженного массива. Над «2» => 2 на самом деле означает, что отфильтрованный атрибут с идентификатором № 2 имеет значение 2 и аналогично значение атрибута 13 равно 100. Я рад изменить свою структуру данных на нечто более компактное.

Я думал, что у меня есть критерии оценки, которые я могу использовать, чтобы отбросить большинство промежуточных конфигураций. Например, я могу вычислить значение 75 * "значение" 2 "" + 10 * "значения 13 для обеспечения относительного взвешивания решений.Другими словами, если бы не было никаких других ограничений для проблемы, каждое повышение стоимости на 1 атрибута 2 стоило бы 75, а каждое повышение стоимости атрибута 13 стоило бы 10. Продолжая идею части автомобиля, подумайте об этом, как покупка запасной части и с машинистом изменить его на наши спецификации.

Одна из проблем, которую я вижу с отбрасыванием конфигураций слишком рано, заключается в том, что функция взвешивания не учитывает такие ограничения, как «конечный результат должен иметь значение« 2 », равное ровно 25». Так что это нормально, если у меня есть полная конфигурация 24 элементов, я могу запустить цикл ограничений, отказаться от решений, которые не совпадают, а затем, наконец, ранжировать оставшиеся решения функцией, но я не уверен, что есть действительный линия мысли, которая позволяет мне раньше отбрасывать решения.

Есть ли у кого-нибудь предложения о том, как двигаться вперед? Хотя языковое агностическое решение в порядке, я реализую в PHP, если есть какая-то соответствующая языковая функция, которая может быть полезна.

Answer 1

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

Главным источником вдохновения для этого решения является the very concise answer on this question. Вот мой код, поскольку поиск первого алгоритма декартовой модели php глубины меньше тривиального.

function dfcartesian ($input, $current, $index) { 
    // sample use: $emptyArray = array(); 
    //    dfcartesian($items, $emptyArray, 0) 
    if ($index == count($input)) { 
     // If we have iterated over the entire space and are at the bottom 
     // do whatever is relevant to your problem and return. 
     // 
     // If I were to improve the solution I suppose I'd pass in an 
     // optional function name that we could pass data to if desired. 
     var_dump($current); 
     echo '<br><br>'; 
     return; 
    } 

    // I'm using non-sequential numerical indicies in an associative array 
    // so I want to skip any empty numerical index without aborting. 
    // 
    // If you're using something different I think the only change that 
    // needs attention is to change $index + 1 to a different type of 
    // key incrementer. That sort of issue is tackled at 
    // https://stackoverflow.com/q/2414141/759749 
    if (isset ($input[$index])) { 
     foreach ($input[$index] as $element) { 
      $current[] = $element; 
      // despite my concern about recursive function overhead, 
      // this handled 24 levels quite smoothly. 
      dfcartesian($input, $current, ($index + 1)); 
      array_pop($current); 
     } 
    } else { 
     // move to the next index if there is a gap 
     dfcartesian($input, $current, ($index + 1)); 
    } 
} 

Я надеюсь, что это будет полезно для кого-то другого, решающего ту же проблему.