From fe4152a6949a9ec3132d1a1c08335f370989198f Mon Sep 17 00:00:00 2001 From: Xavier Chantry Date: Thu, 3 Sep 2009 22:34:39 +0200 Subject: improve compute_dep algorithm The compute_dep function I wrote for the more informative hierarchy output was very inefficient. It's much better now (10s -> 0.5s) on my box, and I get exactly the same results :) Now the big majority of the time is again spent on parsing pkgbuilds. Signed-off-by: Xavier Chantry Signed-off-by: Aaron Griffin --- cron-jobs/check_archlinux/check_packages.py | 35 +++++++++++++---------------- 1 file changed, 16 insertions(+), 19 deletions(-) (limited to 'cron-jobs/check_archlinux/check_packages.py') diff --git a/cron-jobs/check_archlinux/check_packages.py b/cron-jobs/check_archlinux/check_packages.py index 96f3181..9ffdac5 100755 --- a/cron-jobs/check_archlinux/check_packages.py +++ b/cron-jobs/check_archlinux/check_packages.py @@ -205,26 +205,22 @@ def verify_deps(name,repo,deps): return (pkg_deps,missdeps,hierarchy) -def compute_deplist_aux(pkg,deplist): - newdeplist = [] - list = [] - if pkgdeps.has_key(pkg): - list.extend(pkgdeps[pkg]) - if makepkgdeps.has_key(pkg): - list.extend(makepkgdeps[pkg]) - for dep in list: - if dep not in deplist: - newdeplist.append(dep) - deplist.append(dep) - for dep in newdeplist: - deplist2 = compute_deplist_aux(dep,deplist) - for dep2 in deplist2: - if dep2 not in deplist: - deplist.append(dep2) - return deplist - def compute_deplist(pkg): - return compute_deplist_aux(pkg,[]) + list = [] + stack = [pkg] + while stack != []: + dep = stack.pop() + if pkgdeps.has_key(dep): + for dep2 in pkgdeps[dep]: + if dep2 not in list: + list.append(dep2) + stack.append(dep2) + if makepkgdeps.has_key(dep): + for dep2 in makepkgdeps[dep]: + if dep2 not in list: + list.append(dep2) + stack.append(dep2) + return list def check_hierarchy(deph): hierarchy = [] @@ -471,6 +467,7 @@ for name,pkg in repopkgs.iteritems(): missing_makedeps.extend(missdeps) makedeph.extend(hierarchy) +print "==> checking hierarchy" dep_hierarchy = check_hierarchy(deph) makedep_hierarchy = check_hierarchy(makedeph) -- cgit v1.2.3-24-g4f1b