Why Strings as Classes?

Nick Sabalausky a at a.a
Wed Aug 27 21:06:11 PDT 2008


"Fawzi Mohamed" <fmohamed at mac.com> wrote in message 
news:g94k2b$2a1e$1 at digitalmars.com...
> On 2008-08-27 23:27:52 +0200, "Nick Sabalausky" <a at a.a> said:
>
>> "superdan" <super at dan.org> wrote in message
>> news:g94g3e$20e9$1 at digitalmars.com...
>>> Nick Sabalausky Wrote:
>>>
>>>> "Dee Girl" <deegirl at noreply.com> wrote in message
>>>> news:g943oi$11f4$1 at digitalmars.com...
>>>>> Benji Smith Wrote:
>>>>>
>>>>>> Dee Girl wrote:
>>>>>>> Michiel Helvensteijn Wrote:
>>>>>>>> That's simple. a[i] looks much nicer than a.nth(i).
>>>>>>>
>>>>>>> It is not nicer. It is more deceiving (correct spell?). If you look
>>>>>>> at
>>>>>>> code it looks like array code.
>>>>>>>
>>>>>>> foreach (i; 0 .. a.length)
>>>>>>> {
>>>>>>> a[i] += 1;
>>>>>>> }
>>>>>>>
>>>>>>> For array works nice. But for list it is terrible! Many operations
>>>>>>> for
>>>>>>> incrementing only small list.
>>>>>>
>>>>>> Well, that's what you get with operator overloading.
>>>>>
>>>>> I am sorry. I disagree. I think that is what you get with bad design.
>>>>>
>>>>>> The same thing could be said for "+" or "-". They're inherently
>>>>>> deceiving, because they look like builtin operations on primitive 
>>>>>> data
>>>>>> types.
>>>>>>
>>>>>> For expensive operations (like performing division on an
>>>>>> unlimited-precision decimal object), should the author of the code 
>>>>>> use
>>>>>> "opDiv" or should he implement a separate "divide" function?
>>>>>
>>>>> The cost of + and - is proportional to digits in number. For small
>>>>> number
>>>>> of digits computer does fast in hardware. For many digits the cost
>>>>> grows.
>>>>> The number of digits is log n. I think + and - are fine for big
>>>>> integer. I
>>>>> am not surprise.
>>>>>
>>>>>> Forget opIndex for a moment, and ask the more general question about
>>>>>> all
>>>>>> overloaded operators. Should they imply any sort of asymptotic
>>>>>> complexity guarantee?
>>>>>
>>>>> I think depends on good design. For example I think ++ or -- for
>>>>> iterator.
>>>>> If it is O(n) it is bad design. Bad design make people say like you
>>>>> "This
>>>>> is what you get with operator overloading".
>>>>>
>>>>>> Personally, I don't think so.
>>>>>>
>>>>>> I don't like "nth".
>>>>>>
>>>>>> I'd rather use the opIndex. And if I'm using a linked list, I'll be
>>>>>> aware of the fact that it'll exhibit linear-time indexing, and I'll 
>>>>>> be
>>>>>> cautious about which algorithms to use.
>>>>>
>>>>> But inside algorithm you do not know if you use a linked list or a
>>>>> vector.
>>>>> You lost that information in bad abstraction. Also abstraction is bad
>>>>> because if you change data structure you have concept errors that 
>>>>> still
>>>>> compile. And run until tomorrow ^_^.
>>>>>
>>>>
>>>> A generic algoritm has absolutely no business caring about the 
>>>> complexity
>>>> of
>>>> the collection it's operating on.
>>>
>>> absolutely. desperate. need. of. chanel.
>>>
>>>> If it does, then you've created a concrete
>>>> algoritm, not a generic one.
>>>
>>> sure you don't know what you're talking about. it is generic insofar as 
>>> it
>>> abstracts away the primitives it needs from its iterator. run don't walk
>>> and get a dose of stl.
>>>
>>>> If an algoritm uses [] and doesn't know the
>>>> complexity of the []...good! It shouldn't know, and it shouldn't care.
>>>
>>> nonsense. so wrong i won't even address it.
>>>
>>>> It's
>>>> the code that sends the collection to the algoritm that knows and 
>>>> cares.
>>>> Why? Because "what algoritm is best?" depends on far more than just 
>>>> what
>>>> type of collection is used. It depends on "Will the collection ever be
>>>> larger than X elements?". It depends on "Is it a standard textbook 
>>>> list,
>>>> or
>>>> does it use trick 1 and/or trick 2?". It depends on "Is it usually 
>>>> mostly
>>>> sorted or mostly random?". It depends on "What do I do with it most
>>>> often?
>>>> Sort, append, search, insert or delete?". And it depends on other 
>>>> things,
>>>> too.
>>>
>>> sure it does. problem is you have it backwards. types and algos tell you
>>> the theoretical properties. then you in knowledge of what's goin' on use
>>> the algorithm that does it for you in knowledge that the complexity 
>>> would
>>> work for your situation. or you encode your own specialized algorithm.
>>>
>>> thing is stl encoded the most general linear search. you can use it for
>>> linear searching everything. moreover it exactly said what's needed for 
>>> a
>>> linear search: a one-pass forward iterator aka input iterator.
>>>
>>> now to tie it with what u said: you know in your situation whether 
>>> linear
>>> find cuts the mustard. that don't change the nature of that fundamental
>>> algorithm. so you use it or use another. your choice. but find remains
>>> universal so long as it has access to the basics of one-pass iteration.
>>>
>>>> Using "[]" versus "nth()" can't tell the algoritm *any* of those 
>>>> things.
>>>
>>> doesn't have to.
>>>
>>>> But
>>>> those things *must* be known in order to make an accurate decision of 
>>>> "Is
>>>> this the right algoritm or not?"
>>>
>>> sure. you make them decision on the call site.
>>>
>>>> Therefore, a generic algoritm *cannot* ever
>>>> know for certain if it's the right algoritm *even* if you say "[]" 
>>>> means
>>>> "O(log n) or better".
>>>
>>> utterly wrong. poppycock. gobbledygook. nonsense. this is so far off i
>>> don't have time to even address. if you want to learn stuff go learn 
>>> stl.
>>> then we talk. if you want to teach me i guess we're done.
>>>
>>>> Therefore, the algorithm should not be designed to
>>>> only work with certain types of collections.
>>>
>>> it should be designed to work with certain iterator categories.
>>>
>>>> The code that sends the
>>>> collection to the algoritm is the *only* code that knows the answers to
>>>> all
>>>> of the questions above, therefore it is the only code that should ever
>>>> decide "I should use this algorithm, I shouldn't use that algorithm."
>>>
>>> correct. you just have all of your other hypotheses jumbled.
>>>
>>> sorry dood don't be hatin' but there's so much you don't know i ain't
>>> gonna continue this. last word is yours. call me a pompous prick if you
>>> want. go ahead.
>>
>> I'll agree to drop this issue. There's little point in debating with 
>> someone
>> whose arguments frequently consist of things like "You are wrong", "I'm 
>> not
>> going to explain my point", and "dood don't be hatin'".
>
> I am with dan dee_girl & co on this issue, the problem is that a generic 
> algorithm "knows" the types he is working on and can easily check the 
> operations they have, and based on this decide the strategy to use. This 
> choice works well if the presence of a given operation is also connected 
> with some performance guarantee.
>

