Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualJuliean

Posted 21 April 2013 - 11:16 AM

Thanks for the input,

 

but unfortunately the radix sort performs even worse (takes almost twice the time), but thats probably due to my bad implementation:

 


void acl::gfx::radixsort(ParticleEmitter::DepthVector::iterator first, ParticleEmitter::DepthVector::iterator last, int factor)
{
	// partitionieren
	std::map<int, std::vector<int> > buckets;
	for (ParticleEmitter::DepthVector::const_iterator i = first; i != last; ++i) {
		// get digit and map to bucket
		if (factor == 10) buckets[i->depth%factor].push_back(i->depth);
		else buckets[(i->depth/(factor/10)) %10].push_back(i->depth);
	}
 
	// collect
	ParticleEmitter::DepthVector::iterator copyfirst = first;
	for (int i = 0; i < 10; ++i) {
		for (std::vector<int>::const_iterator it = buckets[i].begin(); it != buckets[i].end(); )
			// collect and apply changes
				copyfirst++->depth = *it++;
	}
 
 
	if (factor > std::max_element(first, last, ParticleSorter())->depth) return;
	radixsort(first, last, factor *= 10);
}

Do you maybe have a better radix implementation so I could give it another shot? My struct now uses an int as key:

 

		struct ParticleDepth
		{
			int index;
			int depth;
		};

#2Juliean

Posted 21 April 2013 - 11:16 AM

Thanks for the input,

 

but unfortunately the radix sort performs even worse (takes almost twice the time), but thats probably due to my bad implementation:

 


void acl::gfx::radixsort(ParticleEmitter::DepthVector::iterator first, ParticleEmitter::DepthVector::iterator last, int factor)
{
	// partitionieren
	std::map<int, std::vector<int> > buckets;
	for (ParticleEmitter::DepthVector::const_iterator i = first; i != last; ++i) {
		// get digit and map to bucket
		if (factor == 10) buckets[i->depth%factor].push_back(i->depth);
		else buckets[(i->depth/(factor/10)) %10].push_back(i->depth);
	}
 
	// collect
	ParticleEmitter::DepthVector::iterator copyfirst = first;
	for (int i = 0; i < 10; ++i) {
		for (std::vector<int>::const_iterator it = buckets[i].begin(); it != buckets[i].end(); )
			// collect and apply changes
				copyfirst++->depth = *it++;
	}
 
 
	if (factor > std::max_element(first, last, ParticleSorter())->depth) return;
	radixsort(first, last, factor *= 10);
}

Do you maybe have a better radix implementation so I could give it another shot? My struct now uses an int as key:

 

		struct ParticleDepth
		{
			int index;
			float depth;
		};

#1Juliean

Posted 21 April 2013 - 11:15 AM

Thanks for the input,

 

but unfortunately the radix sort performs even worse (takes almost twice the time), but thats probably due to my bad implementation:

 


void acl::gfx::radixsort(ParticleEmitter::DepthVector::iterator first, ParticleEmitter::DepthVector::iterator last, int factor)
{
	// partitionieren
	std::map<int, std::vector<int> > buckets;
	for (ParticleEmitter::DepthVector::const_iterator i = first; i != last; ++i) {
		// get digit and map to bucket
		if (factor == 10) buckets[i->depth%factor].push_back(i->depth);
		else buckets[(i->depth/(factor/10)) %10].push_back(i->depth);
	}
 
	// collect
	ParticleEmitter::DepthVector::iterator copyfirst = first;
	for (int i = 0; i < 10; ++i) {
		for (std::vector<int>::const_iterator it = buckets[i].begin(); it != buckets[i].end(); )
			// collect and apply changes
				copyfirst++->depth = *it++;
	}
 
 
	if (factor > std::max_element(first, last, ParticleSorter())->depth) return;
	radixsort(first, last, factor *= 10);
}

Do you maybe have a better radix implementation so I could give it another shot?


PARTNERS