- xml - AJAX/Jquery XML 解析
- 具有多重继承的 XML 模式
- .net - 枚举序列化 Json 与 XML
- XML 简单类型、简单内容、复杂类型、复杂内容
我有一个经典的依赖解决问题。我以为我正朝着正确的方向前进,但现在我遇到了障碍,我不确定如何继续。
在已知宇宙中(所有工件及其依赖项的缓存),每个工件和版本之间存在 1->n 关系,并且每个版本可能包含一组不同的依赖项。例如:
A
1.0.0
B (>= 0.0.0)
1.0.1
B (~> 0.1)
B
0.1.0
1.0.0
给定一组“需求约束”,我想找到可能的最佳解决方案(其中“最佳”是仍然满足所有约束的最高可能版本)。这是带有解决方案的“需求约束”示例:
solve!('A' => '~> 1.0') #=> {"A" => "1.0.1", "B" => "0.1.0"}
实际上,需求要多得多:
solve!('A' => '~> 1.0', 'B' => '>= 0.0.0', 'C' => '...', 'D' => '...')
(版本遵循semantic versioning标准)
当前的解决方案使用回溯并且性能不是很好。我做了一些挖掘,发现性能问题是由于宇宙的大小造成的。我决定尝试另一种方法,并为仅一组需求构造一个“可能性”DAG 图:
class Graph
def initialize
@nodes = {}
@edges = {}
end
def node(object)
@nodes[object] ||= Set.new
self
end
def edge(a, b)
node(a)
node(b)
@nodes[a].add(b)
self
end
def nodes
@nodes.keys
end
def edges
@nodes.values
end
def adjacencies(node)
@nodes[node]
end
end
然后,我构建了一个包含宇宙中所有可能解决方案的 DAG。这大大减少了可能性的数量,并为我提供了一个具有真实工件可能性的实际图表。
def populate(artifact)
return if loaded?(artifact)
@graph.node(artifact)
artifact.dependencies.each do |dependency|
versions_for(dependency).each do |dependent_artifact|
@graph.edge(artifact, dependent_artifact)
populate(dependent_artifact)
end
end
end
private
def versions_for(dependency)
possibles = @universe.versions(dependency.name, dependency.constraint)
# Short-circuit if there are no versions for this dependency,
# since we know the graph won't be solvable.
raise "No solution for #{dependency}!" if possibles.empty?
possibles
end
因此,根据前面的示例图,如果我有需求 'A', '>= 0.0.0'
,我的 DAG 将如下所示:
+---------+ +---------+
| A-1.0.0 | | A-1.0.1 |
+---------+ +---------+
/ \ |
/ \ |
/ \ |
/ \ |
+---------+ +---------+
| B-1.0.0 | | B-0.1.0 |
+---------+ +---------+
由于 A-1.0.0 的可能值是“B 的任何值”,但 A-1.0.1 的约束是“0.1 系列中的任何 B”。这目前正在按预期工作(使用完整的测试套件)。
换句话说,DAG 采用抽象的依赖约束并创建一个“真实的”图,其中每条边都是一个依赖关系,每个顶点(我称之为节点
)是一个实际的工件.如果存在解决方案,则它位于该图中的某处。
可悲的是,这就是我卡住的地方。我无法想出一种算法或程序来通过这张图找到“最佳”路径。我也不确定有什么方法可以检测图形是否不可解。
我做了一些研究,我认为拓扑排序 (tsort) 是我需要的过程。但是,该算法确定依赖项的插入顺序,而不是最佳解决方案。
我相当确定这是一个 np-hard 问题,并且可能会导致运行时效率低下。我虽然使用 DAG 会减少我必须做的比较次数。我这个假设错了吗?有没有更好的数据结构可以使用?
最佳答案
我不是这个问题的专家,我提出了一个不是最优的完整解决方案,因为有很多东西可以优化..
算法很简单,理想情况下是递归集。交集DFS :
算法
防御
Define: Name as String on format [ .* ]
Define: Version as String on format [ dd.dd.dd ]
Define: Revision as { Name, Version, Requirement }
Define: Range<T> as { min<T>, max<T> }
Define: Condition as { Name, Range<Version> }
Define: Requirement as Set<Revision> OR as Set<Condition>
Define: Component as { Name, Range<Version>, Requirement }
Define: System as Set<Component>
输入
Input: T as System aka basis
Input: C as Set<Condition> aka conditions to apply
初始化
Init: S as Set<Condition> = { S[i] as Condition | S[i] = {T[i].Name,T[i].Range} }
Init: Q as Stack<Condition> = { push(q) | q[i] = C[i] }
过程
for (Condition c in C)
{
S.find(c.Name).apply(c)
}
While (Q.size > 0)
{
Condition q = Q.pop()
switch (T.assert(S.find(q.Name),q))
{
case VALID:
S.find(q.Name).apply(q)
q.push(S.find(q.Name).Requirement)
case INVALID:
S.find(q.Name).set(INVALID)
case IDENTICAL:
case SKIP:
}
}
return S aka Solution
操作
Stack.push
在堆栈的前面插入一个项目
Stack.pop
从栈顶移除一个项目
System.assert(Condition a, Condition b):
if (a is INVALID) then return SKIP
else if (b.Range = a.Range) then IDENTICAL
else if (b.Range - a.Range = {}) then VALID
else INVALID
Set.find(x)
根据条件 x 搜索一个项目
Condition.apply(Condition b) = { this.Name, intersection(this.Range,b.Range) }
关于ruby - 解决依赖约束,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22615659/
@Cacheable在同一类中方法调用无效 上述图片中,同一个类中genLiveBullets()方法调用同类中的queryLiveByRoom()方法,这样即便标识了Cacheable标签,
目录 @Transaction注解导致动态切换更改数据库失效 使用场景 遇到问题 解决 @Transaction
@RequestBody不能class类型匹配 在首次第一次尝试使用@RequestBody注解 开始加载字符串使用post提交(貌似只能post),加Json数据格式传输的时候,
目录 @Autowired注入static接口问题 @Autowired自动注入普通service很方便 但是如果注入static修饰的serv
目录 @RequestBody部分属性丢失 问题描述 JavaBean实现 Controller实现
目录 解决@PathVariable参数接收不完整的问题 今天遇到的问题是: 解决办法: @PathVariable接受的参
这几天在项目里面发现我使用@Transactional注解事务之后,抛了异常居然不回滚。后来终于找到了原因。 如果你也出现了这种情况,可以从下面开始排查。 1、特性 先来了解一下@Trans
概述: ? 1
场景: 在处理定时任务时,由于这几个方法都是静态方法,在aop的切面中使用@Around注解,进行监控方法调用是否有异常。 发现aop没有生效。 代码如下:
最近做项目的时候 用户提出要上传大图片 一张图片有可能十几兆 本来用的第三方的上传控件 有限制图片上传大小的设置 以前设置的是2M&nb
我已经实现了这个SCIM reference code在我们的应用程序中。 我实现的代码确实通过了此postman link中存在的所有用户测试集合。 。我的 SCIM Api 也被 Azure 接受
我一直对“然后”不被等待的行为感到困扰,我明白其原因。然而,我仍然需要绕过它。这是我的用例。 doWork(family) { return doWork1(family)
我正在尝试查找 channel 中的消息是否仍然存在,但是,我不确定如何解决 promise ,查看其他答案和文档,我可以看到它可能是通过函数实现的,但我是不完全确定如何去做。我希望能在这方面获得一些
我有以下情况: 同一工作区中的 2 个 Eclipse 项目:Apa 和 Bepa(为简洁起见,使用化名)。 Apa 项目引用(包括)Bepa 项目。 我在 Bepa 有一个类 X,具有公共(publ
这个问题已经有答案了: Why am I getting a NoClassDefFoundError in Java? (31 个回答) 已关闭 6 年前。 我正在努力学习 spring。所以我输入
我正在写一个小游戏,屏幕上有许多圆圈在移动。 我在两个线程中管理圈子,如下所示: public void run() { int stepCount = 0; int dx;
我在使用 Sympy 求解方程时遇到问题。当我运行代码时,例如: 打印(校正(10)) 我希望它打印一个数字 f。相反,它给我错误:执行中止。 def correction(r): from
好吧,我制作的每个页面都有这个问题。我不确定我做错了什么,但我所有的页面都不适用于所有分辨率。可能是因为我使用的是宽屏?大声笑我不确定,但在小于宽屏分辨率的情况下,它永远不会看起来正确。它的某些部分你
我正在尝试像这样进行一个非常简单的文化 srting 检查 if(culture.ToUpper() == "ES-ES" || "IT-IT") { //do something } else
Closed. This question is off-topic. It is not currently accepting answers. Learn more。 想改进这个问题吗?Upda
我是一名优秀的程序员,十分优秀!