1

在我的 MYSQL 数据库中，我有 2 个表：

+-------------------+  +---------------------------------+
|       tags        |  |          relationships          |
+----+--------------+  +---------+---------+------+------+
| id | tag          |  | x_table | y_table | x_id | y_id |
+----+--------------+  +---------+---------+------+------+
| 1  | parent 1     |  | tags    | tags    | 1    | 2    |
| 2  | child 1      |  | tags    | tags    | 1    | 3    |
| 3  | child 2      |  | tags    | tags    | 3    | 4    |
| 4  | grandchild 1 |  +---------+---------+------+------+
+----+--------------+

我需要将这些关系加载到一个多维数组中。孩子的数量可以改变，深度可以改变。每个关系树的深度也不同。

现在我读到递归函数比 PHP 等解释语言的循环慢，并且想知道是否甚至可以用循环编写它，如果是这样，它是否会比使用递归更快且资源消耗更少功能？

多维数组的结构应该如下：

array(
    'id' => $id_from_db,
    'tag' => $tag_from_db,
    'children' => array( /* Just like parent array or false/NULL */ )
)

编辑： 这里的 SQLfiddle

编辑：我创建了递归函数来实现这一点：

private function get_tags($id = false){
    global $pdo;
    $tags = array();

    if(!$id)
        $info = $pdo->query("SELECT DISTINCT
                    t.id,
                    t.tag

            FROM    tags t
            JOIN    relationships r
            ON      r.x_table = 'tags'
            AND     r.y_table = 'tags'
            AND     t.id NOT IN ( SELECT rb.y_id FROM relationships rb WHERE x_table = 'tags' AND y_table = 'tags' )

            ORDER BY t.tag");

    else
        $info = $pdo->query("SELECT DISTINCT
                    t.id,
                    t.tag

            FROM    tags t
            JOIN    relationships r
            ON      r.x_table = 'tags'
            AND     r.y_table = 'tags'
            AND     r.x_id = " .(int)$id."
            AND     r.y_id = t.id

            ORDER BY t.tag");

    while($tag = $info->fetch(PDO::FETCH_ASSOC))
        $tags[] = array('tag' => $tag['tag'], 'children' => $this->get_tags($tag['id']) );

    if(!count($tags))
        return false;

    return $tags;
}
4

2 回答 2

3

如果您不介意一次性获取所有内容（2 个查询），则可以使用引用（标签的总数可能应低于几百个，并且您可以将生成的构造缓存一段时间）：

 //fill tags
 $tags[] = array()
 foreach($pdo->query('SELECT * FROM tags')->fetchAll(PDO::FETCH_ASSOC) as $tag){
    $tags[$tag['id']] = $tag;
 }

 //add relationships
 $relation_query = $pdo->query("SELECT * FROM relationships 
   WHERE x_table='tags'  AND y_table = 'tags'");
 foreach($relation_query->fetchAll(PDO::FETCH_ASSOC) as $relationship){
   //ensure targets exists:
   if(!isset($tags[$relationship['x_id '])) $tags[$relationship['x_id '] = array();
   if(!isset($tags[$relationship['y_id '])) $tags[$relationship['y_id '] = array();

   if(!isset($tags[$relationship['x_id ']['children'])) 
     $tags[$relationship['x_id ']['children'] = array();       

   //add as reference
   $tags[$relationship['x_id ']['children'] = &$tags[$relationship['y_id ']; 
 }

 //pick the tag you want:
 var_dump($tags[1]);
 var_dump($tags[4]);

并不是一张closure表，或者只是路径枚举（从第 18 张幻灯片开始，但整个内容都值得一读）会给您带来更大的性能，并且可以只查询子树。比尔·卡尔文的大道具。

于 2013-06-03T15:51:53.573 回答
0

感谢Wrikken 的一点帮助，我能够想出代码：

public function get_tags(){
    global  $pdo;
    $tags = $childs = array();

    foreach($pdo->query('SELECT * FROM tags')->fetchAll(PDO::FETCH_ASSOC) as $tag)
        $tags[$tag['id']] = $tag;

     foreach($pdo->query("SELECT * FROM relationships WHERE x_table='tags' AND y_table='tags'")->fetchAll(PDO::FETCH_ASSOC) as $relationship){
        if(!isset($tags[$relationship['x_id']]['children'])) 
            $tags[$relationship['x_id']]['children'] = array();       

        $tags[$relationship['x_id']]['children'][] = &$tags[$relationship['y_id']]; 

        $childs[] = $relationship['y_id'];
    }

    while($childs)
        unset($tags[array_pop($childs)]);

    return $tags;
}

这将返回我请求的数组，但如果没有子元素，则子元素根本不存在（这实际上比将其设置为 false 更好）。

基准测试：
我使用每个函数运行了一个简单time php file.php > /dev/null的函数，结果表明使用循环总共花费了0.751s，而递归总共花费了1.303s. 不过，这是在循环一小部分数据。根据代码的结构，我假设随着数据集的增加，递归将成倍增加，而循环的执行时间将以线性方式增加。

总而言之，我会说循环比递归快得多。

于 2013-06-04T03:59:58.083 回答