logo标签列表

通过链接导航多个对象而不重复

phparraysloopsobject
13

我想要浏览一组包含链接到其他对象的对象。我想从id为1的对象开始，遍历每个对象。其中一些对象将会循环回到之前的对象，因此我要确保只查看每个对象一次，否则我会陷入无限循环中。我还想知道哪些对象不能通过浏览链接来访问。我认为导航的顺序并不重要。

这是一个我可能会遇到的示例数据集（我的实际数据将来自数据库）：

<?php

$obj_array = [] ;

$obj = new stdClass;
$obj->id = 1;
$obj->name = "Apple";
$obj->link = array(14, 5);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 3;
$obj->name = "Carrot";
$obj->link = array(1, 14, 3);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 4;
$obj->name = "Dill";
$obj->link = array(1, 5);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 5;
$obj->name = "Egg";
$obj->link = array(6);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 6;
$obj->name = "Fred";
$obj->link = array(7);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 7;
$obj->name = "Goat";
$obj->link = array(7, 8);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 8;
$obj->name = "Harry";
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 9;
$obj->name = "Igloo";
$obj->link = array(14, 5);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 10;
$obj->name = "Jason";
$obj->link = array(1, 5, 8);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 11;
$obj->name = "Klaus";
$obj->link = array(1, 5, 10);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 14;
$obj->name = "Banana";
$obj->link = array(3);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 15;
$obj->name = "Oyster1";
$obj->link = array(16);
$obj_array[] = $obj;


$obj = new stdClass;
$obj->id = 16;
$obj->name = "Oyster2";
$obj->link = array(15);
$obj_array[] = $obj;

我希望看到类似这样的内容（顺序无关紧要）:

已处理：

Apple
Banana
Carrot
Egg
Fred
Goat
Harry

未链接：

Dill
Igloo
Jason
Klaus
Oyster1
Oyster2

当每个对象都可以具有多个链接时，如何创建循环来遍历这样的结构？

您提供的对象并没有真正地链接在一起，因为您无法从一个对象导航到另一个对象，因为该对象并没有实际保持对另一个对象的引用，只是匹配另一个对象的“id”值的整数。您还未能清楚地定义您正在使用的API。通常，在网络遍历问题中，输入不是整个网络（通常太大），而只是一个节点/根。因此，我猜想您想要的函数可能不会将整个对象数组作为输入。 - BeetleJuice
另外一件事：你是指对象链接到它们自己吗？（例如，egg和goat这样做）？ - BeetleJuice
@BeetleJuice 是的，如果我理解正确的话，你两个方面都是正确的。对象是根据所有权从数据库中获取的。每个用户都将拥有自己的个人对象，并链接到他们拥有的其他对象。因此，返回的对象将是整个数据库表的子集。 - kojow7
@BeetleJuice 是的，虽然不太可能，但对象可以链接到自身。我在这里的测试数据中尝试考虑了每种可能的情况。 - kojow7
4个回答
6

虽然@wizards answer的方法可行，但我认为我想要一个代码更清晰的版本。下面的版本返回一个带有链接和非链接元素的对象，我相信它的工作原理非常清楚。

我之所以想要这样工作，是为了能够扩展它来回答未来的问题。例如“一个项目被链接了多少次”或“哪个项目有最多的链接”。它可以轻松地适应这些问题的答案。

另一个好处是尽可能使用有限的循环，当大小增加时，这可能会加快速度。

<?php
error_reporting(E_ALL);

$obj_array = [] ;

$obj = new stdClass;
$obj->id = 1;
$obj->name = "Apple";
$obj->link = array(14, 5);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 3;
$obj->name = "Carrot";
$obj->link = array(1, 14, 3);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 4;
$obj->name = "Dill";
$obj->link = array(1, 5);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 5;
$obj->name = "Egg";
$obj->link = array(6);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 6;
$obj->name = "Fred";
$obj->link = array(7);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 7;
$obj->name = "Goat";
$obj->link = array(7, 8);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 8;
$obj->name = "Harry";
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 9;
$obj->name = "Igloo";
$obj->link = array(14, 5);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 10;
$obj->name = "Jason";
$obj->link = array(1, 5, 8);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 11;
$obj->name = "Klaus";
$obj->link = array(1, 5, 10);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 14;
$obj->name = "Banana";
$obj->link = array(3);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 15;
$obj->name = "Oyster1";
$obj->link = array(16);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 16;
$obj->name = "Oyster2";
$obj->link = array(15);
$obj_array[] = $obj;


