Jump to content

  • Log In with Google      Sign In   
  • Create Account


sorting floats with index


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
21 replies to this topic

#1 cozzie   Members   -  Reputation: 1071

Like
0Likes
Like

Posted 08 January 2013 - 03:55 PM

Hi,

I'm struggling with something which sounds fairly simple... although..

 

- I have a int array containing incices of meshes, say Meshes[5] = { 3, 1, 4, 9, 2};

- these indices point to objects (meshes) with a member 'distance' (float)

- say the meshes with indices above have: 10, 30, 40, 50, 15 as distance

 

What I want to achieve is the new index (int array) sorted on the descending order of the member floats..

 

I got so far to be able to sort the int array without the floats, and I got that far to sort the floats as an array (distances).

Simply don't know how to complete this goal...

 

Here's the code that partially does this.

Can someone help me out?

 

	float *dists = new float[mNrD3dMeshesBlended];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) dists[oc] = mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam;

	float elements = sizeof(dists) / sizeof(dists[0]); 
	std::sort(dists, dists+mNrD3dMeshesBlended, std::greater<float>());

//	int elements = sizeof(mMeshIndexBlended) / sizeof(mMeshIndexBlended[0]); 
//	std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, std::greater<int>());

 

 



Sponsor:

#2 ApochPiQ   Moderators   -  Reputation: 12345

Like
1Likes
Like

Posted 08 January 2013 - 04:06 PM

I'd create a struct that holds the original index and the distance. Add an operator > which compares the distance members. Populate a std::vector with instances of the struct for each mesh index/distance combination you need. Then use std::sort on the vector, and voila :-)



#3 swiftcoder   Senior Moderators   -  Reputation: 8076

Like
4Likes
Like

Posted 08 January 2013 - 04:11 PM

I'd create a struct that holds the original index and the distance. Add an operator > which compares the distance members. Populate a std::vector with instances of the struct for each mesh index/distance combination you need. Then use std::sort on the vector, and voila :-)

As a bonus (slightly briefer) approach, you can use a std::pair<float, int> instead of the custom struct, and the default comparison operator will do the right thing (i.e. compare the float first).


Tristam MacDonald - SDE II @ Amazon - swiftcoding        [Need to sync your files via the cloud? | Need affordable web hosting?]


#4 cozzie   Members   -  Reputation: 1071

Like
0Likes
Like

Posted 08 January 2013 - 04:20 PM

Thanks for the quick reactions, I guess I'll have to dig into pairs/vectors (till now not used that much :))

Keeping in mind that this function will run each frame I render, is this the most efficient way to do this?

(looking at memory allocation for the pairs or structs)



#5 swiftcoder   Senior Moderators   -  Reputation: 8076

Like
0Likes
Like

Posted 08 January 2013 - 04:27 PM

Keeping in mind that this function will run each frame I render, is this the most efficient way to do this?
(looking at memory allocation for the pairs or structs)

 

As long as you keep the std::vector around between frames, there shouldn't be much allocation going on (only when the vector's length grows significantly). Your struct (or std::pair, for that matter) should be a very thin wrapper class, and created on the stack - no real cost to those allocations, and copying them into the vector should be similarly cheap.

 

Ideally, the sort itself should dominate the performance cost here. I presume you are not sorting a huge number of items?


Tristam MacDonald - SDE II @ Amazon - swiftcoding        [Need to sync your files via the cloud? | Need affordable web hosting?]


#6 Brother Bob   Moderators   -  Reputation: 7405

Like
1Likes
Like

Posted 08 January 2013 - 04:30 PM

You can also use a custom predicate that sorts the indices by comparing the distance values at the corresponding indices.

 

The C++11 way:

std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, [&](int a, int b) {return dists[a]<dists[b];});

 

Or the pre-C++11 way:

struct pred {
    pred(float *values) : values(values)
    {}
    
    bool operator()(int a, int b)
    { return values[a] < values[b]; }
    float *values;
};
...
std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, pred(dists));



#7 cozzie   Members   -  Reputation: 1071

Like
0Likes
Like

Posted 08 January 2013 - 04:45 PM

Wow, that looks easy (although I have do dig in and read/ study it to understand:))
But it compiles directly, thanks :)

The result is not exacly as expected, but nearly there.
It's sorting but not yet as I'd expect.

Array before sorting:

Render: 1 ,dist to cam: 163.554
Render: 3 ,dist to cam: 136.565
Render: 5 ,dist to cam: 111.131
Render: 7 ,dist to cam: 88.6002
Render: 9 ,dist to cam: 71.7635
Render: 11 ,dist to cam: 159.844
Render: 13 ,dist to cam: 132.098
Render: 15 ,dist to cam: 105.594
Render: 17 ,dist to cam: 81.5475
Render: 19 ,dist to cam: 62.849
Render: 21 ,dist to cam: 154.11
Render: 23 ,dist to cam: 150.167
Render: 25 ,dist to cam: 152.151
Render: 27 ,dist to cam: 46.3681
Render: 29 ,dist to cam: 39.37

