March 09, 2005 A proposal for a new, improved sort (was: A proposal for a new, improved opCmp() [WAS: Round-up of the excuses for keeping Object.opCmp, and rebuttals to them]) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ben Hinkle | 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. |
March 09, 2005 Re: A proposal for a new, improved sort (was: A proposal for a new, improved opCmp() [WAS: Round-up of the excuses for keeping Object.opCmp, and rebuttals to them]) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Stewart Gordon | >
> 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.
|
March 09, 2005 Re: A proposal for a new, improved sort (was: A proposal for a new, improved opCmp() [WAS: Round-up of the excuses for keeping Object.opCmp, and rebuttals to them]) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrew Fedoniouk | "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 |
March 09, 2005 Re: A proposal for a new, improved sort (was: A proposal for a new, improved opCmp() [WAS: Round-up of the excuses for keeping Object.opCmp, and rebuttals to them]) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Stewart Gordon | > 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 :-) |
March 10, 2005 Re: A proposal for a new, improved sort (was: A proposal for a new, improved opCmp() [WAS: Round-up of the excuses for keeping Object.opCmp, and rebuttals to them]) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ben Hinkle |
> 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.
|
Copyright © 1999-2021 by the D Language Foundation