[M3devel] STL algorithms? sort/unique?

[Hendrik Boom]

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.

Not tht I expect a practical solution today or tomorrow.

-- hendrik