Sorting NativeArray failed when entities of them contains different ISharedComponentData

I have 20 entities of random integer number component `IntData`. Each one has an ISharedComponentData `Category` indicating that the random number is an odd number (gets category 1) or even number (gets category 0) The component group `cGroup` then contains both `IntData` and `Category`.

1. I print all, I sort only even number, then I print all numbers again and seeing the even part sorted. (as expected)


all : 20 [91 55 79 95 75 63 92 10 28 72 20 26 90 16 38 82 84 46 78 42]
even : 14 [10 16 20 26 28 38 42 46 72 78 82 84 90 92]
odd : 6 [91 55 79 95 75 63]
all : 20 [91 55 79 95 75 63 10 16 20 26 28 38 42 46 72 78 82 84 90 92]

Bold = sorted.

2. I sort together in `all` and prints the even and odd to check, it works only on the even number and not sorting the odd numbers. (a bug?)



all : 20 [52 70 2 38 12 74 52 36 86 44 25 99 3 31 81 11 73 19 77 35]
even : 10 [52 70 2 38 12 74 52 36 86 44]
odd : 10 [25 99 3 31 81 11 73 19 77 35]
all : 20 [2 12 36 38 44 52 52 70 74 86 25 99 3 31 81 11 73 19 77 35]
even : 10 [2 12 36 38 44 52 52 70 74 86]
odd : 10 [25 99 3 31 81 11 73 19 77 35]

Bold = not sorted.

When I restart the program enough time that I get an odd chunk in the front (I guess this is nondeterministic? Does not matter in real use anyway) this time it only works for odd number and not even numbers. (a bug?)

all : 20 [63 93 47 87 71 23 77 49 27 53 73 68 66 90 76 62 8 86 70 96]
even : 9 [68 66 90 76 62 8 86 70 96]
odd : 11 [63 93 47 87 71 23 77 49 27 53 73]
all : 20 [23 27 47 49 53 63 71 73 77 87 93 68 66 90 76 62 8 86 70 96]
even : 9 [68 66 90 76 62 8 86 70 96]
odd : 11 [23 27 47 49 53 63 71 73 77 87 93]

Bold = not sorted.

 

I see. I was looking for a way to write a job that for loop on ComponentDataArray and can do some early exit based on some conditions. But maybe I am not thinking in the ECS way.

For example in this case, find the first number that is over 50 in all data and return that number. If I have some system to sort them once, all other systems could assume something and early exit when it found something over 50 when if not I have to run through everything to make sure.

Is the ECS way is to think of all data as equal and not as a sequence? Is the best we can do is to sort in-job every time after an inject?

If that is so all search-style system will definitely cost O(n) because it at least have to go through all the data? Also might make sorting in the job irrelevant if the job has to go through everything once anyways. But at least ISharedComponentData is there to reduce the total search space.

 

Can I use "NativeSortExtension.Sort" to sort componentData and the?Is there a better way to sort the entities with Ecs?Thank you a lot!

 

Be more specific about the problem you are trying to solve.

If you are trying to sort entities within an archetype and then lock the chunks, then you can write out all the components into NativeArrays and sort the arrays and then write them back to the entities. This only works if your entities do not have shared components.

 

if there are entities with the the simple component like this:
public struct TestData : IComponentData
{
public int num;
}
how to sort the entities?And how can i excute the system just once when i want?

 

Just export the entities and component you care to sort using EntityQuery API or IJobForEachWithEntity into one or more NativeArrays (depending on what algorithm you use for sorting). Then sort, and you'll end up with a NativeArray of entities in sorted order.

If you are using NativeSortExtension.Sort, you need to define your own struct which holds an Entity and your sortable component type and has a method to do comparisons. Then you need an NativeArray of that struct and write it out using IJobForEachWithEntity.

However, if you are sorting over a singular int or float value in a particular component, you may want to use a radix sort instead. In that case, keeping the entity and component parts in separate arrays will be more performant.

 

Sorry for necro posting. Assuming we maintain 2 separate Arrays and perfrom Radix sort on the first integer one. After sorting, the second array has to have the matching indexes as the sorted one. How would you deal with that?

Thank you.

 

I actually keep more than 2 separate arrays for my use case. My use case is to sort SOA data with a floating point key, in which I sort 8 bits at a time. It goes something like this:
1) Allocate the temp count and prefix sum arrays. Count is cleared to 0. Prefix sum is unitialized.
2) Create a "front" and "back" array of a special indexing struct type which contains the 4 byte keys and the original index.
3) Create backup arrays of all the data that needs to be sorted (not necessary if your input and output can be separate arrays).
4) Run through the data and fill the count arrays and the "front" array.
5) Calculate the prefix sums of all the counts.
6) Apply the radix sort logic on the first byte to copy the "front" array to the "back" array.
7) Apply the radix sort logic on the second byte to copy the "back" array to the "front" array.
8) Apply the radix sort logic on the third byte to copy the "front" array to the "back" array.
9) For the fourth byte, instead of copying the loop variable index of the back array to the prefix sum index of the front array, you instead read the original index out of the back array and copy your backup arrays' value at that index into the original array (or copy the original array into the new output array if that's your thing).
10) Profit!