Re: Grace and Maps (was Re: Development process in the Ada community)

["Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>]

This is just a guess based on years of experience building apps - not any
sort of statistical survey. Most of the time that you are likely to use maps
in a garden variety program, they will be used to store a relatively small
amount of data. A few dozen directory names with a few hundred files under
them, might be one example. A few hundred employees indexed by SSN, might be
another. *Most* of the time, I'd suspect you're dealing with some number
less than 1000. Probably, with today's hardware, you'd not notice the
difference if the performance were on the order of O(n!) :-) So the question
is: "Is it worth arguing over the relative performance between a few
alternate implementations?" My guess is that the best solution is to pick
one that will handle the general cases needed for maps reasonably well and
that will be easy to implement and move on.

I certainly have no objection to providing alternate structures that offer
different performance benefits, but the important thing is to get a general
solution available that will work well enough for most of the programmer's
needs. (I'd see those as being "easy to use" and "works reliably", rather
than "must have optimal performance".)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com


"Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
news:uhem1m47l.fsf@gsfc.nasa.gov...
>
> But if I just declare a map in Python, there's no way it's guaranteed
> to be best case. So I think you are saying "yes, they live with the
> O(n) worst case, and hope for the O(1) best case, and take whatever
> they actually get".
>
> Hmm. Maybe there is a way to tell Python what the hash table size
> should be, and what hash function to use? Then I can get O(1). I
> confess to never having used either a Perl or Python map.
>
> > When you'd doing things like looking up variables, it's pretty easy
> > to pay the sort time if you want to iterate over all variable names
> > in sorted order, compared to getting close to O(1) when referencing
> > a variable instead of O(logN) each time. Think "symbol table".
>
> Well, the question is, is a "typical" map in Perl or Python "close to"
> O(n), or "close to" O(1)? Anybody have any data?
>
> If I use a red-black tree, I _know_ it is O(log n).
>
> --
> -- Stephe