www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Xinok Sort - December 2011

reply Xinok <xinok live.com> writes:
I've released a few updates for my sorting algorithm in the past month.

https://sourceforge.net/projects/xinoksort/

Major changes:
* Added concurrency using taskPool
* Use any callable type as predicate (functions, delegates)
* Unittests
* Documentation
* Minor optimizations


I have a few more things I'd like to address before I do a pull request:

* Should I use the global 'taskPool', or a unique TaskPool object for 
concurrency?

* Is it possible to overload opDollar / __dollar at the moment? 
Otherwise, I'll replace the dollars with *.length instead.

* I can't figure out all the requirements to satisfy the condition, 
isRandomAccessRange!(). I've read through the documentation a few times 
but I'm still missing something. I've successfully tested the code for 
ranges on arrays, but not any class type.

class N(T){
	T[] arr;
	this(T[] other){ arr = other.save; }
	ref T opIndex(size_t i){ return arr[i]; }
	size_t length(){ return arr.length; }
	ref T front(){ return arr.front; }
	ref T back(){ return arr.back; }
	ref T popFront(){ arr.popFront(); }
	ref T popBack(){ arr.popBack(); }
	bool empty(){ return arr.empty; }
	N save(){ return new N(arr); }
}
static assert(isRandomAccessRange!(N!uint));
Nov 30 2011
next sibling parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Add  property to front/back/popFront/popBack/empty/save.

Also popFront/popBack need to be void return type.
Nov 30 2011
next sibling parent Xinok <xinok live.com> writes:
On 11/30/2011 8:45 PM, Andrej Mitrovic wrote:
 Add  property to front/back/popFront/popBack/empty/save.

 Also popFront/popBack need to be void return type.

Thanks. I was missing property, the void return type was a mistake. After fixing some bugs, the code is working but the benchmarks are terrible. >.< This is the benchmark compared to Phobos unstable sort: phobUSortArray: 256939 phobUSortRange: 664792 xinokSortArray: 323069 xinokSortRange: 2401659 Also a new problem, this is the primary code for concurrent sorting. It compiles just fine in release builds, but it doesn't compile in debug builds: // Start threading auto th = task!(findRunsT)(arr[0..mid], temp[0..temp.length/2]); taskPool.put(th); findRunsT(arr[mid..arr.length], temp[temp.length/2..temp.length]); th.workForce(); // End threading The compiler prints lots of errors stating several members are not accessible, for example: C:\D\dmd2\windows\bin\..\..\src\phobos\std\parallelism.d(491): Error: class std.parallelism.TaskPool member tryDeleteExecute is not accessible
Nov 30 2011
prev sibling parent =?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <xtzgzorex gmail.com> writes:
On 01-12-2011 14:26, Steven Schveighoffer wrote:
 On Wed, 30 Nov 2011 20:45:19 -0500, Andrej Mitrovic
 <andrej.mitrovich gmail.com> wrote:

 Add  property to front/back/popFront/popBack/empty/save.

 Also popFront/popBack need to be void return type.

popFront/popBack need not be property. -Steve

Anything that mutates the state of an object or does something that's significantly more expensive than retrieving a field should not be a property. This is something I still have gripes with in the language itself (see array.dup). I think it's completely broken that such design is encouraged. - Alex
Dec 01 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 30 Nov 2011 20:45:19 -0500, Andrej Mitrovic  
<andrej.mitrovich gmail.com> wrote:

 Add  property to front/back/popFront/popBack/empty/save.

 Also popFront/popBack need to be void return type.

popFront/popBack need not be property. -Steve
Dec 01 2011
prev sibling parent Xinok <xinok live.com> writes:
On 11/30/2011 8:23 PM, Xinok wrote:
 I've released a few updates for my sorting algorithm in the past month.

 https://sourceforge.net/projects/xinoksort/

 Major changes:
 * Added concurrency using taskPool
 * Use any callable type as predicate (functions, delegates)
 * Unittests
 * Documentation
 * Minor optimizations

Update (2011-12-02) * Fix: Several bugs and other issues related to sorting ranges * Fix: Use taskPool for release builds, Thread for debug builds * Added unittest for ranges * Merged all unittests into one unittest statement * makeTemp now takes size_t rather than Range The performance of ranges isn't as good as I hoped, but it's still significantly faster than Phobos stable sort. Now I'll work on implementing my code in std.algorithm and do a pull request when it's ready. Benchmark on array of 16777216 uints xinokSortArray: 6180865 xinokSortRange: 11515011 phobUSortArray: 4880857 phobUSortRange: 4514736 <- Why is sorting a range faster than an array? phobSSortArray: 104081737 phobSSortRange: Failed to compile (many functions under std.algorithm use $ when slicing)
Dec 01 2011