Графики - Как моделировать зависимые ресурсы?

Question

С библиотеками, я пытаюсь изучить структуры данных.

У меня есть эти зависимости

jquery.js->jqueryui.js 

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

Bascially, jqueryui зависит от JQuery. Bacbon зависит как от подчеркивания, так и от jquery. JQuery и подчеркивание не связаны.

Я хочу создать дерево зависимостей, чтобы вы «проливали свет» на эти отношения.

Мне сказали, что это делается на этом posted question. В частности, этот комментарий.

До тех пор, пока вы не имеют циклическую зависимость всегда можно построить лес на зависимость, которая состоит только из направленных деревьев и/или единственных узлов. На деревьях вы можете просто использовать DFS. Затем вы начинаете с добавления всех корней или отдельных узлов в очередь и добавления других ресурсов в очередь , когда их зависимость загружена. (обратите внимание, что если ресурс имеет несколько зависимостей, вы не можете моделировать свои зависимости как лес , но он остается ацикличным, и вы можете использовать аналогичный подход). - Zeta

... так что у меня есть ресурсы с несколькими зависимостями, поэтому я не могу использовать лес зависимых.

... дальнейшее обсуждение предложило ориентированный ациклический граф.

Ориентированный ациклический граф. Каждый путь от начальной точки может быть равен , но если узел имеет более одного края инцидента , вам придется ждать загрузки всех зависимостей. Кстати, I будет представлять пример 3 как P: [U-underscore, U-jquery] S: [U-подчеркивание, U-backbone-js] S: [U-jquery, U-backbone.js], с указанием исходной зависимости, но они эквивалентны

Могу ли я использовать дерево зависимостей? Если не какая структура данных предлагается моделировать сложные зависимости ... и, наконец, как ее реализовать?

Answer 1

Я считаю, что я решил эту проблему, хотя и давным-давно.Пусть зависимости описывается следующим образом:

• Модуль A
  • Модуль X
  • Модуль Y
• Модуль B
  • Модуль X
  • Модуль A
• Модуль C
  • Модуль A
  • Модуль B

Это означает, что модуль А зависит от модуля X и Y модуля - и так далее.

перебрать листья в этом лесу, и для каждого листа без зависимостей (смотрите, что до у основания), положить лист в очереди загрузки и удалить его из леса, поэтому первый проход дает:

• Модуль A
• Модуль B
  • Модуль A
• Модуль C
  • Модуль A
  • Модуль B

Очередь: Модуль Х, модуль Ю.

Второй проход:

• Модуль B
• Модуль C
  • Модуль B

Очередь: Модуль X, Y модуль, модуль А.

... и так далее. Модули, найденные в том же проходе могут быть загружены параллельно, поэтому способ представить это может быть:

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

Это означает, что модуль X и Y модуль должен быть загружен первым, и что они могут быть загружены параллельно. Остальные должны загружаться последовательно.

Мое самое большое беспокойство в связи с вышеприведенным подходом заключается в том, что он имеет сложность O (n^2). Должно быть возможно улучшить. Обнаружение циклов может быть легко осуществлено с помощью карты поиска.

Answer 2

Учитывая ваш вопрос о модульном коде без библиотеку, но используя библиотеки в качестве модулей (jQuery, jQuery-ui и т. Д.). Кажется, этот вопрос на самом деле является двумя вопросами.

1. Как вы можете понять смысл многих внешних библиотек у вас есть (без зависимости от линейной нагрузки с тегами сценария)
2. Как реализовать модульные зависимости

Чтобы ответить на первый, это немного сложнее. Для большинства модульных зависимостей требуется некоторое обертывание модулей, чтобы отслеживать их. Большинство JS-библиотек не используют такие системы в предположении, что они будут загружаться с помощью тегов скриптов (линейная загрузка). Некоторые системы, такие как require.js, предоставят модифицированную версию для совместимости, в то время как другие попытаются добавить теги сценария на страницу в предопределенном порядке. Более популярные решения - использовать инструмент построения, который объединит другой файл библиотеки, который у вас есть, в один большой файл, который будет заказывать их в правильном порядке.

Большинство библиотек являются красивыми и будут содержать их код внутри, чтобы предотвратить слияние других скриптов, которые также загружаются. Даже jQuery предлагает метод noConflict(), чтобы предотвратить синтаксис $ от клонирования того, что могут ожидать другие библиотеки (например, Zepto).

Ответ на обработку зависимостей с внешними библиотеками зависит либо от модификации библиотек, чтобы соответствовать тому, что у вас есть в модульной системе, либо иметь внешнюю систему, такую ​​как среда сборки, которая (из-за отсутствия лучшего термина) скомпилирует их в правильном порядке.

Плохая новость. Хорошей новостью является то, что код, которым вы управляете, может фактически использовать дерево зависимостей, которое работает очень хорошо. require.js - один из главных примеров этого. Хотя система, такая как CommonJS или AMD, может быть очень мощной, вы можете реализовать простой API зависимостей самостоятельно.

Забрав из Rye.js как example, как реализовать свою собственную модульную систему для вашего кода:

(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 
    }; 

}); 

Answer 3

Данные struc дифракционную картину я показал вам в моем предыдущем ответе,

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

это представляет собой 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. Затем сбор всех возможных деревьев называется forest.

поэтому у меня есть ресурсы с несколькими зависимостями, поэтому я не могу использовать лес зависимых.

Нет, вы этого не сделаете. Наличие ресурсов с несколькими зависимостями означает, что вам нужно дерево вместо очереди. Там, где это не становится (/poly-) деревом, вы имеете форму бриллианта на диаграмме DAG, например, если у вас есть модуль U-myapp, который полагается на U-jquerui и U-backbone.js - он полагается на U-jquery «дважды».

Однако, я не думаю, что нам действительно нужно использовать любые алгоритмы для целого графика.

Если не то, что структура данных предлагается моделировать сложные зависимости

Один я уже показал вам, - только моделирующие прямых зависимостей. Это позволяет вам представлять DAG (включая полиобычные леса), даже если вам это еще не нужно.

и, наконец, как его реализовать?

Я бы отправился с мемориальными обещаниями (извините, мне они нравятся). Каждое обещание представляет собой факт, что модуль был загружен и выполнен; и мы memoize (кэш) их по имени модуля, поэтому мы не запускаем их несколько раз. Тогда код довольно прост:

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"; 
    }); 
}