/*
 * CALL
 */

$parser = new ObjectLinker($obj_array, 1);

//dump found
//decode/encode to only show public values
print_r(json_decode(json_encode($parser)));


/*
 * ACTUAL CODE
 */


class ObjectLinker
{
    private $_array;
    private $_start;

    public $LinkedElements = array();
    public $UnLinkedElements = array();

    final public function __construct($ar, $start)
    {
        $this->_array = $ar;
        $this->_start = $start;

        $this->getElementsArray();
        $this->findLinked($this->_start);
    }

    final private function getElementsArray()
    {       
            //since each Id is unique, i'm using the ID as the key in the array. this will allow faster access
            //Ofcourse it would be better if you would create the array like this in the first place, then you can skip this step
            foreach($this->_array as $obj) {
                if (!is_null($obj) && property_exists($obj, 'id')) {
                    //I add everything to the unlinked elements. We will remove the linked once, to have once less loop
                    $this->UnLinkedElements[$obj->id] = $obj;
                }
            }
    }


    final private function findLinked($id)
    {
        //If the key is not in the array, it's already loaded
        if (!array_key_exists($id, $this->UnLinkedElements)) {
            return;
        }

        //get obj
        //Because of the getElementsArray() step, I'm already sure the object exists.
        //If you change the input array, you might want to check for invalid obj
        $obj = $this->UnLinkedElements[$id];

        //add to linked
        $this->LinkedElements[$id] = $obj;

        //remove from unlinked
        unset($this->UnLinkedElements[$id]);

        //no links
        if (!property_exists($obj, 'link')) {
            return;
        }

        $links = $obj->link;

        //Invalid links
        if (!is_array($links)) {
            return;
        }

        //check links
        foreach($links as $link) {
            $this->findLinked($link);
        }
    }

}

?>

输出：

stdClass Object
(
  [LinkedElements] => stdClass Object
    (
      [1] => stdClass Object
        (
          [id] => 1
          [name] => Apple
          [link] => Array
            (
              [0] => 14
              [1] => 5
            )

        )

      [14] => stdClass Object
        (
          [id] => 14
          [name] => Banana
          [link] => Array
            (
              [0] => 3
            )

        )

      [3] => stdClass Object
        (
          [id] => 3
          [name] => Carrot
          [link] => Array
            (
              [0] => 1
              [1] => 14
              [2] => 3
            )

        )

      [5] => stdClass Object
        (
          [id] => 5
          [name] => Egg
          [link] => Array
            (
              [0] => 6
            )

        )

      [6] => stdClass Object
        (
          [id] => 6
          [name] => Fred
          [link] => Array
            (
              [0] => 7
            )

        )

      [7] => stdClass Object
        (
          [id] => 7
          [name] => Goat
          [link] => Array
            (
              [0] => 7
              [1] => 8
            )

        )

      [8] => stdClass Object
        (
          [id] => 8
          [name] => Harry
        )

    )

  [UnLinkedElements] => stdClass Object
    (
      [4] => stdClass Object
        (
          [id] => 4
          [name] => Dill
          [link] => Array
            (
              [0] => 1
              [1] => 5
            )

        )

      [9] => stdClass Object
        (
          [id] => 9
          [name] => Igloo
          [link] => Array
            (
              [0] => 14
              [1] => 5
            )

        )

      [10] => stdClass Object
        (
          [id] => 10
          [name] => Jason
          [link] => Array
            (
              [0] => 1
              [1] => 5
              [2] => 8
            )

        )

      [11] => stdClass Object
        (
          [id] => 11
          [name] => Klaus
          [link] => Array
            (
              [0] => 1
              [1] => 5
              [2] => 10
            )

        )

      [15] => stdClass Object
        (
          [id] => 15
          [name] => Oyster1
          [link] => Array
            (
              [0] => 16
            )

        )

      [16] => stdClass Object
        (
          [id] => 16
          [name] => Oyster2
          [link] => Array
            (
              [0] => 15
            )

        )

    )

)
谢谢Hugo。经过测试，你的答案是目前速度最快、易于理解和具有可重用对象集的最有效的答案。 - kojow7
如果您有机会，请查看我的最新问题。 - kojow7
在大多数情况下，任何代码都可以通过提高速度、内存、效率等方面进行改进。我们只是使用了不同的编程范式，如面向对象编程和函数式编程 :) 不幸的是，PHP不支持尾递归优化，尽管您的代码可能无法使用它，在这种能力存在的情况下) 无论如何，感谢您的代码！ :) - Wizard
@kojow7 不要问一个95%内容相同的新问题。更新这个问题，附上你的表结构或者直接问一个“如何将这个表结构转换为这个对象结构”的问题，并且在提问中附上这个问题的链接，说明你需要它的原因。采用第二种方式，你会得到更多的回复。 - Hugo Delsing
@HugoDelsing，问题在于如果我修改我的问题，那么将使每个人为回答我的问题所付出的努力失效，而且它们都是好答案。提出第二个关于转换表结构的问题可能会起作用，但不如保留现有结构高效，因为必须额外完成一些工作才能进行转换。 - kojow7
5
你可以跳过打印步骤，直接使用$obj_array本身，将数据分成两个数组只是为了方便漂亮地打印它们。
$linked_ids = array();
$processed_objects = array();
$unlinked_objects = array();

