On Thu, 07 Oct 2010 16:23:47 -0400, Rainer Deyke <rain...@eldwood.com>
wrote:
On 10/7/2010 13:57, Andrei Alexandrescu wrote:
On 10/7/10 14:40 CDT, bearophile wrote:
Another solution is just to accept O(n) as the worst complexity for
the "in" operator. I don't understand what's the problem in this.
That means we'd have to define another operation, i.e. "quickIn" that
has O(log n) bound.
Why?
I can't say I've ever cared about the big-O complexity of an operation.
Then you don't understand how important it is. Here is an example of how
caring about the big O complexity cut the runtime of dmd to about 1/3:
http://d.puremagic.com/issues/show_bug.cgi?id=4721
big O complexity is very important when you are writing libraries. Not so
much when you are writing applications -- if you can live with it in your
application, then fine. But Phobos should not have these problems for
people who *do* care.
What I'd suggest is to write your own function that uses in when possible
and find when not possible. Then use that in your code.
-Steve
