[M3devel] STL algorithms? sort/unique?

[Jay K]

C++ already has this to some extent and has for a long time.  You can't actually request to qsort a std::list. The type system doesn't allow it. They don't come up with random access that is ridiculously slow. They come up with none at all, and it is a compilation error.

But if you are just writing loops over loops over loops over random access to large working sets and network I/O, talking to a server, that does more of the same..yeah....

What you want though is, I guess, "more composition", more flowing of data.A lot more.Tough problem...order of runtime is a factor of so many things, size of a file, or lines in the file, or tokens in a file, or number of heap allocations, or number of network I/O, or number of memory reads, or memory writes, etc....

 - Jay


> Date: Mon, 1 Oct 2012 11:18:50 -0500
> From: rodney_bates at lcwb.coop
> To: m3devel at elegosoft.com
> Subject: Re: [M3devel] STL algorithms? sort/unique?
> 
> 
> 
> 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
> >
> 
 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20121001/28248626/attachment-0002.html>