我正在尝试以最有效的方式遍历包含多父依赖项的数组，以构建一个实现 RequireJS 的高效文件依赖脚本。
我已经使用了这个问题的答案Category Hierarchy (PHP/MySQL)成功用于 1 个父场景。然而，还有另一个限制，即一个子脚本可能依赖于多个父脚本。
例如，脚本及其依赖项的列表，目前在 PHP 中是一个数组(考虑脚本名称的唯一性和键):
╔══════════════════╦═════════════════════════════╗
║ Script Name ║ Dependencies ║
╠══════════════════╬═════════════════════════════╣
║ jquery ║ jquery-core, jquery-migrate ║
║ jquery-core ║ null ║
║ jquery-migrate ║ null ║
║ statistics ║ null ║
║ backtotop ║ jquery ║
║ jquery-circle ║ jquery ║
║ interface-slider ║ jquery-circle ║
║ test1 ║ jquery, statistics ║
║ test2 ║ test1 ║
║ test3 ║ null ║
╚══════════════════╩═════════════════════════════╝
将创建一个数组(为清楚起见，显示为 JSON)，如下所示，其中共享依赖项(例如 test1 的依赖项)将嵌套在 [' jquery-core jquery-migrate']['jquery']['statistics'] 而不是新包含 ['jquery-core jquery-migrate']['jquery statistics'][ 'test1']
allScripts = [
{
"name": "jquery-core jquery-migrate",
"children":[
{
"name":"jquery",
"children":[
{
"name":"backtotop",
"children":null
},
{
"name":"statistics",
"children":[
{
"name":"test1",
"children":[
{
"name":"test2",
"children":null
}
]
}
]
},
{
"name":"jquery-circle",
"children":[
{
"name":"interface-slider",
"children":null
}
]
}
]
}
]
},
{
"name":"test3",
"children":null
}
];
也许这需要一种最低共同祖先的方法？ http://www.stoimen.com/blog/2012/08/24/computer-algorithms-finding-the-lowest-common-ancestor/
非常感谢任何帮助!
最佳答案
我整理了一些演示代码，首先加载脚本的依赖项，然后再加载脚本。还有一些示例输出可以演示正在发生的事情。请务必阅读所有评论，因为这里要解释的内容太多了。如果您需要任何更改，请告诉我。
+1，有趣的挑战!
#!/usr/bin/php
<?php
/*
* -------
* There's room for improvement, but this is a good start.
* Let me know if you need any changes.
* -------
*
* This loads scripts with dependencies being loaded
* first, with efficiency being key here.
* Reference counting is also performed, and can be
* seen in the $loaded array. A script can be referenced
* indirectly many times through the loading of various
* scripts and their dependencies.
* Circular dependencies are handled by checking if the
* script has already been loaded. Since it can only
* be loaded once, a circular dependency is avoided.
*
* Original Sample Data:
* ╔══════════════════╦═════════════════════════════╗
* ║ Script Name ║ Dependencies ║
* ╠══════════════════╬═════════════════════════════╣
* ║ jquery ║ jquery-core, jquery-migrate ║
* ║ jquery-core ║ null ║
* ║ jquery-migrate ║ null ║
* ║ statistics ║ null ║
* ║ backtotop ║ jquery ║
* ║ jquery-circle ║ jquery ║
* ║ interface-slider ║ jquery-circle ║
* ║ test1 ║ jquery, statistics ║
* ║ test2 ║ test1 ║
* ║ test3 ║ null ║
* ╚══════════════════╩═════════════════════════════╝
*
*/
define('NO_DEPENDENCIES_LIST', TRUE); //create a list of scripts with no dependencies
//sample data, taken from OP
$scripts = array(
'jquery'=>array('jquery-core','jquery-migrate',),
'jquery-core'=>array(),
'jquery-migrate'=>array(null ),
'statistics'=>array( ),
'backtotop'=>array('jquery' ),
'jquery-circle'=>array('jquery' ),
'interface-slider'=>array('jquery-circle' ),
'test1'=>array('jquery','statistics', 'test3' ),
'test2'=>array('test1' ),
'test3'=>array( ),
);
$loaded = array(); //list of loaded scripts, order is important
$nodepends = array(); //list of scripts with no dependencies. async load perhaps?
/**
* Adds a null item to an empty array, strictly for json output
* as the OP used null instead of empty arrays in the example.
* @param array $scripts
*/
function process_array(&$scripts) {
foreach($scripts as $s=>&$data)
if (count($data)==0)
$data = array(null);
}
/**
* Finds dependents of $scriptName.
* @param array $scripts script test data
* @param string $scriptName name of script to search for dependcies for
* @param boolean $retNames TRUE to return script names, false to return ref count
* @return multitype:number unknown
*/
function find_dependencies(array $scripts, $scriptName, $retNames=FALSE) {
$ret = array();
foreach($scripts as $s=>$data)
foreach($data as $d) {
if ($d == $scriptName)
if (!$retNames) {
$ret[$s] = (isset($ret[$s])?$ret[$s] + 1 : 0);
} else {
$ret[$s] = $s;
}
}
return $ret;
}
/**
* Checks $script to see if it has already been added to the list of
* loaded scripts.
* @param string|array $script script name or array of script names
* @return boolean
*/
function script_loaded($script) {
global $loaded;
if (is_array($script)) {
foreach($script as $s)
if (!isset($loaded[$s]))
return FALSE;
}
if (is_string($script))
return isset($loaded[$script]);
return TRUE;
}
/**
* Loads a script into the $loaded array, first loading all
* dependencies, and the dependencies of those, etc., etc.
* Ensures that scripts are only loaded after all required
* scripts are loaded. Remember - order of $loaded is important!
* Return value is unimportant in this version.
*
* @param array $scripts
* @param string $script
* @param array|null $children
* @param integer $level
* @return boolean
*/
function load_script(array &$scripts, $script, &$children, $level) {
global $loaded, $nodepends;
if ($script == null)
return FALSE;
if (script_loaded($script))
return TRUE;
if (count($scripts[$script]) > 0 && $scripts[$script][0] != null) {
for($i=0;$i<count($scripts[$script]);$i++) {
if (!isset($scripts[$script][$i]))
break;
if ($i >= count($scripts[$script]))
break;
if (!script_loaded($scripts[$script][$i])) {
load_script($scripts, $scripts[$script][$i], $scripts[$script], $level+1);
}
if (isset($children[$i]) && script_loaded($children[$i]))
$children[$i] = null;
}
}
if ($scripts[$script][0]==null) {
if (!isset($loaded[$script]))
$loaded[$script] = $script;
if (NO_DEPENDENCIES_LIST)
$nodepends[$script] = $loaded[$script];
}
if (!isset($loaded[$script])) {
$loaded[$script] = 0;
} else {
$loaded[$script] = $loaded[$script] + 1;
return TRUE;
}
$loaded[$script] = $loaded[$script] + 1;
echo "load_script($script)\n";
return TRUE;
}
/**
* demo main function
* @param array $scripts - array of scripts and their dependencies: test data
*/
function main(&$scripts, &$loaded, &$nodepends) {
process_array($scripts);
foreach($scripts as $s=>$data) {
load_script($scripts, $s, $data, 0);
}
if (NO_DEPENDENCIES_LIST)
//reverse this to put the less-referenced scripts at the top
$nodepends = array_reverse($nodepends);
//here we print out a table of the $loaded array.
//it's just here for a visual representation of
//what scripts were loaded and what their dependent scripts
//are.
//The left column is the loaded script, the right column
//is a list of scripts that tried to load the script.
echo "
╔══════════════════════════════════════════════════╗
║ Loaded Scripts: with scripts that loaded them ║
╚══════════════════════════════════════════════════╝
╔══════════════════╦═══════════════════════════════╗
║ Script Name ║ Loading Scripts ║
╠══════════════════╬═══════════════════════════════╣\n";
foreach($loaded as $s=>$n) {
$d = find_dependencies($scripts, $s, TRUE);
$n = 16-strlen($s);
$s2 = implode(",", $d);
if ($s2=="")
$s2 = "null";
$n2 = 29-strlen($s2);
printf (" ║ %s%s ║ %s%s ║\n", $s, str_repeat(" ", $n), $s2, str_repeat(" ", $n2));
}
echo " ╚══════════════════╩═══════════════════════════════╝\n";
//print json of loaded scripts -- just because OP used json
print_r( json_encode($scripts, JSON_PRETTY_PRINT) );
//print array of loaded scripts: the order of this array is important;
//scripts that are depended on by other scripts are loaded first. If
//a script has no dependencies, its order is not significant.
//--
//this is the actual result that we're looking for: all scripts loaded
//with dependencies loaded first.
print_r( $loaded );
//print array of scripts that have no dependencies. Since efficiency is
//a requirement, you could async load these first, since it doesn't matter
//what order they load in.
if (NO_DEPENDENCIES_LIST)
print_r( $nodepends );
}
//run the demo
main($scripts, $loaded, $nodepends);
关于php - 高效解析多父依赖数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24507310/