Suggestion for algorithm improvement

[Steven Michalske]

i love it, it seems to work great.

its going in to the edge now

hardkrash

On Wednesday 21 January 2004 9:13 am, Erik Søe Sørensen wrote:
> Hi all.
>
> 'lunar update' took so long time on my machine that I thought something
> looped.  I found that it was sort_by_dependency() that consumed much
> time, and my first thought (after having done some tracing) was that
> there was some cyclic dependencies.
>
> I didn't find any of those, but I did find that the algorithm revisited
> parts of the dependency graph - some parts are revisited *many* times
> (perl, m4 and automake for instance) because of the simple depth-first
> traversal the function does.
> The algorithm had exponential complexity.
>
> By keeping track of what parts of the graph has already been visited,
> though, the complexity could be improved.
>
> The following version does this (lines with '#NEW' are new):
>
> # function : sort_by_dependency
> # usage    : LIST=$(sort_by_dependency $LIST)
> # purpose  : return a LIST sorted by dependency
> sort_by_dependency() {
>    debug_msg "sort_by_dependency ($@)"
>
>    included="" #NEW
>
>    recurse() {
>      debug_msg "Recurse $*"
>      for MOD in $* ; do
>        if echo "$included" | grep -qFx "$MOD" ; then #NEW
>          debug_msg "Cutoff: $MOD"                  #NEW
>        else                                        #NEW
>        LIST=$(grep ^$MOD: $DEPENDS_STATUS | grep ":on:" | cut -d: -f2)
>        for DEP in $LIST ; do
>          echo $MOD $DEP
>        done
>        included=$included$'\n'$MOD  #NEW
>        recurse $LIST
>      fi  #NEW
>      done
>    }
>
>    ALL=$(recurse $* | tsort | tac)
>    for DEP in $ALL ; do
>      if echo " $* " | grep -q " $DEP " ; then
>        echo $DEP
>      fi
>    done
> }
>
> Opinions?
>
> /Erik
>
> _______________________________________________
> Lunar mailing list
> Lunar at lunar-linux.org
> http://dbguin.lunar-linux.org/mailman/listinfo/lunar