求N个集合的并集
做容器放置实验时,需要计算下载N个Images的总size(Image之间可能会有可以共享的size)。
一开始想到的是Images两两之间求交集,然后慢慢推到了容斥原理。。。时间复杂度大概就是O(NN),这显然是不可接受的。
之后想到容器有层(Layers)的概念,而层的数量是有限的,假设现所有的层共有L个[1]。
我们可以按层来计算,并且实际上的下载也是按照层来下载的。
按照每个层是否下载,最终计算的时间复杂度就是O(L*N)。
然后就在考虑,为什么两者时间复杂度差这么多呢,然后再一细想,差的多吗?那个更大呢?
问题就在这个L上,如果我们Layer划分的相对粗糙些,那最终下载的总size相比实际的并集要大,
如果我们划分的Layer越细致,那就越接近实际的并集[2],从而下载的数据size就更小。
所以,当这个Layer足够小时,使用这种分层下载的结果就会无限接近实际的交集。
但值得注意的是,二者的时间复杂度是完全不同的,因为把Layer划分到无穷小时,最终的之间复杂的就是无穷大了。
至于划分到什么程度会有O(L*N)<O(NN),这可以举几个整数集合来推理。
然后使用Map(Python就是字典)来保存这些集合是否包含某一数字,e.g.,{5:0}表示这些集合都没有整数5,{5:1}表示有[3]。
具体例子先填个坑,实验搞定了再来写= =。
忽然又想到一点。。
容斥原理的计算怎么编程实现?
注:
[1]根据A. Anwar, M. Mohamed, V. Tarasov, M. Littley, L. Rupprecht, Y. Cheng, N. Zhao, D. Skourtis, A. S. Warke, H. Ludwig, D. Hildebrand, and A. R. Butt, “Improving Docker Registry Design Based on Production Workload Analysis,” in FAST, 2018.
引用的IBM Cloud traces,其包含996种Images,共计5672个Layers。
[2]这也是T. Harter, B. Salmon, R. Liu, A. C. Arpaci-Dusseau, and R. H. Arpaci- Dusseau, “Slacker: Fast distribution with lazy docker containers,” in FAST, 2016.所提出的思想,将Layers进一步划分为Chunks来进一步加速下载。
[3]遍历累加时使用min(count, 1)来确定是否包含某一整数。
最新文章
- 深入解析PHP中的(伪)多线程与多进程
- Tips for VNCServer config
- python---difflib
- Linux scp复制文件,不需要输入密码的技巧
- Oracle EBS 术语解释
- Android学习3&mdash;电话拨号器
- python socket实例练习
- Mac Please try running this command again as root/Administrator.
- Binder机制,从Java到C (10. Binder驱动)
- ECMAScript 6 中的快捷语法汇总及代码示例
- bzoj:3392: [Usaco2005 Feb]Part Acquisition 交易
- [dotnet core]落地微服务特色的DevOps管道,持续集成/部署到kubernetes。
- select下拉框的数据回显
- MATLAB绘图功能(2) 二维底层绘图修饰
- js 拖拽 碰撞 + 重力 运动
- 关于 global nonlocal 用法
- IEC62304开发过程框架
- 对比python的进程和线程:多线程是假的
- Centos如何通过yum安装php7
- BZOJ 1486 最小圈(01分数规划)
热门文章
- 把zTree前的展开收起图标改为三角形,且只有在点击三角形图标时才展开子节点解决方案
- cli中webpack的配置详解
- web服务器端挖矿代码攻击的错误检测及排除
- springboot 部署到tomcat,获取根路径问题。空格变为%20
- U盘不能复制4G以上的单个文件如何处理?
- Scyther-Semantics and verification of Security Protocol 翻译 (第二章 2.2.2----2.3)
- 2.caffe初解
- Android.mk走读与Cmake配置
- 1. jenkins常见错误及解决方法
- 用python计算最高投标限价