用户工具

站点工具


doc:d:dependency

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
doc:d:dependency [2013/06/04 11:16]
IOU
doc:d:dependency [2013/06/07 12:51] (当前版本)
IOU
行 1: 行 1:
 +====== 量化 Ports 的紧致程度 ======
  
 +FreeBSD 的 Ports 管理是透明的,读者可参考 [[software:​p:​pkg_cutleaves|]] 一文。用户在 /var/db/pkg 里可以查看已安装的 ports。对于那些“终极”ports(即,没有其他 ports 依赖于该 port),其目录下没有 +REQUIRED_BY 文件;而对于每个“非终极” port,其目录下,可以通过 +REQUIRED_BY 文件了解这个 port 被哪些其他的 ports 所依赖,进而统计出该 port 在依存关系形成的 DAG 中的**入度**(in-degree,即在有向非循环图中,指向某结点的边的个数。具体请参阅 [[software:​p:​pkg_cutleaves|]] 一文中的 DAG)。
 +
 +
 +例如,在我所安装的 ports 里,有两个 ports 依赖于 R-3.0.1。
 +
 +<​code>​
 +jansen@~$ cat /​var/​db/​pkg/​R-3.0.1/​+REQUIRED_BY ​
 +ess-13.05_1
 +rpy-1.0.3_28
 +</​code>​
 +
 +在 [[software:​p:​pkg_cutleaves|]] 一文中,作者介绍了 ports 之间的依存关系,这里不再赘述。对于那些非终极 ports,我们希望它们的被利用率越高越好,即越紧致越好。试想一下,所安装的 ports 里,如果有一大堆非终极 ports 只被依赖了一次,ports 之间的依存关系就会显得很松散。
 +
 +本文试图对已安装 ports 的紧致程度进行量化,以便于宏观地了解 ports 依存关系,进而对它进行优化。
 +
 +===== 主要算法 =====
 +主要算法很简单,就是对 /var/db/pkg 里的每个 port 进行考察,记录其被依赖的次数。紧致程度通过平均依赖次数(即,平均入度)来量化:我们分别给出了非终结 ports 的紧致程度 b,以及所有 ports 的紧致程度 a。显然后者严格小于前者,即 a<b。
 +
 +
 +对紧致程度的评估,我们采用这样的标准:**a 越大越好。同时,区间 [a,b] 越短越好**。
 +
 +
 +例如,在我所安装的 403 个 ports 里,终极 ports 有 94 个,其他为非终极的。依赖次数最高到 218 次,紧致程度为 [13.56575,​17.69255]。具体统计结果如下,
 +
 +<​code>​
 +1) There are totally 403 installed ports, in which 94 ports are final, and 309 are non-final ports.
 +The sum of all in-degrees is 5467.
 +The average in-degree of non-final ports is 17.69255.
 +The average in-degree of all ports is 13.56575.
 +
 +
 +2) The maximum in-degree is 218, for instance, the port of pkgconf-0.9.2_1.
 +
 +
 +3) The distribution of in-degree of all installed ports
 +
 +in-degree ​       Number of ports
 +----------------------------------
 +0                94
 +1                36
 +2                69
 +3                41
 +4                13
 +5                11
 +6                11
 +7                13
 +8                7
 +9                4
 +10               6
 +11               3
 +12               3
 +13               1
 +14               1
 +15               3
 +...
 +218              1
 +----------------------------------
 +</​code>​
 +
 +为了验证结果的正确性,将 Number of ports 一列求和,看是否与所安装 ports 的总数吻合。
 +
 +===== BASH 脚本 =====
 +
 +欢迎坛子里的朋友对它进行改进(我应该把注释写得更详细些)。
 +
 +<​code>​
 +#​!/​usr/​local/​bin/​bash ​      
 +# Purpose: We study the in-degree of each port, which is described ​
 +# by the number of REQUIRED_BY other ports. The distribution of 
 +# in-degree, as well as the average in-degree of ports, are overviewed. ​
 +#          ​
 +# Author: Jansen
 +# Date: 06-01-2013
 +#
 +###
 +
 +# The directory of installed ports
 +PortsDir="/​var/​db/​pkg"​
 +# The number of installed ports
 +NumOfPorts=`ls -l $PortsDir | awk 'END{ print NR }'`
 +# Alternative method of getting NumOfPorts
 +#​NumOfPorts=`ls -l $PortsDir | wc | awk '{ print $1 }'`
 +
 +
 +let NumOfPorts-=1
 +# Output the statistics of dependency
 +echo -e "​\n"​
 +echo -n 1\) There are totally $NumOfPorts installed ports, in which  ​
 +
 +# Examine the file of "​+REQUIRED_BY"​ of each port, if it exists,
 +# to survey the number of dependency on this port.
 +# The sample size of dependency n is recorded in PortsDist[n].
 +DepsFile="​+REQUIRED_BY"​
 +
 +# The initialization of sum of in-degrees
 +SumOfDegrees=0
 +
 +# The initialization of maximum in-degree
 +MaxIdx=0
 +
 +for i in $( ls -l $PortsDir | awk '{ print $9 }' ); do
 +    LastFile=`basename ls $PortsDir/​$i/​+* | awk 'END{ print }'`
 +    if [ $LastFile = $DepsFile ]; then
 +        NumOfDeps=`cat $PortsDir/​$i/​$DepsFile | awk 'END{ print NR }'`
 +        #​NumOfDeps=`cat $PortsDir/​$i/​$DepsFile | wc | awk '{ print $1 }'`
 +        PortsDist[$NumOfDeps]+=1
 +        let SumOfDegrees=$SumOfDegrees+$NumOfDeps
 +        if [ $MaxIdx -lt $NumOfDeps ]; then
 +            MaxIdx=$NumOfDeps
 +            MostRequirediPort=$i
 +        fi
 +    else PortsDist[0]+=1
 +    fi
 + done
 +
 +# The number of non-final ports
 +let NumOfNonFinalPorts=$NumOfPorts-${#​PortsDist[0]}
 +echo \ ${#​PortsDist[0]} ports are final, and $NumOfNonFinalPorts are non-final ports.
 +echo The sum of all in-degrees is $SumOfDegrees.
 +
 +# The average in-degree
 +MeanDegree=`echo "​scale=5;​ $SumOfDegrees/​$NumOfNonFinalPorts"​ | bc`
 +MeanDegree4All=`echo "​scale=5;​ $SumOfDegrees/​$NumOfPorts"​ | bc`
 +
 +echo The average in-degree of non-final ports is $MeanDegree.
 +echo The average in-degree of all ports is $MeanDegree4All.
 +echo -e "​\n"​
 +
 +
 +# The maximum in-degree
 +#let MaxDegree=${#​PortsDist[@]}-1 # it is weired that this method yields a wrong result!
 +MaxDegree=$MaxIdx
 +echo 2\) The maximum in-degree is $MaxDegree, for instance, the port of $MostRequirediPort.
 +echo -e "​\n"​
 +
 +# The distribution of in-degree of all installed ports
 +echo 3\) The distribution of in-degree of all installed ports
 +echo -e "​\n"​
 +echo -e "​in-degree\t Number of ports"
 +echo ----------------------------------
 +for j in $(seq 0 $MaxDegree);​ do
 +    echo -e "​$j\t\t ${#​PortsDist[$j]}"​
 +done
 +echo ----------------------------------
 +echo -e "​\n" ​  
 +</​code>​
 +
 +===== 效果图 =====
 +
 +{{:​doc:​d:​portsdist.png|}}
/data/vhosts/wiki-data/pages/doc/d/dependency.txt · 最后更改: 2013/06/07 12:51 由 IOU