After sort:

Render: 27 ,dist to cam: 46.3681
Render: 29 ,dist to cam: 39.37
Render: 25 ,dist to cam: 152.151
Render: 15 ,dist to cam: 105.594
Render: 17 ,dist to cam: 81.5475
Render: 19 ,dist to cam: 62.849
Render: 21 ,dist to cam: 154.11
Render: 23 ,dist to cam: 150.167
Render: 1 ,dist to cam: 163.554
Render: 5 ,dist to cam: 111.131
Render: 13 ,dist to cam: 132.098
Render: 3 ,dist to cam: 136.565
Render: 9 ,dist to cam: 71.7635
Render: 11 ,dist to cam: 159.844
Render: 7 ,dist to cam: 88.6002

Edited by cozzie, 08 January 2013 - 04:48 PM.


#8 Brother Bob   Moderators   -  Reputation: 7405

Like
0Likes
Like

Posted 08 January 2013 - 05:01 PM

From your initial set of indices, I get the impression now that your indices are not sequential. In that case, my method won't work. It assumes that index n has the distance value dists[n], while it seems like you have a set of index/distance pairs (n, dist) with arbitrary n and dist, and that has to be sorted by dist. If that's the case, then the structure approach suggested earlier will work.



#9 cozzie   Members   -  Reputation: 1071

Like
0Likes
Like

Posted 08 January 2013 - 05:07 PM

too bad, I'll have to get into that then.

Thanks for the help.

 

My gut feeling that there must be a easy way was not true then :)



#10 Paradigm Shifter   Crossbones+   -  Reputation: 4783

Like
0Likes
Like

Posted 08 January 2013 - 05:13 PM

Stick the distances and indices in a std::map<float, int> then, with the float as the key. Then when you iterate through the map you will get the indices back in order of increasing float key.
"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#11 swiftcoder   Senior Moderators   -  Reputation: 8076

Like
0Likes
Like

Posted 08 January 2013 - 05:14 PM

My gut feeling that there must be a easy way was not true then smile.png

It's really not that complicated...

std::vector< std::pair<float, int> > data;

data.push_back( std::make_pair(0.5, 12) );
data.push_back( std::make_pair(1.75, 14) );
data.push_back( std::make_pair(1.5, 4) );
data.push_back( std::make_pair(0.25, 7) );

std::sort(data.begin(), data.end());

Tristam MacDonald - SDE II @ Amazon - swiftcoding        [Need to sync your files via the cloud? | Need affordable web hosting?]


#12 Paradigm Shifter   Crossbones+   -  Reputation: 4783

Like
0Likes
Like

Posted 08 January 2013 - 05:15 PM

I think the map way is easier ;)
"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#13 ApochPiQ   Moderators   -  Reputation: 12345

Like
1Likes
Like

Posted 08 January 2013 - 05:16 PM

Stick the distances and indices in a std::map<float, int> then, with the float as the key. Then when you iterate through the map you will get the indices back in order of increasing float key.

 

This is dangerous if you might have identical distances, as one will stomp the others. You might prefer a std::multimap instead, but even then, the cost of building the tree, traversing it, and maintaining sorted order during inserts/removes is going to clobber your speed compared to just stuffing things into a vector and sorting once.



#14 Brother Bob   Moderators   -  Reputation: 7405

Like
0Likes
Like

Posted 08 January 2013 - 05:17 PM

Well, thinking about it a bit more, you can actually use my approach with some modifications: add an additional order-array and add an additional level of referencing to the comparison.

 

int *order = new int[mNrD3dMeshesBlended]; // fill this one with values from 0 and up to mNrD3dMeshesBlended-1
...
std::sort(
    order,
    order+mNrD3dMeshesBlended,
    [&](int a, int b) {
        return dists[mMeshIndexBlended[a]]<dists[mMeshIndexBlended[b]];
    }
);

The array order can, after sorting, be used to traverse the index arrays in sorted order based on distance.



#15 Paradigm Shifter   Crossbones+   -  Reputation: 4783

Like
0Likes
Like

Posted 08 January 2013 - 05:18 PM

Good point, hadn't thought about identical floats.
"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#16 alantseng   Members   -  Reputation: 102

Like
0Likes
Like

Posted 09 January 2013 - 10:24 AM

Great!

 

try a little modification

struct pred {
    pred(d3dMesh *values) : values(values)
    {}
    
    bool operator()(int a, int b)
    { return values[a].mDistToCam < values[b].mDistToCam; }
    d3dMesh *values;
};
...
std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, pred(mD3dMeshes));

 

 

