Sorting of uchar array of a million elements with sorted indices? about hpcsharp HOT 16 CLOSED

I've implemented the function you're after, with an input of unsigned byte array and the output of sorted indexes. The function is SortRadixReturnIndexes(). Look for it at the bottom of RadixSort.cs source file in the HPCsharp folder. I have not tested it yet - will test it this weekend. Just wanted to give you a head start of thinking about porting it from C# to C++, which should be pretty simple, since the function is self contained and doesn't call any other functions and uses nothing but arrays.

from hpcsharp.

You're welcome. Yours is a very nice solution also, as it comes with the same realization that we need to reflect something (i.e. go backwards). Both should perform nearly the same.

from hpcsharp.

There are several way to accomplish this. One possible way is to do something similar to
public static T[] SortRadix(this T[] inputArray, UInt32[] inKeys, ref UInt32[] outSortedKeys)
which is implemented in HPCsharp
where the inputArray is an array of integer indexes, incrementing from 0 to inputArray.Length-1
inKey[] would need to be modified to be UInt8[]
This SortRadix() function would return sorted keys (UInt8's) in outSortedKeys[]. Also, it would return
an output array of indexes
The current source code would need modification to support UInt8[] inKeys instead of the current
UInt32[] inKeys.

from hpcsharp.

First of all, only array elements are of uint8 but their indices have to be of uint32(to account all indices).
What modification is required for uint8 type elements?

Can't a pointer(which points first element in array) and length be passed for efficiency?

from hpcsharp.

Yes, what you are after is providing one array that is of uint8/byte type to the sorting function. The sorting function would then return and array of Int32's, which are indexes of the sorted array.
By the way, C# does not have a uchar data type, but C++ does. This HPCsharp library is a C# library and not a C++ library.
Currently, the closest functionality in this HPCsharp (C#) library is a function where you pass in an array of Int32's as the array, instead of char/byte array, along with an array of Int32 indexes. The sorting function would then sort both arrays and return both of them.
It would be pretty simple for me to modify the library to add a new function that would provide you the functionality that you're after, since instead of an array of Int32's as the input array, I would change it to be a char/byte array (along with quite a bit of functionality inside that function).

from hpcsharp.

Passing 2 arrays(data+ indices) would be an overload.
As I am developing a real-time image processing project, I am looking to deal with pointers wherever possible.
Do you know any function, which can deal with pointers also?

from hpcsharp.

Yes, pointers are possible with C#, but they don't necessarily make the code faster, and certainly not the strength of C#, and more of C++ strength. Any function using pointers has to be declared unsafe and has to be dealt with carefully because of memory management by the C# managed memory system - C# moves arrays around. Most C# developers stay away from pointers whenever possible, as it slows development down.
Do you need to code in C# for your real-time image processing project?

from hpcsharp.

Thanks for replying so promptly.
Since I am developing for ROS network. My project is on C++.
Can you share me the algorithm for index sorting at-least! (fastest for uint8 array)

from hpcsharp.

No worries. If you make a donation to this project (see at the top of Readme) or give this project another star by clicking on the star at the top, I'll crank it out in the next few days.

from hpcsharp.

Because of being a student, I have starred it.
Thanks

from hpcsharp.

ok, cool! I'll let you know when the implementation is ready.

from hpcsharp.

Wow, it is much faster than std::sort. Thank a lot.
What changes would you prefer to sort in descending manner.

from hpcsharp.

Yes, it should be many times faster than std::sort, since this is based on LSD Radix Sort and is O(N) versus O(NlgN) of std::sort. How many times faster did it turn out to be? Do the results compare?
Descending shouldn't be hard. Let me think about it and I'll let you know.
What are your plans for usage for this algorithm?

from hpcsharp.

For an uchar array of 450x800. I found this LSD Radix Sort 3 times faster than std::sort.
I would be using this for my image processing algorithm. To sort the depth map.

Let me know, if you figure out the efficient way for descend sort.
Thanks again.

from hpcsharp.

Very nice speedup! It is possible to accelerate even more by using multiple cores for the counting portion of the LSD Radix Sort algorithm. I do that currently in the HPCsharp library for several implementations, and have implemented it in C++ as well using TBB, but harder to explain. It may get you another 20%.
Very nice use of sorting for depth map.
I've just checked in a version of the sort that will do ascending or descending, without additional performance cost.

from hpcsharp.

Thanks for updating. Meanwhile I also figured out a way.
But it is more like a cheat. :D
Yours is elegant.

for (int current = 0; current < inputArray.Length; current++)
            {
                byte digit = inputArray[current];
                int index  = startOfBin[digit]++;
                outputIndexArray[inputArray.Length- 1 - index] = current;          // I changed it from'index' ->'inputArray.Length- 1 - index'
            }

from hpcsharp.