2

没有图书馆，我正在尝试学习数据结构。

我有这些依赖项

jquery.js->jqueryui.js

(underscores.js, jquery.js) -> backbone.js

基本上，jqueryui 依赖于 jquery。Bacbkone 依赖于下划线和 jquery。Jquery 和下划线不相关。

我想创建一个依赖树让你“阐明”这些关系。

有人告诉我这是如何在这个发布的问题上完成的。特别是这个评论。

只要您没有循环依赖项，您始终可以构建一个依赖项林，它仅由有向树和/或唯一节点组成。在树上，您可以简单地使用 DFS。然后，您首先将所有根或单个节点添加到队列中，并在加载它们的依赖项时将其他资源添加到队列中。（请注意，如果一个资源有多个依赖项，您不能将您的依赖项建模为森林，但它保持非循环，您可以使用类似的方法）。– 泽塔

...所以我确实有具有多个依赖项的资源，所以我不能使用依赖林。

...进一步的讨论提出了一个有向无环图。

有向无环图。从起点开始的每条路径都可以并行完成，但是如果一个节点有多个事件边，则您必须等待所有依赖项被加载。顺便说一句，我将示例 3 表示为 P:[U-underscore, U-jquery] S:[U-underscore, U-backbone-js] S:[U-jquery, U-backbone.js]，显示原始依赖，但它们是等价的

我可以使用依赖树吗？如果不是，建议使用什么数据结构来模拟复杂的依赖关系......最后我该如何实现它？

4

3 回答 3

1

我相信我已经解决了这个问题，尽管它是很久以前的事了。让依赖关系描述如下：

  • 模块 A
    • 模块 X
    • 模块 Y
  • 模块 B
    • 模块 X
    • 模块 A
  • 模块 C
    • 模块 A
    • 模块 B

这意味着模块 A 依赖于模块 X 和模块 Y - 依此类推。

遍历这个森林中的叶子，并且对于没有依赖关系的每个叶子（在基部查找），将叶子放入加载队列并将其从森林中删除，所以第一次通过产生：

  • 模块 A
  • 模块 B
    • 模块 A
  • 模块 C
    • 模块 A
    • 模块 B

队列：模块 X，模块 Y。

第二关：

  • 模块 B
  • 模块 C
    • 模块 B

队列：模块 X、模块 Y、模块 A。

……等等。在同一通道中找到的模块可以并行加载，因此表示这一点的一种方法可能是：

[[Module X, Module Y], [Module A], [Module B], [Module C]]

这意味着应该首先加载模块 X 和模块 Y，并且它们可以并行加载。其余的必须按顺序加载。

我对上述方法的最大担忧是它的复杂度为 O(n^2)。应该可以改进。使用查找图可以轻松检测循环。

于 2013-04-06T19:06:23.613 回答
1

考虑到您询问没有库但使用库作为模块（jQuery、jQuery-ui 等）的模块化代码，看来这个问题实际上是两个问题。

  1. 您如何理解您拥有的许多外部库（取决于使用脚本标签的线性加载）
  2. 如何实现模块化依赖

回答第一个，有点复杂。设计的大多数模块化依赖项都需要围绕模块进行一些包装以跟踪它们。大多数 JS 库不使用这样的系统，假设它们将通过脚本标签加载（线性加载）。一些系统（例如require.js）将提供修改后的版本以兼容，而其他系统则尝试以预定义的顺序将脚本标签注入页面。更流行的解决方案是使用一种构建工具，它将您拥有的不同库文件连接到一个大文件中，该文件将以正确的顺序对它们进行排序。

大多数库都很好，并且会在其中包含它们的代码，以防止破坏也加载的其他脚本。甚至 jQuery 也提供了一种noConflict()方法来防止$语法破坏其他库可能期望的内容（例如Zepto）。

处理与外部库的依赖关系的答案取决于修改库以符合您拥有的任何模块化系统或拥有一个外部系统，例如构建环境，它将（由于缺乏更好的术语）将它们编译成正确的顺序.

这就是坏消息。好消息是您控制的代码实际上可以使用运行良好的依赖关系树。require.js是这样做的一个主要例子。尽管像CommonJS或AMD这样的系统可能非常强大，但您可以自己实现一个简单的依赖 API。

以Rye.js为例，说明如何为您的代码实现自己的模块化系统：

(function(global) {

  var module_list = {};

  global.require = function (module) {
    return module_list[module];
  };

  global.define = function (module, fn) {
    modules[module] = fn();
  };

})(this);

然后你可以定义你自己的模块：

define("hello_world", function() {

  function helloWorld() {
    alert("Hello World!");
  }

  return {
    sayHello: helloWorld
  };

});

然后在另一个依赖于该模块的模块中：

define("greetings", function() {

  var hello = require("hello_world");

  function sayAll() {
    hello.sayHello();
    alert("Good-Bye!");
  }

  return {
    sayAll: sayAll
  };

});
于 2013-04-06T19:14:04.650 回答
1

我在上一个答案中向您展示的数据结构，

deps = {
    "U-jqueryui": ["U-jquery"],
    "group1": ["U-underscore", "U-jquery"],
    "U-backbone.js": ["group1"]
}

is 代表一个 DAG：

U-jquerui   U-backbone.js
     |          |
     |          v
     |       group1
     |      /     |
     v    L       v
 U-jquery    U-underscore.js

从中，您可以提取依赖关系树，例如

     root
    |    |
    v    v

U-jquery U-underscore.js

为group1. 所有可能的树的集合称为森林。

所以我确实有具有多个依赖项的资源，所以我不能使用依赖林。

不，你没有。拥有具有多个依赖项的资源仅意味着您需要一棵树而不是队列。当你的 DAG 图中有菱形时，它不再变成（多/多U-myapp）树的地方，例如，如果你有一个依赖于U-jquerui和U-backbone.js- 它依赖于U-jquery“两次”的模块。

但是，我认为我们真的不需要对整个图使用任何算法。

如果不是，建议使用什么数据结构来建模复杂的依赖关系

我已经向您展示了一个 - 只是对直接依赖项进行建模。即使您还不需要它，它也允许您表示 DAG（包括多森林）。

最后我该如何实现它？

我会选择记忆中的承诺（对不起，我喜欢它们）。每一个promise都代表一个模块已经被加载和执行的事实；我们通过模块名称记忆（缓存）它们，因此我们不会多次启动它们。那么代码就相当简单了：

var modulepromises = {};
function loadAndExecute(name) {
    if (name in modulepromises) // memoized?
        return modulepromises[name]; // we're on it already!

    var dependencies = [];
    if (name in deps)
        dependencies = deps[name].map(loadAndExecute);
    // all promises for direct dependencies (indirect deps are included) combined
    // will be fulfilled already if empty array
    var depsExecuted = Promise.when(dependencies);

    if (name.slice(0, 2) == "U-") // if a group, don't load anything
        var file = ajaxPromiseForModulesource(name);

    return modulepromises[name] = /*memoize!*/ depsExecuted.then(function() {
        if (file)
            return file.then(function(code) {
                execute(code); // eval?
                return "module "+name+" executed";
            });
        return "group loaded";
    });
}
于 2013-04-07T11:14:38.710 回答