You can also use a custom predicate that sorts the indices by comparing the distance values at the corresponding indices.

 

The C++11 way:

 

std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, [&](int a, int b) {return dists[a]<dists[b];});

 

 

Or the pre-C++11 way:

 

struct pred {
    pred(float *values) : values(values)
    {}
    
    bool operator()(int a, int b)
    { return values[a] < values[b]; }
    float *values;
};
...
std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, pred(dists));

 



#17 cozzie   Members   -  Reputation: 1071

Like
0Likes
Like

Posted 09 January 2013 - 02:06 PM

removed

Edited by cozzie, 09 January 2013 - 02:32 PM.


#18 cozzie   Members   -  Reputation: 1071

Like
0Likes
Like

Posted 09 January 2013 - 02:22 PM

I might have read it wrong and filled the int array with the non-sorted index, just filled it with just 0, 1, 2 etc. up to mNrD3dMeshesBlended.

Error is gone now, and here's the result up till now:

 

Before sort:

Order org: 1 ,dist to cam: 163.554
Order org: 3 ,dist to cam: 136.565
Order org: 5 ,dist to cam: 111.131
Order org: 7 ,dist to cam: 88.6002
Order org: 9 ,dist to cam: 71.7635
Order org: 11 ,dist to cam: 159.844
Order org: 13 ,dist to cam: 132.098
Order org: 15 ,dist to cam: 105.594
Order org: 17 ,dist to cam: 81.5475
Order org: 19 ,dist to cam: 62.849
Order org: 21 ,dist to cam: 154.11
Order org: 23 ,dist to cam: 150.167
Order org: 25 ,dist to cam: 152.151
Order org: 27 ,dist to cam: 46.3681
Order org: 29 ,dist to cam: 39.37
 

 

After sort:

Order: 12
Order: 13
Order: 14
Order: 7
Order: 8
Order: 9
Order: 10
Order: 11
Order: 6
Order: 4
Order: 1
Order: 3
Order: 0
Order: 5
Order: 2
 

Probably this is the order based on the new int array being 0 up to mNrD3dMeshesBlended.

Now probably have to link them all together.



#19 cozzie   Members   -  Reputation: 1071

Like
0Likes
Like

Posted 09 January 2013 - 02:34 PM

I can't find the relation yet between the output and the corresponding index of the original index/ array. The code now looks like this (please don't mind al the local variables, will pick this up later when I get the aimed output)

 

	std::ofstream before("blaorg.txt");
	for(int j=0;j<mNrD3dMeshesBlended;++j)
		before << "Unsorted: " << mMeshIndexBlended[j] << " ,dist to cam: " << mD3dMeshes[mMeshIndexBlended[j]].mDistToCam << std::endl;
	before.close();

	float *dists = new float[mNrD3dMeshesBlended];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) dists[oc] = mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam;

	int *order = new int[mNrD3dMeshesBlended]; // fill this one with values from 0 and up to mNrD3dMeshesBlended
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) order[oc] = oc; //mMeshIndexBlended[oc];

	std::sort(order, order+mNrD3dMeshesBlended, [&](int a, int b) { return dists[mMeshIndexBlended[a]]<dists[mMeshIndexBlended[b]]; });

	std::ofstream after("bla.txt");
	for(int j=0;j<mNrD3dMeshesBlended;++j)
		after << "Sorted: " << order[j] << std::endl; // << " ,dist to cam: " << mD3dMeshes[mMeshIndexBlended[j]].mDistToCam << std::endl;
	after.close();

 

The output of this in the reply above, before and after sorting.


When I look at it, it's probably bad that the indices in the "order" int array don't match up with the distances in the float array.

Shouldn't I fill the "order" int array with the unsorted index? (although giving an access violation at the moment)

 



#20 Brother Bob   Moderators   -  Reputation: 7405

Like
0Likes
Like

Posted 09 January 2013 - 02:56 PM

I apologize for my previous attempts at trying to get this right. I have partly read your question too quick, and partly been evaluating it with the wrong set of values and not seen the obvious errors. However, third times a charm; is this what you want? This time I'm even using your exact values and not some made-up test bench.

int main()
{
    int order[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
    int indices[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29};
    int values[] = {163.554, 136.565, 111.131, 88.6002, 71.7635, 159.844, 132.098, 105.594, 81.5475, 62.849, 154.11, 150.167, 152.151, 46.3681, 39.37};
   
    std::sort(
        order,
        order+15,
        [&](int a, int b){
            return values[a]<values[b];
        }
    );
    
    for(int i : order) {
        std::cout << "(" << indices[i] << ", " << values[i] << ")" << std::endl;
    }
}

The idea is to forget about the index-values of the vector you want to sort, and just do an index-sort on the vector values directly. As long as the contents of values is unchanged, the vector indices maintains its correspondence to the vector values.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS