如何修改传统的笛卡尔产品以减少我的内存开销？

Question

对于我的问题，您最多可能从5-10,000个物品池中选择24个物品。换句话说，我们正在生成配置。

数字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（）值中，id是对数组中项目索引的引用，其他值是属性id和值对。因此$items[10][] = array("id" => "3", "2" => 2, "13" => 100);意味着在位置10中有一个id为3的项目，属性2中的值为2，属性13中的值为100.如果它有助于将一个项目标识为一对，例如（10,0）是位置10中的项目0.

我知道我不是特定的，有61个属性，我不认为它改变了它们所代表的问题的结构。如果我们想要，我们可以将属性2视为权重和属性13作为成本。用户想要解决的问题可能是生成一个配置，其权重为25，成本最小化。

信封数学的背面表示一个粗略的估计，如果每个位置只有2个选择，则是2^24个选择x记录的大小。假设一个32位整数可以被编码来以某种方式表示单个记录，我们正在查看16,777,216 * 4 = 67,108,864字节的内存（完全忽略数据结构开销），并且没有理由相信这些假设中的任何一个将会是有效的，尽管在67兆字节范围内具有较高内存限制的算法将是可接受的内存大小。

没有什么特别的理由要坚持这种表示，我使用了关联数组，因为我使用了可变数量的属性，并且认为这将允许我避免大的稀疏数组。上面的“2”=> 2实际上表示过滤的属性id＃2的值为2，同样属性13的值为100.我很乐意将我的数据结构更改为更紧凑的东西。

我的一个想法是，我确实有一个评估标准，可以用来放弃大多数中间配置。作为例子，我可以计算“13”的“2”“+ 10 *”值的75 *值，以提供解的相对加权。换句话说，如果对问题没有其他限制，则属性2的每个值增加1就花费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)); 
    } 
} 

我希望这对别人解决同样问题有用。