foreach ( $obj_array as $obj ) {
    if ( isset($obj->link) && $obj->link ) {
        $linked_ids = array_merge($linked_ids, $obj->link);
    }
}

$linked_ids = array_unique( $linked_ids );

foreach ($obj_array as $obj) {
    if ( !in_array($obj->id, $linked_ids) ) {
        $unlinked_objects[] = $obj;
    } else {
        $processed_objects[] = $obj;
    }
}

/* Printing */

echo '<b>Processed:</b><br>';

foreach ( $processed_objects as $obj ) {
    echo $obj->name . '<br>';
}

echo '<b>Not Linked:</b><br>';

foreach ( $unlinked_objects as $obj ) {
    echo $obj->name . '<br>';
}
虽然你的代码一开始看起来很有前途，但它并不适用于所有情况。我已经更新了我的示例。你会注意到你的代码错误地处理了对象#10、15和16。我当然愿意听取其他建议。 - kojow7
Klaus（＃11）正在链接到Jason（＃10），同样的，＃15链接到＃16，反之亦然！？ - Plamen Nikolov
嗨，Plamen，是的，用户可以定义任何方向和任何对象的链接，甚至可以像Goat(#7)中看到的那样链接自身。 - kojow7
我明白了，但为什么#10、#15和#16应该在“未链接”中输出？ - Plamen Nikolov
因为如果你从#1开始，就没有办法通过跟随链接到达任何其他数字。 #1始终是起点。 - kojow7
5

回答已更新，现在代码遍历一个以ID=1开头的数组，在运行时收集所有符合条件的“连接”链接并显示对象的名称。我希望能够实现期望的结果。

第一个列表（虚线之前）是可以通过与ID=1的对象连接的链接访问的列表。

第二个列表中缺少名称。

代码如下：

<?php

$obj_array = [] ;

$obj = new stdClass;
$obj->id = 1;
$obj->name = "Apple";
$obj->link = array(14, 5);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 3;
$obj->name = "Carrot";
$obj->link = array(1, 14, 3);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 4;
$obj->name = "Dill";
$obj->link = array(1, 5);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 5;
$obj->name = "Egg";
$obj->link = array(6);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 6;
$obj->name = "Fred";
$obj->link = array(7);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 7;
$obj->name = "Goat";
$obj->link = array(7, 8);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 8;
$obj->name = "Harry";
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 9;
$obj->name = "Igloo";
$obj->link = array(14, 5);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 10;
$obj->name = "Jason";
$obj->link = array(1, 5, 8);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 11;
$obj->name = "Klaus";
$obj->link = array(1, 5, 10);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 14;
$obj->name = "Banana";
$obj->link = array(3);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 15;
$obj->name = "Oyster1";
$obj->link = array(16);
$obj_array[] = $obj;

$obj = new stdClass;
$obj->id = 16;
$obj->name = "Oyster2";
$obj->link = array(15);
$obj_array[] = $obj;

function findObject($objects, $id) {
    foreach ($objects as $object) {
        if ($object->id === $id) {
            return $object;
        }
    }
    return null;
}

function getLinkedIds($objects, $startId=1) {
    $idQueue = [$startId];
    $linkedIds = [];
    while (count($idQueue)) {
        $id = array_pop($idQueue);
        $obj = findObject($objects, $id);
        if (!is_null($obj) && property_exists($obj, 'link')) {
            $linksToAdd = array_filter($obj->link, function($linkedId) use ($linkedIds) {
                return !in_array($linkedId, $linkedIds);
            });
            $idQueue = array_merge($idQueue, $linksToAdd);
        }
        $linkedIds[] = $id;
    }
    return array_unique($linkedIds);
}

function getNotLinkedObjects($objects, $startId=1) {
    $linked = getLinkedIds($objects, $startId);
    return array_filter($objects, function($obj) use ($linked) {
        return !in_array($obj->id, $linked);
    });
}

function getLinkedObjects($objects, $startId=1) {
    $linked = getLinkedIds($objects, $startId);
    return array_filter($objects, function($obj) use ($linked) {
        return in_array($obj->id, $linked);
    });
}

function listNames($objects) {
    foreach ($objects as $obj) {
        echo $obj->name.PHP_EOL;
    }
}

listNames(getLinkedObjects($obj_array));
echo '----'.PHP_EOL;
listNames(getNotLinkedObjects($obj_array));

结果：

Apple
Carrot
Egg
Fred
Goat
Harry
Banana
---
Dill
Igloo
Jason
Klaus
Oyster1
Oyster2
感谢您的时间，很遗憾您的代码并不能在所有情况下正常工作。我已经更新了我的示例。使用我的新示例，您的代码会错误地处理Jason、Oyster1和Oyster2。 - kojow7
@kojow7 我已经更新了答案，但我的结果与你的略有不同 :-/ - Wizard
我有点困惑$startId是从哪里来的。如果没有它，$idQueue就没有值。 - kojow7
@kojow7 更新了源代码，并更新了对象列表，享受结果吧 :D - Wizard
啊哇，感谢您！在更新 Stack Overflow 和我的代码时，我发现两者之间存在差异。非常感谢您的帮助！ - kojow7
显示剩余2条评论
5

请注意我做了一些假设以更好地反映典型的现实网络问题

  1. 我假设在生产中，对象的完整网络过大无法全部存储在内存中。这意味着正确的方法必须仅选取一个根节点，并发现所有链接的对象，避免重复。

  2. 我假设$obj->link中的每个ID都可以使用数据库或其他查询解析为链接对象。为了简化代码（不需要编写getObjAtID()函数），我将链接接口从$obj->link = [id1, id2]改为$obj->link = [objectRef1, objectRef2]

我的代码：

function processObjNetwork(stdClass $rootObj){
    $linkedObjects = [];

    $process = function(stdClass $obj) use(&$linkedObjects, &$process){
        if(isset($linkedObjects[$obj->id])) return; // already processed
        else $linkedObjects[$obj->id] = $obj; // add to linked

        if(empty($obj->link)) return; // nothing linked; no recursion needed

        foreach($obj->link as $child) $process($child); // recursion to linked objs
    };

    $process($rootObj); // start with the root node
    return $linkedObjects;
}

返回的是所有链接对象的集合：
$linkedObjects = processObjNetwork($rootObject); // root here is 'Apple'

实时演示

假设我的前提条件是，由于地图太大，我们只从根节点开始，因此不可能发现未连接的节点，因为按定义它们与根节点没有连接。

如果您已经将所有节点存储在存储器中，那么可以通过简单地遍历每个节点并检查它是否在链接中找到来查找未连接的节点。如果没有，则表示它是未连接的。

$unlinkedObjects = [];
foreach($obj_array as $obj){ 
  // add to $unlinkedObjects anything not found in $linkedObjects 
  if(!isset($linkedObjects[$obj->id])) $unlinkedObjects[$obj->id] = $obj;
}
虽然我认为这个概念很好，但我从中检索数据的数据库将链接存储为ID号码，而不是对象引用。我认为尝试将ID转换为对象引用会有相当大的开销。 - kojow7
@kojow7 你误解了。你不需要对你的数据库结构进行任何转换。你只需要一个getter函数，从数据库中检索该id处的对象。这就是我假设你会做的（再看一下我第二个假设的第一句话）。所以要将这段代码适应你的设置，你需要用一个query($obj->link)函数来替换我的代码中的$obj->link，它返回从数据库中链接对象的数组。 - BeetleJuice
谢谢，不过我需要能够提醒用户，他们有一些尚未连接到主结构的对象。此外，尽管你给了我一个思考的方向，但目前来看，我认为任何选定的数据集最多只有几百个对象需要查看。 - kojow7
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接