求N个集合的并集

时间:2022-09-03 00:26:03

做容器放置实验时,需要计算下载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)来确定是否包含某一整数。