Re: Too Many Packages [was Re: Splitting locales...]
On Thu, Oct 05, 2000 at 11:39:58AM -0500, David Starner wrote:
> As I said, this can't be fixed. If you have n packages, files/directories
> that have information on each package are going to be O(n) in size.
> Any program (dselect, console-apt) that needs to deal with all the
> packages is going to take O(n) memory for storage and O(n log n) for
> sorting the packages. With brilliant programming, you could get dpkg
> using b-trees and stuff to get O(b log n) (where b is the number of
> packages being installed or changed), but that's going to be a lot of
> work with fragile databases and you're still going to have significant
> parts that are O(n).
Those lower bounds on sorting are incorrect. Bucket sorting and
radix sorting can reduce the sorting time to O(n), given appropriate a
priori information about the sorting keys (either a bounded space for
radix sort, or a rough distribution for an unbounded space; the bound
on bucket sorting is actually the expected sorting time).
Every programmer should know about radix sort; it predated the
advent of computers by at least 50 years, and was a fairly important
commercial application of computers for at least a decade after. In
fact, one of the three companies that formed IBM in 1914 was dedicated
to radix sort based punch card sorting machines.
Both of these algorithms are documented in Cormen, Leiserson,
and Rivest, as well as numerous other algorithms texts. I have no
doubt they will turn up in various web search engines as well.
On Thu, Oct 05, 2000 at 11:39:58AM -0500, David Starner wrote:
> It's not a problem of our package tools; it's innate in the problem.
> We may be in trouble sometime, but it doesn't mean we should give
> up now.
O(n) is not just innate in the problem, it's even deeper.
If an algorithm uses O(f(n)) space _and it consumes all of its input_,
it must take at least O(f(n)) time.
Cheers,
Bill
--
-b Disables the INTERCAL-72 random-bug feature.
--
Reply to: