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

Question

对于我的问题，您要从大约 5-10,000 项的池中选择最多 24 项。换句话说，我们正在生成配置。

数字 24 来自项目类别，每个项目都与特定的安装位置相关联，位置 1 的项目不能安装在位置 10，所以我安排了我的关联数组以分组组织数据。每个项目看起来像：

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

第一个参数 ( $item[9] ) 告诉您允许进入的位置。如果您愿意，可以考虑不能在排气管的位置安装轮胎的想法。

项目存储在 mySQL 数据库中。用户可以指定对解决方案的限制，例如，属性 2 的最终值必须为 25 或更大。他们可以有多个竞争限制。查询检索对正在考虑的属性具有任何值的项目（存储未指定的属性，但我们不对它们进行任何计算）。 PHP 脚本然后 p运行排除任何多余的选择（例如：如果项目 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是对item在数组中索引的引用，其他值是属性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。我很高兴将我的数据结构更改为更紧凑的东西。

我的一个想法是我确实有一个评估标准可以用来丢弃大部分中间配置。例如，我可以计算 75 * "value of "2"" + 10 * "value of "13" 来提供解决方案的相对权重。换句话说，如果对问题没有其他限制，属性 2 的每个价值改进 1 成本为 75，属性 13 的每个价值改进成本为 10。继续汽车零件的想法，将其视为购买库存零件并让机械师根据我们的规格进行修改。

我看到过早丢弃配置的一个问题是加权函数没有考虑限制，例如 "the final result must have a value of "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
    // 
    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 ) );
    }
}

我希望这对解决同样问题的其他人有用。

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

How can I modify a traditional cartesian product to reduce my memory overhead?

php

algorithm

cartesian-product