Ben Hinkle wrote:
<snip>
>> int arr[] = new int[10000];
>> sort!(int) ( arr,   function int(int i1,int i2) { return i1 - i2; }    );
>>
>> It is simple and works *30% faster* than D builtin sort.

By a direct translation of the DMD algorithm, or by coding up a better sorting algorithm altogether?

>> Walter, please, pay attention - C standard qsort is a piece of...

That won't work if two elements of the array can differ by more than 2147483647.  This used to be a bug with the TypeInfo for int and uint.

But your idea is like one I've had for ages.  Isn't it silly if a given D compiler has a state-of-the-art sort implementation but you can't use it, because you want to sort by something other than the type's natural ordering?

We could have, on every T[], a built-in method .sort(int function(T, T)) which would sort using the given function as a comparator.  And it could be overloaded so it can take either a function or a delegate - this would enable the comparator to be parameterised, and might be useful for database apps.

Your code would become

    arr.sort(function int(int i1, int i2) { return i1 - i2; });

Of course,

    arr.sort;

by itself would remain to denote sorting by the natural ordering.

> I could see having the generic array.sort use TypeInfo and its opCmp and have a
> templated sort in Phobos for those cases when people want a sort that can be
> optimized for their type (where the comparison function is specified some other
> way than through the TypeInfo - either explicitly at the call site as you do
> here or through opCmp operator lookup).
<snip>

Why not have opCmp operator lookup as the behaviour of the built-in one?

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on the 'group where everyone may benefit.

>
> But your idea is like one I've had for ages.  Isn't it silly if a given D compiler has a state-of-the-art sort implementation but you can't use it, because you want to sort by something other than the type's natural ordering?

My point is simple.
Existing arr.sort works now (could work better in terms of speed though)
and for simple cases, small arrays and atomic types it is pretty handy.

For other cases anyone can use given template or the like. I just don't understand the problem.

Andrew.

"Andrew Fedoniouk" <news@terrainformatica.com> wrote in message news:d0n64j$2i1u$1@digitaldaemon.com...
> >
>> But your idea is like one I've had for ages.  Isn't it silly if a given D compiler has a state-of-the-art sort implementation but you can't use it, because you want to sort by something other than the type's natural ordering?
>
> My point is simple.
> Existing arr.sort works now (could work better in terms of speed though)
> and for simple cases, small arrays and atomic types it is pretty handy.
>
> For other cases anyone can use given template or the like. I just don't understand the problem.
>
> Andrew.

I just pasted your template into std.array and recompiled phobos. I took
your main() example and stuck in
  import std.array;
and compiled (with -O -inline -release) and viola everything works great.
The only downside is that phobos isn't build with debug information so when
I try to compile my example with debug info I get the following link error:
 Error 42: Symbol Undefined _array_3std5array
So if Walter were really going to put a template into phobos he would either
have to have debug and non-debug builds of phobos or he'd have to figure out
a way around that link error.
For those who haven't poked around with Andrew's attached code the actual
sort call looks like
  int[] arr;
  ...
  sort!(int)(arr, function int(int i1,int i2) { return i1 - i2; } );

nice!

-Ben

> We could have, on every T[], a built-in method .sort(int function(T, T)) which would sort using the given function as a comparator.  And it could be overloaded so it can take either a function or a delegate - this would enable the comparator to be parameterised, and might be useful for database apps.
>
> Your code would become
>     arr.sort(function int(int i1, int i2) { return i1 - i2; });
> Of course,
>     arr.sort;
> by itself would remain to denote sorting by the natural ordering.

That would be fine, too. I have no problems with that - though I haven't any idea how easy it would be for Walter to do.

>> I could see having the generic array.sort use TypeInfo and its opCmp and
>> have a
>> templated sort in Phobos for those cases when people want a sort that can
>> be
>> optimized for their type (where the comparison function is specified some
>> other
>> way than through the TypeInfo - either explicitly at the call site as you
>> do
>> here or through opCmp operator lookup).
> <snip>
>
> Why not have opCmp operator lookup as the behaviour of the built-in one?

I don't have any problem with that, either. One advantage I see of the current impl is that the sorting routine is a single routine which cuts down on code duplication. The TypeInfo factors out the type-specific pieces of the sorting algorithm. Having the compiler make custom sorting routines per invocation using either template expansion or something would be fine but it's a trade-off decision Walter has to make. Until Walter decides on a standard way of supplying a comparison fcn, though, Andrew's template will do nicely. I'm sure other people have posted similar things. Maybe Walter will end up extending the sort property on arrays, maybe he'll toss TypeInfos entirely and go with templates, maybe he'll keep TypeInfos and use templates for custom sorting. Who knows :-)

>  int[] arr;
>  ...
>  sort!(int)(arr, function int(int i1,int i2) { return i1 - i2; } );
>
> nice!
>

Yep, exactly. This is the case when templates work.

Out of scope, IMO: boost (and STL at some extent) are too generic to be
practicaly
useful. Even basic stuff - I did by myself full implementation of custom
iterator, to use it once or twice - titanic job with zero result
practically.
onApply way better. One simple function. Little bit "enigmatic" but works.