IMO, a better way to do that would be via C#-style attributes or equivilent 
named interfaces. I'm not sure if this is what you're referring to below or 
not.

> Concepts (or better categories (aldor concept not C++), that are 
> interfaces for types, but interfaces that have to be explicitly assigned 
> to a type) might relax this situation a little, but the need for some 
> guarantees will remain.
>

If this "guarantee" (or mechanism for checking the types of operations that 
a collection supports) takes the form of a style guideline that says "don't 
implement opIndex for a collection if it would be O(n) or worse", then that, 
frankly, is absolutely no guarantee at all.

If you *really* need that sort of guarantee (and I can imagine it may be 
useful in some cases), then the implementation of the guarantee does *not* 
belong in the realm of "implements vs doesn't-implement a particular 
operator overload". Doing so is an abuse of operator overloading, since 
operator overloading is there for defining syntactic sugar, not for acting 
as a makeshift contract.

The correct mechanism for such guarantees is with named interfaces or 
C#-style attribtes, as I mentioned above. True, that can still be abused if 
the collection author wants to, but they have to actually try (ie, they have 
to lie and say "implements IndexingInConstantTime" in addition to 
implementing opIndex). If you instead try to implement that guarantee with 
the "don't implement opIndex for a collection if it would be O(n) or worse" 
style-guideline, then it's far too easy for a collection to come along that 
is ignorant of that "psuedo-contract" and accidentially breaks it. Proper 
use of interfaces/attributes instead of relying on the existence or absense 
of an overloaded operator fixes that problem.





More information about the Digitalmars-d mailing list