Click here to Skip to main content
15,171,993 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
Hello, I'm using counting sort for sorting elo rating of players, I've compared many different sorting techniques and decided to use counting sort. Even if counting sort is a little slower than insertion sort, because it's more stable and consistent I've decided to use it.(by stable and consistent I mean it has a fixed time independent of the target)

Anyways, I'm still not too happy with the results , so I wanted to ask if it's possible to further optimize the below code. The below codes runes at 150-200ms. r.size() is 2million.

What I have tried:

C++
void TcpServer::sortRankCounting(std::vector<boost::shared_ptr<ServerData::character_object>>& r)
{

	if (r.size() == 0) return;//r.size() is 2 million for the sake of testing.

	int max = r[0]->elo;
	int min = r[0]->elo;

	for (int i = 0; i < r.size(); i++) { //takes 19ms
		int elo = r[i]->elo;
		if (max < elo)max = elo;
		if (min > elo)min = elo;
	}
	int range = max - min + 1;

	std::vector<int> count(range);//takes 0 ms
	std::vector<boost::shared_ptr<ServerData::character_object>> output;//takes 0 ms
	output.reserve(r.size());//takes 0ms
	for (int i = 0; i < r.size(); i++)//takes 39ms
		count[r[i]->elo - min]++;

	for (int i = 1; i < count.size(); i++)//takes 0 ms
		count[i] += count[i - 1];

	for (int i = r.size() - 1; i >= 0; i--) {//takes 63ms
		output[count[r[i]->elo - min] - 1] = r[i];
		count[r[i]->elo - min]--;
	}
	
	for (int i = 0; i < r.size(); i++) {//takes 51ms
		r[i] = output[i];
        r[i]->rank = i;
	}

}
Posted
Updated 29-Oct-21 14:26pm
v5
Comments
Patrice T 29-Oct-21 12:59pm
   
ELO ?
Like chess player ranking ?
Weird Japanese Shows 29-Oct-21 15:02pm
   
Yes, it's used in chess. But I'm planning to use it in an arena pvp game.

You could try creating locals for r.size() and count[r[i]->elo - min], but it probably won't matter if you're using a decent optimizing compiler.

There's probably some overhead caused by boost::shared_ptr. A unique_ptr would be slightly faster, and raw memory managed by new[] and delete[] slightly faster still.

But your greatest gains would come from not copying entries in r to output and back again. I don't have the patience to figure out what your uncommented code is doing to see if this suggestion makes sense, but it's gold if it does.
   
Comments
Weird Japanese Shows 28-Oct-21 18:10pm
   
Yes, creating locals doesn't matter. I'm using visual studio 2019 and I guess it handles those stuff. I've read 300+ page on c++ optimization and half of the book is already auto-handled by the compiler, lol.
And I need a shared_ptr because I use 2 containers. 1 for listing users by id and the other is listing them by rank. That's why I have to use shared_ptr instead of unique_ptr.

And unfortunately I need to copy entries from r to output and vice-versa. that's how counting sort works. I've tried several sorting algorithms. Fastest one is insert sort. 2nd fastest is counting sort(there is not a big gap between the two). Insert sort is not optimal for every situation. it's worst case speed is O(n²). Normally it shouldn't occur in my code under normal circumstances but I can't risk it since n² would consume a huge time. So I decided to use counting sort.
Regarding your comments - they do not explain why you need to use shared_ptr. If you control the lifetime of the objects then you can safely use unique_ptr. I always make sure that I do (control object lifetimes) so I never, ever use shared_ptr and I have no problems.

I think you should revise your algorithm so it never copies objects because there is really no need to. Do your sorting on a vector of raw pointers to the objects or indexes into the vector. Either way, copying and moving a simple, word-sized value will be very fast in the sort. The question becomes do you actually have to have them in ranked order? I don't know but I would seriously examine that. If you can do your logic with a vector of pointers into the vector of arrays that could simplify some things and improve performance.
   
Comments
Weird Japanese Shows 29-Oct-21 3:20am
   
Yes, unfortunately I have to have them in ranked order. I will need to show players the rank list, and if I don't keep ranked order in a container, the only other choice is sorting it in database , which is at least a hundred times slower if not more.
So I don't keep rank in database, I just calculate it from elo in the server itself.
I will sort this rank order every 5 minutes. If I could, by some miracle, achieve something like <5ms, I would do it more frequently.
Quote:
How to optimize this code for speed any further

Assuming the Elo ranking is positive values only:
- At cost of count a little larger, min can be just removed from code.
Assuming you know the range of values of Elo:
- you can set max to a constant and remove the first loop that search max.
C++
void TcpServer::sortRankCounting(std::vector<boost::shared_ptr<ServerData::character_object>>& r)
{

	if (r.size() == 0) return;//r.size() is 2 million for the sake of testing.

	int max = r[0]->elo;
	int min = r[0]->elo;

	for (int i = 0; i < r.size(); i++) { //takes 19ms
		int elo = r[i]->elo;
		if (max < elo)max = elo;
		if (min > elo)min = elo;
	}
	int range = max - min + 1;
	int range = 4000;

	std::vector<int> count(range);//takes 0 ms
	std::vector<boost::shared_ptr<ServerData::character_object>> output;//takes 0 ms
	output.reserve(r.size());//takes 0ms
	for (int i = 0; i < r.size(); i++)//takes 39ms
		count[r[i]->elo - min]++;

	for (int i = 1; i < count.size(); i++)//takes 0 ms
		count[i] += count[i - 1];

	for (int i = r.size() - 1; i >= 0; i--) {//takes 63ms
		output[count[r[i]->elo - min] - 1] = r[i];
		count[r[i]->elo - min]--;
	}
	
	for (int i = 0; i < r.size(); i++) {//takes 51ms
		r[i] = output[i];
        r[i]->rank = i;
	}

}

[update]
I would also try another thing: replace
C++
for (int i = r.size() - 1; i >= 0; i--) {//takes 63ms
    output[count[r[i]->elo - min] - 1] = r[i];
    count[r[i]->elo - min]--;
}

with
C++
for (int i = r.size() - 1; i >= 0; i--) {//takes 63ms
    output[--count[r[i]->elo - min]] = r[i];
    count[r[i]->elo - min]--;
}

or
C++
for (int i = r.size() - 1; i >= 0; i--) {//takes 63ms
    count[r[i]->elo - min]--;
    output[count[r[i]->elo - min]] = r[i];
    count[r[i]->elo - min]--;
}
   
v3
Comments
Weird Japanese Shows 29-Oct-21 19:26pm
   
I like the idea but unfortunately it wants constant attention. I need to keep track of maximum elo in the server so if it gets close to 4k , I need to increase the value. This is not my style. I like codes which are automated, instead of in need of manual operations. This makes the idea unusable for me.
Patrice T 29-Oct-21 19:31pm
   
The change for min can still apply.
Weird Japanese Shows 29-Oct-21 19:39pm
   
you're right, will try that tomorrow.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900