On Fri, 12 Mar 2010, John M McIntosh wrote:
10 or 15 years back I look a look at the SortedCollection logic with an eye to
improve it.
Oddly I found the folks who wrote it had a good understanding of how the code
becomes bytecodes and
how that impacts performance. My attempts made things worst, so good luck.
Quicksort has worse performance than merge sort in dynamic languages
(and in general when comparison costs more than minimal), because it makes
more comparisons.
The simple quicksort performs really bad (O(n^2)) if there are only a
few different elements. A 3-way partitioning algorithm could perform much
better in general, but I think it'd be still slower than merge sort.
Here is a bug report which is pretty naive, but shows the effect of the
few different elements case:
http://code.google.com/p/pharo/issues/detail?id=1718&q=sort&colspec=ID%20Type%20Status%20Summary%20Milestone%20Difficulty
Squeak/Pharo's merge sort implementation is highly optimized. The merge
algorithm compiles to pure bytecodes and primitive sends.
Levente
Personally I'd choose the font rendering path, since there is lots of *stuff*
required to run to splash a
character glyph to Display.
On 2010-03-12, at 4:46 PM, Julian Fitzell wrote:
On Sat, Mar 13, 2010 at 12:23 AM, Levente Uzonyi <[email protected]> wrote:
- SortedCollection: just deprecate it (or replace it's crappy quicksort
implementation if you really want to improve it. But I think it's useless)
You shouldn't deprecate it... it's ANSI. :)
But it's implementation could certainly be improved...
Julian
_______________________________________________
Pharo-project mailing list
[email protected]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
--
===========================================================================
John M. McIntosh <[email protected]> Twitter: squeaker68882
Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com
===========================================================================
_______________________________________________
Pharo-project mailing list
[email protected]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________
Pharo-project mailing list
[email protected]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
