Why Strings as Classes?

superdan super at dan.org
Tue Aug 26 12:29:33 PDT 2008


Robert Fraser Wrote:

> superdan wrote:
> >> No, the SCALABLE opIndex runs in O(1). The CORRECT opIndex can run in 
> >> O(n^n) and still be correct.
> > 
> > stepanov has shown that for composable operations the complexity must be part of the specification. otherwise composition easily leads to high-order polynomial that fail to terminate in reasonable time. opIndex is an indexing operator expected to run in constant time, and algorithms rely on that. so no. opIndex running in o(n^n) is incorrect because it fails it spec.
> 
> Um.. . how would one "show" that. I'm not talking theoretical bullshit 
> here, I'm talking real-world requirements.

hey. hey. watch'em manners :) he's shown it by putting stl together.

> Some specs of operations 
> (composable or not) list their time/memory complexity. Most do not. 
> They're still usable. I agree that a standard library sort routine is 
> one that *should* list its time complexity. My internal function for 
> enumerating registry keys doesn't need to.

sure thing.

> > here you hint you don't understand what i'm talking about indeed. neither of java, c#, or tango define a[n] to run in o(n). they define named functions, which i'm perfectly fine with.
> 
> I guess I didn't understand what you were saying because you _never 
> mentioned_ you were talking only about opIndex and not other functions.

well then allow me to quote myself: "oopsies. houston we got a problem here. problem is all that pluggable sort business works only if it can count on a constant time opIndex. why? because sort has right in its spec that it takes o(n log n) time. if u pass LinkedList to it you obtain a nonsensical design that compiles but runs afoul of the spec. because with that opIndex sort will run in quadratic time and no amount of commentin' is gonna save it from that."

> I don't see the difference between a[n] and a.get(n); the former is just 
> a shorter syntax.

wrong. the former is used by sort. the latter ain't.

> The D spec certainly doesn't make any guarantees about 
> the time/memory complexity of opIndex; it's up to the implementing class 
> to do so.

it don't indeed. it should. that's a problem with the spec.

> In fact, the D spec makes no time/memory complexity guarantees 
> about sort for arbitrary user-defined types, either, so maybe you 
> shouldn't use that.

makes guarantees in terms of the primitive operations used.

> > funny you should mention that. window manager in windows 3.1 worked exactly like that. users noticed that the more windows the opened, the longer it took to open a new window. with new systems and more memory people would have many windows. before long this became a big issue. windows 95 fixed that.
> > 
> > never misunderestimate scalability.
> 
> I don't know enough about GUI programming to say for sure, but that 
> suggests a window manager shouldn't be written using linked lists. It 
> doesn't suggest that getting a value from an arbitrary index in a linked 
> list is useless (in fact, it shows the opposite -- that it works fine -- 
> it just shows its not scalable).

problem's too many people talk without knowin' enuff 'bout stuff. there's only a handful of subjects i know any about. and i try to not stray. when it come about any stuff i know i'm amazed readin' here at how many just fudge their way around.



More information about the Digitalmars-d mailing list