9 replies to this topic

[Mihail121]

Hi!

Do you think it's possible to sort 5 objects with 7 comparisons? I'm doing a small research project where I use 5 parallel clipping planes, which need to be sorted. I define an order by taking the distance to the user. I know it's possible with 8, but each operation is important, since we're extremely low-level.

Thank you!

[Reedbeta]

Is there any way to take advantage of temporal coherence? For instance, is it possible to start with the order from last frame and just update it to get the order for the current frame?

[Mihail121]

Unfortunately no, we thought about that strategy though.

[dave_]

... I'm not sure about the implementation but I quickly knocked this up:

#include <iostream>
#include <vector>
#include <algorithm>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <Windows.h>

unsigned compares=0;

struct SomeSortable {
	SomeSortable() : v(rand()) {}

	bool operator <(const SomeSortable& rhs) const { ++compares; return v < rhs.v; }
	bool operator >(const SomeSortable& rhs) const { return v > rhs.v; }

	unsigned v;
}; 

template<typename T>
bool is_sorted(T start, T end)
{
	for(T itt = start; itt != end; ++itt)
	{
		if (itt > itt+1)
			return false;
	}
	return true;
}



int main(int argc, char *argv[])
{
	time_t t;
	time(&t);
	srand((unsigned int)t);

	std::vector<SomeSortable> sort1;
	
	const unsigned num_iterations = 100000;

	DWORD start;
	start = GetTickCount();
	for (unsigned j = 0; j < num_iterations; ++j)
	{
		for (unsigned i = 0; i < 5; ++i)
		{
			sort1.push_back(SomeSortable());
		}
		std::sort(sort1.begin(), sort1.end());

		bool sorted = is_sorted(sort1.begin(), sort1.end());
		assert(sorted);
		sort1.clear();
	}
	DWORD end;
	end = GetTickCount();

	std::cout << "std::sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

	compares = 0;
	start = GetTickCount();
	for (unsigned j = 0; j < num_iterations; ++j)
	{
		for (unsigned i = 0; i < 5; ++i)
		{
			sort1.push_back(SomeSortable());
		}
		std::stable_sort(sort1.begin(), sort1.end());

		bool sorted = is_sorted(sort1.begin(), sort1.end());
		assert(sorted);
		sort1.clear();
	}

	end = GetTickCount();
	std::cout << "std::stable_sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

	compares = 0;
	start = GetTickCount();
	for (unsigned j = 0; j < num_iterations; ++j)
	{
		for (unsigned i = 0; i < 5; ++i)
		{
			sort1.push_back(SomeSortable());
		}
		std::sort_heap(sort1.begin(), sort1.end()); 

		bool sorted = is_sorted(sort1.begin(), sort1.end());
		assert(sorted);
		sort1.clear();
	}

	end = GetTickCount();
	std::cout << "std::sort_heap number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

	return 0;
}

std::sort number of comparisons 9 duration 4047
std::stable_sort number of comparisons 8 duration 4344
std::sort_heap number of comparisons 5 duration 4016

[Mihail121]

Ehm Dave, there is most probably an error in your code. There is no sorting algorithm, that can sort 5 comparable objects with 5 comparisons, since the lower bound of the amount of comparisons for the worst case (n objects) should be greater equal log2 (n!) . In our case that's 7.

[dave_]

Heapsort has a worst case complexity of O(n log n) that should be 11.61 so I've no idea where the error is.

Edit figured it out. I wasn't dereferencing the iterators and I also forgot a make heap. That doubles the comparisons. :(
Corrected results, with more iterations

std::sort number of comparisons 9 duration 20875
std::stable_sort number of comparisons 8 duration 21266
std::sort_heap number of comparisons 10 duration 22688

[dave_]

Since they're parallel planes is it possible to sort them by 'd' first to gain some advantage?
What about caching normal . eye?
Edit: Though about it a bit more.
comparison is normal1 . eye + d1 < normal2 . eye + d2
since plane1 & plane2 are parallel normal1 == normal2
can you simplify this to just d1 < d2?
Have you already done this optimization? Is it even valid?

