[M3devel] STL algorithms? sort/unique?

[Rodney M. Bates]

On 10/01/2012 08:14 AM, Hendrik Boom wrote:
> On Sun, Sep 30, 2012 at 04:02:26PM -0500, Rodney M. Bates wrote:
>>
>>
>> On 09/29/2012 01:29 PM, mika at async.caltech.edu wrote:
>>> Well that depends on how you maintain the vector, no?
>>>
>>> SortedTable uses "treaps" which are supposed to be good data structures.
>>> Too new to have made it into Knuth, last I checked.  The amortized cost
>>> of your operations shouldn't be much worse than with your method, with
>>> the additional benefit that the sorted order is maintained dynamically.
>>>
>>> The separation of algorithms from containers sounds a bit like a bug.
>>> You have to be careful so you don't shoot yourself in the foot there!
>>> (Sorting a list using an algorithm that randomly accesses elements,
>>> say...)
>>>
>>> The Modula-3 approach is that you figure out what you want to do, pick
>>> the ADT you want that provides the minimal set of operations, import
>>> that interface, then instantiate a more carefully chosen implementation
>>> of the ADT.  The language itself obviously can be coaxed into supporting the
>>> algorithm/data structure separation but no one uses it that way as
>>> far as I know.  (Modula-3 generics are not that well explored, actually.
>>> I suspect there are many things you can do with them that no one has
>>> tried.)
>>>
>>>       Mika
>>>
>>>
>>
>> I do think the ability to easily and inadvertently create mashups with
>> horrible asymptotic efficiency problems is a fundamental problem with
>> abstractions of any kind.  Just plain old-fashioned procedural abstractions
>> give plenty of opportunity.  Write one loop and call your code O(n).
>> Call something inside the loop. That guy did the same.  Quickly, you
>> can O(n^3) etc., and nobody realizes it.
>>
>> Functional style abstractions are often just oh-so-easy to use, but
>> they can hide a lot.  Even Modula-3 Text operations, immeasurably
>> more versatile and easy than when you have to worry about allocation,
>> have created some unpleasant surprises.  Documenting the performance
>> characteristics in comments seems to be only solution.  This has been
>> done in some places by both C++ and Modula-3 library writers.
>
> It might be interesting to speculate on language  features that coul
> track performance problems the way type-checking checks types.
>

Yes, I agree.

> Not tht I expect a practical solution today or tomorrow.
>

Yes, I agree here too.

> -- hendrik
>