代码之家 › 专栏 › 技术社区 › helloandre

在不耗尽内存的情况下生成唯一的组合

algorithm mysql php

helloandre · 技术社区 · 15 年前

我正在编写一个从数据库生成项目组合的算法。它们必须是唯一的排列(即145、156==156、145)。我遇到的问题是如何跟踪以前的组合,这样我就不会得到145、156和156、145。

目前我正在将它们添加到索引为id1_id2的数组中…(已排序,因此ID总是从低到高)并在生成组合时将值设置为1,这样我可以检查$combo s[$index]是否存在。如果它不存在,则创建它。(有其他的标准可以消除每一个排列,但它们是无关的)一旦这些组合被生成,它们就被存储在MySQL的一个表中。

我遇到的问题是,对于我正在使用的测试项(大约85个),在没有耗尽内存的情况下,我无法生成超过3个项(id1_id2_id3)的组合,因为组合的数量很大,$combos数组占用的内存超过了我在PHP内存中分配的64m。

有没有一种方法可以做到这一点a)不跟踪以前的组合,或者b)跳过$combos数组路由,只向mysql添加一个唯一的行,让mysql处理重复检查。

以下是一些伪代码供参考:

$items = array(/*85 items*/);
foreach ($items as $item1){
    generate(array($item1));
        foreach($items as $item2){
            generate(array($item1, $item2));
        }
    }
}

function generate($items_arary){
    $temp_array = array();
    foreach ($items_array as $item){
        $temp_array[] = $item['id'];
    }

    sort($temp_array);
    $index = implode("_", $temp_array);

    if (!$combos[$index]){
        $combos[$index] = 1;
        /* some code to generate query to store to db */
    }
}

查询结果如下:(数据库在脚本开头被截断)

INSERT INTO `combos` (combo_id, more_info) VALUES ('id1_id2', 'Item Name');

在写这个问题的过程中,我想到了一个可能的解决方案:确保ID3>ID2>ID1。这是否是一个可行的解决方案,以消除对$Combos的需求?

6 回复 | 直到 15 年前

Justin Giboney 15 年前

我之所以询问before数据结构是因为您可以这样做:

$sql = "SELECT id FROM test_a";
$result = mysql_query($sql);
while ($row = mysql_fetch_array($result)) {
  $item1 = $row['id'];

  $sql2 = "SELECT id FROM test_a";
  $result2 = mysql_query($sql2);
  while ($row2 = mysql_fetch_array($result2)) {
    $item2 = $row2['id'];

    $combo1 = $item1 . "_" . $item2;
    $combo2 = $item2 . "_" . $item1;

    $sql3 = "SELECT * FROM combos WHERE combo_id = '$combo1' OR combo_id = '$combo2'";
    $result3 = mysql_query($sql3);
    if (mysql_num_rows($result3) == 0) {
      $sql4 = "INSERT INTO combos (combo_id, more_info) VALUES ('$combo1','Item Name')";
      $result4 = mysql_query($sql4);
    }
  }
}

当表test_a的值为1、2、3和4时,此脚本将插入: 1Y1 1Y2 1Y3 1Y4 2Y2 2Y3 2Y4 3Y3 3Y4 4Y4

这不应该有任何内存问题。但是如果你有一个庞大的数据库,你可能会遇到一个与PHP的时间限制有关的问题。

Justin Giboney 15 年前

这里的概念与我的另一个答案相同,但采用了全SQL格式。

INSERT INTO combos (combo_id, more_info) 
  SELECT CONCAT_WS("_",t1.id,t2.id), "item_name" 
  FROM test_a t1, test_a t2 
  WHERE NOT EXISTS (SELECT * FROM combos WHERE combo_id = CONCAT_WS("_",t1.id,t2.id))
    AND NOT EXISTS (SELECT * FROM combos WHERE combo_id = CONCAT_WS("_",t2.id,t1.id))

假设您可以从数据库的某个地方获得项目名称,这可能是您最快、最不占用内存的解决方案。目前我正在对大约1000个ID进行测试。完成后我会更新这个。

Community Dunja Lalic 7 年前

对。您可以存储和使用组合的词典索引来重建/迭代它们,或者在需要迭代所有代码时使用灰色代码。

看一看: “算法515:从词典编纂索引生成向量”;Buckles,B.P.和Lybanon,M.ACM数学软件汇刊,第3卷,第2期,1977年6月。

我已经翻译成C了 here ,并详细描述 here .

Jason S 15 年前

如果不需要自动强制引用完整性(如果使用字符串串联,则不是这样),请为85个项目使用一个表,为每个项目提供索引(0-84),并使用第二个表表示给定的项目集,使用数字数据类型,其中数字中的每个位位置表示一个项目。(例如,000001101表示项目0、2和3)

对于超过64个的项目,您可能需要将它们拆分为多个字段,或者使用blob或字符串(gack!).

如果将此字段用作主键字段,则可以强制执行不重复项。

Deno 9 年前

在TSQL中,您可以使用递归CTE,不记得从哪里得到的,但是非常好。注意mysql不使用“with”选项,所以它在mysql中不起作用。

WITH Numbers(N) AS (
                    SELECT N
                    FROM ( VALUES(1), (2), (3), (4), (5), (6)) Numbers(N)),
                        Recur(N,Combination) AS (
                        SELECT N, CAST(N AS VARCHAR(20)) 
                        FROM Numbers


UNION ALL

SELECT n.N,CAST(r.Combination + ',' + CAST(n.N AS VARCHAR(10)) AS VARCHAR(20)) 
FROM Recur r
INNER JOIN Numbers n ON n.N > r.N)



select Combination
from RECUR
ORDER BY LEN(Combination),Combination;

-1

Alex L 15 年前

增加内存更改

php.ini中的内存限制=512M
或
php脚本中的ini-set(“内存限制”,“512M”)。
或
php_-value-memory_-limit.htaccess中的512M