#include <iostream>
#include <vector>
#include <algorithm>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <Windows.h>

unsigned compares=0;


float eyex = 1.0f, eyey = 12.433f, eyez = -100.f;
struct SomeSortable {
	SomeSortable() : x_(0.58f), y_(0.58f), z_(0.58f), d_((rand() % 1000)*1.f) {}

	float distanceToEye() const
	{
		float dot = x_ * eyex
			+ y_ * eyey
			+ z_ * eyez;
		return dot + d_;

	}
	bool operator<(SomeSortable const& rhs) const
	{
		++compares;
		return distanceToEye() < rhs.distanceToEye();
	}
	bool operator>(SomeSortable const& rhs) const
	{
		return distanceToEye() > rhs.distanceToEye();
	}

	float x_, y_, z_, d_;
}; 

template<typename T>
bool is_sorted(T start, T end)
{
	for(T itt = start; itt != end-1; ++itt)
	{
		if (*itt > *(itt+1))
			return false;
	}
	return true;
}

struct Sorter
{
	Sorter() {}
	bool operator()(SomeSortable const& lhs, SomeSortable const& rhs) const
	{
		++compares;
		return lhs.d_ < rhs.d_;
	}

};


int main(int argc, char *argv[])
{
	time_t t;
	time(&t);
	srand((unsigned int)t);

	std::vector<SomeSortable> sort1;

	const unsigned num_iterations = 100000;

	DWORD start;
	start = GetTickCount();
	for (unsigned j = 0; j < num_iterations; ++j)
	{
		for (unsigned i = 0; i < 5; ++i)
		{
			sort1.push_back(SomeSortable());
		}
		std::sort(sort1.begin(), sort1.end());

		bool sorted = is_sorted(sort1.begin(), sort1.end());
		assert(sorted);
		sort1.clear();
	}
	DWORD end;
	end = GetTickCount();

	std::cout << "std::sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

	compares = 0;
	start = GetTickCount();
	for (unsigned j = 0; j < num_iterations; ++j)
	{
		for (unsigned i = 0; i < 5; ++i)
		{
			sort1.push_back(SomeSortable());
		}
		std::stable_sort(sort1.begin(), sort1.end());

		bool sorted = is_sorted(sort1.begin(), sort1.end());
		assert(sorted);
		sort1.clear();
	}

	end = GetTickCount();
	std::cout << "std::stable_sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

	compares = 0;
	start = GetTickCount();
	for (unsigned j = 0; j < num_iterations; ++j)
	{
		for (unsigned i = 0; i < 5; ++i)
		{
			sort1.push_back(SomeSortable());
		}
		std::make_heap(sort1.begin(), sort1.end()); 
		std::sort_heap(sort1.begin(), sort1.end()); 

		bool sorted = is_sorted(sort1.begin(), sort1.end());
		assert(sorted);
		sort1.clear();
	}

	end = GetTickCount();
	std::cout << "std::sort_heap number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;



	compares = 0;
	start = GetTickCount();
	for (unsigned j = 0; j < num_iterations; ++j)
	{
		for (unsigned i = 0; i < 5; ++i)
		{
			sort1.push_back(SomeSortable());
		}

		std::sort(sort1.begin(), sort1.end(), Sorter());


		bool sorted = is_sorted(sort1.begin(), sort1.end());
		assert(sorted);
		sort1.clear();
	}

	end = GetTickCount();
	std::cout << "dot sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;


	return 0;
}

[Nick]

Mihail121 said:

I'm doing a small research project where I use 5 parallel clipping planes, which need to be sorted.

Could you give us a little hint at what you're trying to do? It sounds interesting, but I can't imagine anything where sorting 5 numbers is a performance bottleneck. And it's even weirder that there's no temporal/spacial coherence...

[Hyde]

I bet you can't avoid having to do 8 compares, given that you assume nothing.

[SamuraiCrow]

The only way you can beat O(n log n) time with a sorting algorithm is if you can use the values themselves as an index and avoid the whole comparison-type sorting algorithms altogether. Eg. the radix sort.