Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualGeometrian

Posted 03 February 2013 - 01:13 PM

Hi,

I have an array of structs, each containing three elements:

class A { public: unsigned int x, y, z; };
//...
A* long_list; //Has at least 250,000 elements

. . . and I need to find a set of the unique structs in long_list.

I try to construct the set as follows:

unordered_set<A> mapping(/*passing in long_list's length to preallocate*/);
//Now .insert(...) each struct into the set

The problem is that this takes a ridiculously long amount of time (like 30 seconds in debug mode, 0.5 in release).

Also, the following:

namespace std {

template<> struct hash<typename my::A> {
	std::size_t operator()(const my::A& vr) const {
		std::hash<unsigned int> func;
		size_t h1 = func(vr.x);
		size_t h2 = func(vr.y);
		size_t h3 = func(vr.z);
		return h1+h2+h3;
	}
};

}

And:

bool operator==(const A& a, const A& b) {
	if (a.x!=b.x) return false;
	if (a.y!=b.y) return false;
	if (a.z!=b.z) return false;
	return true;
}

Maybe the hashing combination is leading to a lot of collisions? Anyway, why is this so slow?

Thanks,
-G


#1Geometrian

Posted 03 February 2013 - 01:12 PM

Hi,

I have an array of structs, each containing three elements:

class A { public: unsigned int x, y, z; };
//...
A* long_list; //Has at least 250,000 elements

. . . and I need to find a set of the unique structs in long_list.

I try to construct the set as follows:

unordered_set<struct A> mapping(/*passing in long_list's length to preallocate*/);
//Now .insert(...) each struct into the set

The problem is that this takes a ridiculously long amount of time (like 30 seconds in debug mode, 0.5 in release).

Also, the following:

namespace std {

template<> struct hash<typename my::A> {
	std::size_t operator()(const my::A& vr) const {
		std::hash<unsigned int> func;
		size_t h1 = func(vr.x);
		size_t h2 = func(vr.y);
		size_t h3 = func(vr.z);
		return h1+h2+h3;
	}
};

}

And:

bool operator==(const A& a, const A& b) {
	if (a.x!=b.x) return false;
	if (a.y!=b.y) return false;
	if (a.z!=b.z) return false;
	return true;
}

Maybe the hashing combination is leading to a lot of collisions? Anyway, why is this so slow?

Thanks,
-G


PARTNERS