升级客户端首先获取到产品的配置信息列表,里面包含一些可能的升级路径,比如可以从 1.1-1.2 升级到 1.5 ,并且需要包含一些依赖的其他组件或者数据库啊什么的内容包(这些当然也会当成是一个产品来升级),所以就有如下问题:
一个产品 A 如果升级的话,可能一次无法完成升级,需要从中间版本过渡,如 1.1 升级到 1.8 ,需要先升级到 1.5 ,然后再从 1.5 升级到 1.8 ,如何在配置的路径中找到最优的升级路径。配置的路径就是一些可实现升级的路径,如: from 1.1-1.2 to 1.5 , from 1.3 to 1.4 , from 1.4-1.7 to 1.8 ,等等。
这个有什么好的算法解决呢?
一个产品 A 如果需要升级到如上所述的 1.8 的话,首先需要升级到 1.5 ,然后再升级到 1.8 ,而且在每一次升级过程中还需要升级依赖的其他产品,如 A 从 1.1 升级到 1.5 ,需要将 B 升级到 1.9 ,将 C 升级到 2.1 ,这又会导致在升级 B 和 C 的时候,又需要安装他们的依赖。
那么用什么数据结构和算法来解决这个问题呢?
1
domty 2015-10-22 15:54:03 +08:00
1. 第一个 把每生一次的权设为 1 的话,就是当前版本到最高版本的最短路径把?
2. 给个我的理解,可以参考 android 的 google play 服务。设置一个专门的提供服务的软件 d ,所有的软件升级统一依赖这个服务软件 d ,这样就可以把每个软件对其他多个软件的依赖转为单对软件 d 的依赖。在升级当前软件后发现缺少依赖的服务的话直接提示用户升级软件 d 到最新版本就好。 |
2
sunway1988 OP @domty 感谢回答:
1. 通过将升级路径构造“图”数据结构可以找到最短路径,这样解决很好。 2. 产品是相互独立的,每个产品都有特定的依赖,怎么实现统一依赖软件 d 呢? 比如一套系统由 A , B , C , D 组成,如果 A 升级需要依赖 BCD 的版本,另一套系统由 E , F , G , H 组成, E 升级需要依赖 FGH 的版本。 |
3
domty 2015-10-22 17:18:09 +08:00
@sunway1988
第二个我只是提供一种参考方式,因为你提的需求恰好让我想到了 google play 服务框架的做法。 首先要确定每套系统到底依赖的是什么东西。 *比如一套系统由 A , B , C , D 组成,如果 A 升级需要依赖 BCD 的版本,另一套系统由 E , F , G , H 组成, E 升级需要依赖 FGH 的版本。* 你可以认为唯一被依赖软件(假设为 d)是一个被所有软件所共享的工具箱,当其他软件需要使用一些不是自己的动能的时候,就去工具箱找。所以当每个软件中存在除本身外还被其他软件所需要的功能的时候,这个功能就应该是可被所有软件共享的,就应该被放到工具箱(软件 d)里。 |
4
wencan 2015-10-22 17:34:20 +08:00
如果是 linux ,可以考虑自建仓库
|
5
sunway1988 OP @domty 我受到启发可以通过树的建立和后续遍历(假设以二叉树为例)来解决:
首先根据升级路径建树: 假设需要升级 A ,则 A 为根节点, A 依赖于 B , C , D ,则 BCD 依次为 A 的子节点,构成一棵树; 同样升级 B , C , D 时,也有相应的依赖,假设是存在没有任何依赖的软件(主要通过配置文件约束实现),那么必然上述过程会结束,也就是存在叶子节点。 然后先子节点后根节点 /或者按层从下到上的顺序遍历上面建的树: 那么必然是被依赖的先升级,然后再升级有依赖的(但是此时依赖已经完成升级了,尽管大胆升级)。 由此,就可以将存在依赖关系转化为升级顺序,这样在升级时,就可以只关注自己,而不用关心依赖了,因为依赖已经完成升级了。 以上方案,如何? |
6
sunway1988 OP |
7
domty 2015-10-22 17:56:47 +08:00
@sunway1988
可以啊,就是先生成一个依赖树,然后子节点先于父节点升级(后续遍历) 但是要注意一点,设置依赖关系的时候不要设错,否则你的树可能就变成一个环了。最后可能造成类似死锁的东西。 比如 a 依赖 b , b 依赖 c ,如果设置错了 c 依赖 a ,你的这个升级循环就找不到子节点了 |
8
xylophone21 2015-10-22 18:03:14 +08:00
移植一个软件包管理系统吧,看看 dpkg , pip 神马的是怎么实现的。
|
9
sunway1988 OP @domty 是啊,不能存在互相依赖,这个可以通过配置文件约束实现。而且一般现实情况也是不会存在这样互相依赖情形的。
|
10
sunway1988 OP @xylophone21 这是不是太复杂了一点,短时间能否实现?
|
11
sunway1988 OP @xylophone21 这个在哪可以找到参考,搜索出来基本都是如何使用的
|
12
sunway1988 OP 最后总结一下,主要实现方案如下:
1. 首先,根据配置文件中所有的升级路径创建图,权值设为 1 ; 2. 根据上面创建的图,寻找最短路径,即为升级的最优路径; 3. 依次(反序,即先高版本的升级路径,假设 A 需要 1.0-1.3-1.5 ,则先处理 1.3-1.5 ,后处理 1.0-1.3 )判断上述产品升级的依赖情况,如有依赖,则将该产品升级信息入栈,假设记为{‘ A ’, ‘ 1.0 ’,‘ 1.3 ’},即 A 由 1.0 升级到 1.3 ,然后按照上述方式判断 A 的依赖的升级路径和是否存在依赖,后面的操作同 A ; 4. 依次将升级情况入栈,最终栈中保存了升级的先后顺序,依次出栈并完成升级,此时依赖关系已经转化为了升级顺序,只需要专注升级自身即可。 感谢各位的回答,谢谢! |
13
xylophone21 2015-10-23 11:39:58 +08:00
忽然发现既然你发在 Python 节点下,那你的那些模块都是 Python 模块?那是不是自己建一个 pip 的服务器,用 pip 管理就可以了?
至于看资料,就看 pip 的官网吧 |