推荐学习书目
› Learn Python the Hard Way
Python Sites
› PyPI - Python Package Index
› http://diveintopython.org/toc/index.html
› Pocoo
值得关注的项目
› PyPy
› Celery
› Jinja2
› Read the Docs
› gevent
› pyenv
› virtualenv
› Stackless Python
› Beautiful Soup
› 结巴中文分词
› Green Unicorn
› Sentry
› Shovel
› Pyflakes
› pytest
Python 编程
› pep8 Checker
Styles
› PEP 8
› Google Python Style Guide
› Code Style from The Hitchhiker's Guide
这是一个创建于 3326 天前的主题，其中的信息可能已经有所发展或是发生改变。
问题是这样的
公司有很多产品需要实现在线自动更新（可以定时检查发起更新，也可能是用户自己发起），大致的解决方案如下：
升级客户端首先获取到产品的配置信息列表，里面包含一些可能的升级路径，比如可以从 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  1
@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 的官网吧 |
Select Language