On Sat, May 12, 2007 at 01:53:36PM -0500, Stephen Montgomery-Smith wrote: > I believe that if this function is optimized, that practically all of the > slowness issues we have seen with pkg_add, pkg_deinstall, etc, will be > solved. Give me a few days. I think I will be able to make it work very > much faster. For starters it uses a bubble sort. I can understand why they > don't want to use a quicksort, because they want to check complete integrety > of comparison tree (i.e. that there are no internal loops), but I recall > seeing an algorithm due perhaps to one of or both of Hopcroft and Tarjan > that uses a depth first search, maybe 20 years ago, that should be much > faster, and I think I could reproduce it.
Please don't use a bubblesort, it's incredibly inefficient. Using a topological sort would be the most optimal way to do this. It's a standard algorithm: http://en.wikipedia.org/wiki/Topological_sorting http://www.cee.hw.ac.uk/~alison/ds98/node65.html We have existing code that does it (src/usr.bin/tsort/tsort.c), but one shouldn't use the code from there. tsort.c builds the actual graph in memory, which isn't needed in the case of pkg_install as long as we have functions like chkifdepends() and others which query dependency relations (these represent arcs in the graph). Thanks for looking into/solving all of this though. Thumbs up. :-) -- | Jeremy Chadwick jdc at parodius.com | | Parodius Networking http://www.parodius.com/ | | UNIX Systems Administrator Mountain View, CA, USA | | Making life hard for others since 1977. PGP: 4BD6C0CB | _______________________________________________ [email protected] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-ports To unsubscribe, send any mail to "[EMAIL PROTECTED]"
