fork download
copy 
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <chrono>
  4. #include <cstdlib>
  5. #include <ctime>
  6. #include <iostream>
  7. #include <map>
  8. #include <random>
  9. #include <unordered_map>
  10. #include <vector>
  11.  
  12. #define BENCHMARK 1
  13.  
  14.  
  15. template<class PairMap>
  16. inline float DotPairsMapped(const PairMap& lhs, const PairMap& rhs) {
  17. 	float dot = 0;
  18. 	for(auto& pair : lhs) {
  19. 		auto pos = rhs.find(pair.first);
  20. 		if(pos != rhs.end())
  21. 			dot += pair.second * pos->second;
  22. 	}
  23. 	return dot;
  24. }
  25.  
  26. template<class PairContainerSorted>
  27. inline float DotPairsSorted(const PairContainerSorted& lhs, const PairContainerSorted& rhs) {
  28. 	float dot = 0;
  29. 	for(auto pLhs = lhs.begin(), pRhs = rhs.begin(), endLhs = lhs.end(), endRhs = rhs.end(); pRhs != endRhs;) {
  30. 		for(; pLhs != endLhs && pLhs->first < pRhs->first; ++pLhs);
  31. 		if(pLhs == endLhs)
  32. 			break;
  33. 		for(; pRhs != endRhs && pRhs->first < pLhs->first; ++pRhs);
  34. 		if(pRhs == endRhs)
  35. 			break;
  36. 		if(pLhs->first == pRhs->first) {
  37. 			dot += pLhs->second * pRhs->second;
  38. 			++pLhs;
  39. 			++pRhs;
  40. 		}
  41. 	}
  42. 	return dot;
  43. }
  44.  
  45. template<class PairContainer>
  46. inline float LenSqrPairs(const PairContainer& vec) {
  47. 	float dot = 0;
  48. 	for(auto& pair : vec)
  49. 		dot += pair.second * pair.second;
  50. 	return dot;
  51. }
  52.  
  53. struct SparseVector {
  54. 	explicit SparseVector(size_t d, const std::pair<size_t, float>* begin, const std::pair<size_t, float>* end) : d(d) {
  55. 		size_t k(end - begin);
  56. 		idx.resize(k);
  57. 		val.resize(k);
  58. 		for(size_t i = 0; begin != end; ++i, ++begin) {
  59. 			idx[i] = begin->first;
  60. 			val[i] = begin->second;
  61. 		}
  62. 	}
  63.  
  64. 	bool IsValid() const {
  65. 		if(idx.size() != val.size())
  66. 			return false;
  67. 		for(size_t i = 1; i < idx.size(); ++i) {
  68. 			if(idx[i - 1] >= idx[i])
  69. 				return false;
  70. 		}
  71. 		return true;
  72. 	}
  73.  
  74. 	static float CosineDistance(const SparseVector& lhs, const SparseVector& rhs);
  75.  
  76. 	size_t d;
  77. 	std::vector<size_t> idx;
  78. 	std::vector<float> val;
  79. };
  80.  
  81. inline float Dot(const std::map<size_t, float>& lhs, const std::map<size_t, float>& rhs) { return DotPairsSorted(lhs, rhs); }
  82. inline float LenSqr(const std::map<size_t, float>& vec) { return LenSqrPairs(vec); }
  83. inline float Dot(const std::unordered_map<size_t, float>& lhs, const std::unordered_map<size_t, float>& rhs) { return DotPairsMapped(lhs, rhs); }
  84. inline float LenSqr(const std::unordered_map<size_t, float>& vec) { return LenSqrPairs(vec); }
  85. inline float Dot(const std::vector<std::pair<size_t, float>>& lhs, const std::vector<std::pair<size_t, float>>& rhs) { return DotPairsSorted(lhs, rhs); }
  86. inline float LenSqr(const std::vector<std::pair<size_t, float>>& vec) { return LenSqrPairs(vec); }
  87.  
  88. inline float Dot(const SparseVector& lhs, const SparseVector& rhs) {
  89. 	float dot = 0;
  90. 	if(!lhs.idx.empty() && !rhs.idx.empty()) {
  91. 		const size_t *itIdxLhs = &lhs.idx[0], *endIdxLhs = &lhs.idx[0] + lhs.idx.size();
  92. 		const float *itValLhs = &lhs.val[0], *endValLhs = &lhs.val[0] + lhs.val.size();
  93. 		const size_t *itIdxRhs = &rhs.idx[0], *endIdxRhs = &rhs.idx[0] + rhs.idx.size();
  94. 		const float *itValRhs = &rhs.val[0], *endValRhs = &rhs.val[0] + rhs.val.size();
  95. 		while(itIdxRhs != endIdxRhs) {
  96. 			for(; itIdxLhs < endIdxLhs && *itIdxLhs < *itIdxRhs; ++itIdxLhs, ++itValLhs);
  97. 			if(itIdxLhs == endIdxLhs)
  98. 				break;
  99. 			for(; itIdxRhs < endIdxRhs && *itIdxRhs < *itIdxLhs; ++itIdxRhs, ++itValRhs);
  100. 			if(itIdxRhs == endIdxRhs)
  101. 				break;
  102. 			if(*itIdxLhs == *itIdxRhs) {
  103. 				dot += (*itValLhs) * (*itValRhs);
  104. 				++itIdxLhs;
  105. 				++itValLhs;
  106. 				++itIdxRhs;
  107. 				++itValRhs;
  108. 			}
  109. 		}
  110. 	}
  111. 	return dot;
  112. }
  113.  
  114. inline float LenSqr(const SparseVector& vec) {
  115. 	float dot = 0;
  116. 	for(float v : vec.val)
  117. 		dot += v * v;
  118. 	return dot;
  119. }
  120.  
  121. template<class Vector>
  122. inline float CosineDistance(const Vector& lhs, const Vector& rhs) {
  123. 	return Dot(lhs, rhs) / std::sqrt(LenSqr(lhs) * LenSqr(rhs));
  124. }
  125.  
  126. inline float SparseVector::CosineDistance(const SparseVector& lhs, const SparseVector& rhs) {
  127. 	float dotLR = 0, dotLL = 0, dotRR = 0;
  128. 	if(!lhs.idx.empty() && !rhs.idx.empty()) {
  129. 		const size_t *itIdxLhs = &lhs.idx[0], *endIdxLhs = &lhs.idx[0] + lhs.idx.size();
  130. 		const float *itValLhs = &lhs.val[0], *endValLhs = &lhs.val[0] + lhs.val.size();
  131. 		const size_t *itIdxRhs = &rhs.idx[0], *endIdxRhs = &rhs.idx[0] + rhs.idx.size();
  132. 		const float *itValRhs = &rhs.val[0], *endValRhs = &rhs.val[0] + rhs.val.size();
  133. 		while(itIdxRhs != endIdxRhs) {
  134. 			for(; itIdxLhs < endIdxLhs && *itIdxLhs < *itIdxRhs; ++itIdxLhs, ++itValLhs)
  135. 				dotLL += (*itValLhs) * (*itValLhs);
  136. 			if(itIdxLhs == endIdxLhs) {
  137. 				for(; itIdxRhs < endIdxRhs; ++itIdxRhs, ++itValRhs)
  138. 					dotRR += (*itValRhs) * (*itValRhs);
  139. 				break;
  140. 			}
  141. 			for(; itIdxRhs < endIdxRhs && *itIdxRhs < *itIdxLhs; ++itIdxRhs, ++itValRhs)
  142. 				dotRR += (*itValRhs) * (*itValRhs);
  143. 			if(itIdxRhs == endIdxRhs) {
  144. 				for(; itIdxLhs < endIdxLhs; ++itIdxLhs, ++itValLhs)
  145. 					dotLL += (*itValLhs) * (*itValLhs);
  146. 				break;
  147. 			}
  148. 			if(*itIdxLhs == *itIdxRhs) {
  149. 				dotLR += (*itValLhs) * (*itValRhs);
  150. 				dotLL += (*itValLhs) * (*itValLhs);
  151. 				dotRR += (*itValRhs) * (*itValRhs);
  152. 				++itIdxLhs;
  153. 				++itValLhs;
  154. 				++itIdxRhs;
  155. 				++itValRhs;
  156. 			}
  157. 		}
  158. 	}
  159. 	float lenSqrL = LenSqr(lhs), lenSqrR = LenSqr(rhs);
  160. 	return dotLR / std::sqrt(dotLL * dotRR);
  161. }
  162.  
  163. template<class RandomIt, class UniformRandomNumberGenerator>
  164. void shuffleK(RandomIt first, RandomIt last, typename std::iterator_traits<RandomIt>::difference_type k, UniformRandomNumberGenerator&& g) {
  165. 	typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
  166. 	typedef typename std::make_unsigned<diff_t>::type udiff_t;
  167. 	typedef typename std::uniform_int_distribution<udiff_t> distr_t;
  168. 	typedef typename distr_t::param_type param_t;
  169.  
  170. 	distr_t D;
  171. 	diff_t n = std::min(k, last - first);
  172. 	for(diff_t i = n - 1; i > 0; --i) {
  173. 		using std::swap;
  174. 		swap(first[i], first[D(g, param_t(0, i))]);
  175. 	}
  176. }
  177.  
  178. #if BENCHMARK
  179. struct Benchmark {
  180. 	double vectorDot, vectorLen, vectorCos;
  181. 	double mapDot, mapLen, mapCos;
  182. 	double unorderedDot, unorderedLen, unorderedCos;
  183. 	double classDot, classLen, classCos;
  184.  
  185. 	void min(Benchmark other) {
  186. 		vectorDot = std::min(vectorDot, other.vectorDot);
  187. 		vectorLen = std::min(vectorLen, other.vectorLen);
  188. 		vectorCos = std::min(vectorCos, other.vectorCos);
  189. 		mapDot = std::min(mapDot, other.mapDot);
  190. 		mapLen = std::min(mapLen, other.mapLen);
  191. 		mapCos = std::min(mapCos, other.mapCos);
  192. 		unorderedDot = std::min(unorderedDot, other.unorderedDot);
  193. 		unorderedLen = std::min(unorderedLen, other.unorderedLen);
  194. 		unorderedCos = std::min(unorderedCos, other.unorderedCos);
  195. 		classDot = std::min(classDot, other.classDot);
  196. 		classLen = std::min(classLen, other.classLen);
  197. 		classCos = std::min(classCos, other.classCos);
  198. 	}
  199. 	void max(Benchmark other) {
  200. 		vectorDot = std::max(vectorDot, other.vectorDot);
  201. 		vectorLen = std::max(vectorLen, other.vectorLen);
  202. 		vectorCos = std::max(vectorCos, other.vectorCos);
  203. 		mapDot = std::max(mapDot, other.mapDot);
  204. 		mapLen = std::max(mapLen, other.mapLen);
  205. 		mapCos = std::max(mapCos, other.mapCos);
  206. 		unorderedDot = std::max(unorderedDot, other.unorderedDot);
  207. 		unorderedLen = std::max(unorderedLen, other.unorderedLen);
  208. 		unorderedCos = std::max(unorderedCos, other.unorderedCos);
  209. 		classDot = std::max(classDot, other.classDot);
  210. 		classLen = std::max(classLen, other.classLen);
  211. 		classCos = std::max(classCos, other.classCos);
  212. 	}
  213. 	void add(Benchmark other) {
  214. 		vectorDot += other.vectorDot;
  215. 		vectorLen += other.vectorLen;
  216. 		vectorCos += other.vectorCos;
  217. 		mapDot += other.mapDot;
  218. 		mapLen += other.mapLen;
  219. 		mapCos += other.mapCos;
  220. 		unorderedDot += other.unorderedDot;
  221. 		unorderedLen += other.unorderedLen;
  222. 		unorderedCos += other.unorderedCos;
  223. 		classDot += other.classDot;
  224. 		classLen += other.classLen;
  225. 		classCos += other.classCos;
  226. 	}
  227. 	void sub(Benchmark other) {
  228. 		vectorDot -= other.vectorDot;
  229. 		vectorLen -= other.vectorLen;
  230. 		vectorCos -= other.vectorCos;
  231. 		mapDot -= other.mapDot;
  232. 		mapLen -= other.mapLen;
  233. 		mapCos -= other.mapCos;
  234. 		unorderedDot -= other.unorderedDot;
  235. 		unorderedLen -= other.unorderedLen;
  236. 		unorderedCos -= other.unorderedCos;
  237. 		classDot -= other.classDot;
  238. 		classLen -= other.classLen;
  239. 		classCos -= other.classCos;
  240. 	}
  241. 	void mul(double factor) {
  242. 		vectorDot *= factor;
  243. 		vectorLen *= factor;
  244. 		vectorCos *= factor;
  245. 		mapDot *= factor;
  246. 		mapLen *= factor;
  247. 		mapCos *= factor;
  248. 		unorderedDot *= factor;
  249. 		unorderedLen *= factor;
  250. 		unorderedCos *= factor;
  251. 		classDot *= factor;
  252. 		classLen *= factor;
  253. 		classCos *= factor;
  254. 	}
  255.  
  256. 	template<class OStream>
  257. 	friend OStream& operator<< (OStream& os, const Benchmark& o) {
  258. 		os << "  pairs t(dot): " << o.vectorDot << ", t(len2): " << o.vectorLen << ", t(cos): " << o.vectorCos << std::endl;
  259. 		os << "  map'd / pairs dot: " << o.mapDot / o.vectorDot << ", len2: " << o.mapLen / o.vectorLen << ", cos: " << o.mapCos / o.vectorCos << std::endl;
  260. 		os << "  hashm / pairs dot: " << o.unorderedDot / o.vectorDot << ", len2: " << o.unorderedLen / o.vectorLen << ", cos: " << o.unorderedCos / o.vectorCos << std::endl;
  261. 		os << "  class / pairs dot: " << o.classDot / o.vectorDot << ", len2: " << o.classLen / o.vectorLen << ", cos: " << o.classCos / o.vectorCos << std::endl;
  262. 		return os;
  263. 	}
  264. };
  265. #endif
  266.  
  267. void RunBenchmark(size_t D, float Ratio, size_t RunCount, std::mt19937& g);
  268.  
  269. int main() {
  270. 	const size_t D = 169647;
  271. 	const float Ratio = 0.05f;
  272. 	const size_t RunCount = 10;
  273.  
  274. 	//std::random_device rd;
  275. 	//std::mt19937 g(rd());
  276. 	std::mt19937 g(0xC0FFEE);
  277.  
  278. 	for(int last = 1, cur = 1; cur <= 5; last += cur, std::swap(last, cur))
  279. 		RunBenchmark(D, Ratio * cur, RunCount, g);
  280.  
  281. 	return 0;
  282. }
  283.  
  284. volatile float sideEffectOnly = 0;
  285. void RunBenchmark(size_t D, float Ratio, size_t RunCount, std::mt19937& g) {
  286. 	std::vector<size_t> indices;
  287. 	{
  288. 		indices.resize(D);
  289. 		for(size_t i = 0; i < D; ++i)
  290. 			indices[i] = i;
  291. 	}
  292. 	// Generates two sparse random vectors with on average ratio * D entries
  293. 	auto GenerateInput = [&indices, &g](float ratio, std::vector<std::pair<size_t, float>>& a, std::vector<std::pair<size_t, float>>& b) {
  294. 		if(indices.size() == 0) {
  295. 			a.resize(0);
  296. 			b.resize(0);
  297. 			return;
  298. 		}
  299.  
  300. 		// determine number of entries
  301. 		typedef std::normal_distribution<float> norm_t;
  302. 		norm_t nrand;
  303. 		norm_t::param_type nparam(ratio * (float)indices.size(), 3.0f);
  304. 		float sizeA = std::min((float)indices.size(), std::max(1.0f, nrand(g, nparam)));
  305. 		float sizeB = std::min((float)indices.size(), std::max(1.0f, nrand(g, nparam)));
  306. 		a.resize((size_t)sizeA);
  307. 		b.resize((size_t)sizeB);
  308.  
  309. 		// determine values of entries
  310. 		typedef std::uniform_real_distribution<float> uniform_t;
  311. 		uniform_t urand;
  312. 		shuffleK(&indices[0], &indices[0] + indices.size(), indices.size(), g);
  313. 		for(size_t i = 0; i < a.size(); ++i)
  314. 			a[i] = std::make_pair(indices[i], urand(g, uniform_t::param_type(-13.37f, 13.37f)));
  315. 		shuffleK(&indices[0], &indices[0] + indices.size(), indices.size(), g);
  316. 		for(size_t i = 0; i < b.size(); ++i)
  317. 			b[i] = std::make_pair(indices[i], urand(g, uniform_t::param_type(-13.37f, 13.37f)));
  318.  
  319. 		auto pred = [](std::pair<size_t, float> lhs, std::pair<size_t, float> rhs) -> bool { return lhs.first < rhs.first; };
  320. 		std::sort(&a[0], &a[0] + a.size(), pred);
  321. 		std::sort(&b[0], &b[0] + b.size(), pred);
  322. 	};
  323.  
  324. #if BENCHMARK
  325. 	const size_t BenchmarkDot = 3, BenchmarkLen = 10, BenchmarkCos = 3;
  326. 	std::vector<Benchmark> benchmarks;
  327. 	typedef std::chrono::high_resolution_clock Clock;
  328. 	auto intervalAsSeconds = [](Clock::time_point t0, Clock::time_point t1) -> double { return 1e-9 * std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count(); };
  329. 	double tMapDotSpecialMin = 0, tMapDotSpecialAvg = 0, tMapDotSpecialMax = 0;
  330. 	double tClassCosSpecialMin = 0, tClassCosSpecialAvg = 0, tClassCosSpecialMax = 0;
  331. #endif
  332. 	std::vector<std::pair<size_t, float>> a, b;
  333. 	a.reserve(indices.size());
  334. 	b.reserve(indices.size());
  335. 	for(size_t run = 0; run < RunCount; ++run) {
  336. 		GenerateInput(Ratio, a, b);
  337.  
  338. 		// ============= MAP ==============
  339. 		std::map<size_t, float> mA, mB;
  340. 		for(auto pair : a) mA.insert(pair);
  341. 		for(auto pair : b) mB.insert(pair);
  342. 		assert(mA.size() == a.size() && mB.size() == b.size());
  343. 		// warm-up
  344. 		const float mapDot = Dot(mA, mB);
  345. 		const float mapCos = CosineDistance(mA, mB);
  346. #if BENCHMARK
  347. 		std::chrono::time_point<Clock> t0, t1;
  348. 		Benchmark benchmark = {};
  349. 		t0 = Clock::now();
  350. 		for(size_t i = 0; i < BenchmarkDot; ++i)
  351. 			sideEffectOnly += Dot(mA, mB);
  352. 		t1 = Clock::now();
  353. 		benchmark.mapDot = intervalAsSeconds(t0, t1);
  354. 		t0 = Clock::now();
  355. 		for(size_t i = 0; i < BenchmarkLen; ++i) {
  356. 			sideEffectOnly += LenSqr(mA);
  357. 			sideEffectOnly += LenSqr(mB);
  358. 		}
  359. 		t1 = Clock::now();
  360. 		benchmark.mapLen = intervalAsSeconds(t0, t1);
  361. 		t0 = Clock::now();
  362. 		for(size_t i = 0; i < BenchmarkCos; ++i)
  363. 			sideEffectOnly += CosineDistance(mA, mB);
  364. 		t1 = Clock::now();
  365. 		benchmark.mapCos = intervalAsSeconds(t0, t1);
  366. #endif
  367.  
  368. 		// ============= UNORDERED MAP ==============
  369. 		std::unordered_map<size_t, float> uA, uB;
  370. 		for(auto pair : a) uA.insert(pair);
  371. 		for(auto pair : b) uB.insert(pair);
  372. 		assert(uA.size() == a.size() && uB.size() == b.size());
  373. 		const float unorderedDot = Dot(uA, uB);
  374. 		const float unorderedCos = CosineDistance(uA, uB);
  375. #if BENCHMARK
  376. 		t0 = Clock::now();
  377. 		for(size_t i = 0; i < BenchmarkDot; ++i)
  378. 			sideEffectOnly += Dot(uA, uB);
  379. 		t1 = Clock::now();
  380. 		benchmark.unorderedDot = intervalAsSeconds(t0, t1);
  381. 		t0 = Clock::now();
  382. 		for(size_t i = 0; i < BenchmarkLen; ++i) {
  383. 			sideEffectOnly += LenSqr(uA);
  384. 			sideEffectOnly += LenSqr(uB);
  385. 		}
  386. 		t1 = Clock::now();
  387. 		benchmark.unorderedLen = intervalAsSeconds(t0, t1);
  388. 		t0 = Clock::now();
  389. 		for(size_t i = 0; i < BenchmarkCos; ++i)
  390. 			sideEffectOnly += CosineDistance(uA, uB);
  391. 		t1 = Clock::now();
  392. 		benchmark.unorderedCos = intervalAsSeconds(t0, t1);
  393. #endif
  394.  
  395. 		// ============= VECTOR OF PAIRS ==============
  396. 		const float vectorDot = Dot(a, b);
  397. 		const float vectorCos = CosineDistance(a, b);
  398. #if BENCHMARK
  399. 		t0 = Clock::now();
  400. 		for(size_t i = 0; i < BenchmarkDot; ++i)
  401. 			sideEffectOnly += Dot(a, b);
  402. 		t1 = Clock::now();
  403. 		benchmark.vectorDot = intervalAsSeconds(t0, t1);
  404. 		t0 = Clock::now();
  405. 		for(size_t i = 0; i < BenchmarkLen; ++i) {
  406. 			sideEffectOnly += LenSqr(a);
  407. 			sideEffectOnly += LenSqr(b);
  408. 		}
  409. 		t1 = Clock::now();
  410. 		benchmark.vectorLen = intervalAsSeconds(t0, t1);
  411. 		t0 = Clock::now();
  412. 		for(size_t i = 0; i < BenchmarkCos; ++i)
  413. 			sideEffectOnly += CosineDistance(a, b);
  414. 		t1 = Clock::now();
  415. 		benchmark.vectorCos = intervalAsSeconds(t0, t1);
  416. #endif
  417.  
  418. 		// ============= PAIRS OF VECTORS ==============
  419. 		SparseVector vA(indices.size(), &a[0], &a[0] + a.size());
  420. 		SparseVector vB(indices.size(), &b[0], &b[0] + b.size());
  421. 		const float classDot = Dot(vA, vB);
  422. 		const float classCos = CosineDistance(vA, vB);
  423. #if BENCHMARK
  424. 		t0 = Clock::now();
  425. 		for(size_t i = 0; i < BenchmarkDot; ++i)
  426. 			sideEffectOnly += Dot(vA, vB);
  427. 		t1 = Clock::now();
  428. 		benchmark.classDot = intervalAsSeconds(t0, t1);
  429. 		t0 = Clock::now();
  430. 		for(size_t i = 0; i < BenchmarkLen; ++i) {
  431. 			sideEffectOnly += LenSqr(vA);
  432. 			sideEffectOnly += LenSqr(vB);
  433. 		}
  434. 		t1 = Clock::now();
  435. 		benchmark.classLen = intervalAsSeconds(t0, t1);
  436. 		t0 = Clock::now();
  437. 		for(size_t i = 0; i < BenchmarkCos; ++i)
  438. 			sideEffectOnly += CosineDistance(vA, vB);
  439. 		t1 = Clock::now();
  440. 		benchmark.classCos = intervalAsSeconds(t0, t1);
  441. #endif
  442.  
  443. 		// ============= NAIVE MAP ==============
  444. 		const float mapDotSpecial = DotPairsMapped(mA, mB);
  445. 		// ======== DON'T TOUCH IT TWICE ========
  446. 		const float classCosSpecial = SparseVector::CosineDistance(vA, vB);
  447. #if BENCHMARK
  448. 		// naive dot product with map
  449. 		t0 = Clock::now();
  450. 		for(size_t i = 0; i < BenchmarkDot; ++i)
  451. 			sideEffectOnly += DotPairsMapped(mA, mB);
  452. 		t1 = Clock::now();
  453. 		double tMapDotSpecial = intervalAsSeconds(t0, t1);
  454. 		// cosine distance computation touching each element just once
  455. 		t0 = Clock::now();
  456. 		for(size_t i = 0; i < BenchmarkCos; ++i)
  457. 			sideEffectOnly += SparseVector::CosineDistance(vA, vB);
  458. 		t1 = Clock::now();
  459. 		double tClassCosSpecial = intervalAsSeconds(t0, t1);
  460. 		// accumulate specials
  461. 		if(run == 0) {
  462. 			tMapDotSpecialMin = tMapDotSpecial;
  463. 			tMapDotSpecialAvg = tMapDotSpecial;
  464. 			tMapDotSpecialMax = tMapDotSpecial;
  465. 			tClassCosSpecialMin = tClassCosSpecial;
  466. 			tClassCosSpecialAvg = tClassCosSpecial;
  467. 			tClassCosSpecialMax = tClassCosSpecial;
  468. 		} else {
  469. 			tMapDotSpecialMin = std::min(tMapDotSpecialMin, tMapDotSpecial);
  470. 			tMapDotSpecialAvg += tMapDotSpecial;
  471. 			tMapDotSpecialMax = std::max(tMapDotSpecialMax, tMapDotSpecial);
  472. 			tClassCosSpecialMin = std::min(tClassCosSpecialMin, tClassCosSpecial);
  473. 			tClassCosSpecialAvg += tClassCosSpecial;
  474. 			tClassCosSpecialMax = std::max(tClassCosSpecialMax, tClassCosSpecial);
  475. 		}
  476. #endif
  477.  
  478. 		auto equal = [](float lhs, float rhs) -> bool { return (rhs - lhs) * (rhs - lhs) < 1e-4f * std::max(std::abs(lhs), std::abs(rhs)); };
  479. 		if(!equal(vectorDot, mapDot) || !equal(vectorCos, mapCos) ||
  480. 		   !equal(vectorDot, unorderedDot) || !equal(vectorCos, unorderedCos) ||
  481. 		   !equal(vectorDot, classDot) || !equal(vectorCos, classCos) ||
  482. 		   !equal(vectorDot, mapDotSpecial) ||
  483. 		   !equal(vectorCos, classCosSpecial)) {
  484. 			std::cout << "Validation failure on run " << run << std::endl;
  485. 			std::cout << " pairs: dot(a, b): " << Dot(a, b) << ", cos(a, b): " << CosineDistance(a, b) << std::endl;
  486. 			std::cout << " map'd: dot(a, b): " << Dot(mA, mB) << ", cos(a, b): " << CosineDistance(mA, mB) << std::endl;
  487. 			std::cout << " hashm: dot(a, b): " << Dot(uA, uB) << ", cos(a, b): " << CosineDistance(uA, uB) << std::endl;
  488. 			std::cout << " class: dot(a, b): " << Dot(vA, vB) << ", cos(a, b): " << CosineDistance(vA, vB) << std::endl;
  489. 			std::cout << " specl map'd: dot(a, b): " << mapDotSpecial << std::endl;
  490. 			std::cout << " specl class: cos(a, b): " << classCosSpecial << std::endl;
  491. #if BENCHMARK
  492. 		} else {
  493. 			benchmarks.push_back(benchmark);
  494. #endif
  495. 		}
  496. 	}
  497.  
  498. #if BENCHMARK
  499. 	if(RunCount > 0 && !benchmarks.empty()) {
  500. 		Benchmark min = benchmarks[0], avg = min, max = min;
  501. 		for(size_t i = 1; i < benchmarks.size(); ++i) {
  502. 			min.min(benchmarks[i]);
  503. 			avg.add(benchmarks[i]);
  504. 			max.max(benchmarks[i]);
  505. 		}
  506. 		if(RunCount <= 2) {
  507. 			avg.mul(1.0 / RunCount);
  508. 			tClassCosSpecialAvg /= RunCount;
  509. 		} else {
  510. 			avg.sub(min);
  511. 			avg.sub(max);
  512. 			avg.mul(1.0 / (RunCount - 2));
  513. 			tMapDotSpecialAvg = (tMapDotSpecialAvg - tMapDotSpecialMin - tMapDotSpecialMax) / (RunCount - 2);
  514. 			tClassCosSpecialAvg = (tClassCosSpecialAvg - tClassCosSpecialMin - tClassCosSpecialMax) / (RunCount - 2);
  515. 		}
  516.  
  517. 		std::cout << " *** BENCHMARK *** " << std::endl;
  518. 		std::cout << "number of runs: " << RunCount << ", dimensions: " << D << " and non-zero ratio: " << Ratio << std::endl;
  519. 		std::cout << "number of dot products per run: " << BenchmarkDot << std::endl;
  520. 		std::cout << "number of lengthsqares per run: " << BenchmarkLen << std::endl;
  521. 		std::cout << "number of cosine dists per run: " << BenchmarkCos << std::endl;
  522. 		std::cout << std::endl;
  523. #if 0
  524. 		// min(x) / min(base) is not a good measure...
  525. 		std::cout << "min" << std::endl;
  526. 		std::cout << min;
  527. 		std::cout << "  specl / pairs dot (naive map): " << (tMapDotSpecialMin / min.vectorDot) << std::endl;
  528. 		std::cout << "  specl / pairs cos (optimised): " << (tClassCosSpecialMin / min.vectorCos) << std::endl;
  529. 		std::cout << std::endl;
  530. #endif
  531. 		// avg(x) / avg(base)
  532. 		std::cout << "avg" << std::endl;
  533. 		std::cout << avg;
  534. 		std::cout << "  specl / pairs dot (naive map): " << (tMapDotSpecialAvg / avg.vectorDot) << std::endl;
  535. 		std::cout << "  specl / pairs cos (optimised): " << (tClassCosSpecialAvg / avg.vectorCos) << std::endl;
  536. 		std::cout << std::endl;
  537. #if 0
  538. 		// max(x) / max(base) is not a good measure...
  539. 		std::cout << "max" << std::endl;
  540. 		std::cout << max;
  541. 		std::cout << "  specl / pairs dot (naive map): " << (tMapDotSpecialMax / max.vectorDot) << std::endl;
  542. 		std::cout << "  specl / pairs cos (optimised): " << (tClassCosSpecialMax / max.vectorCos) << std::endl;
  543. 		std::cout << std::endl;
  544. #endif
  545. 	}
  546. #endif
  547. }
  548.  
Success #stdin #stdout 4.57s 3440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 *** BENCHMARK *** 
number of runs: 10, dimensions: 169647 and non-zero ratio: 0.05
number of dot products per run: 3
number of lengthsqares per run: 10
number of cosine dists per run: 3

avg
  pairs t(dot): 0.000327096, t(len2): 0.000311987, t(cos): 0.000407925
  map'd / pairs dot: 3.31911, len2: 7.33166, cos: 4.17641
  hashm / pairs dot: 3.50114, len2: 2.28485, cos: 3.32586
  class / pairs dot: 1.03311, len2: 0.993495, cos: 1.06469
  specl / pairs dot (naive map): 8.52663
  specl / pairs cos (optimised): 0.960054

 *** BENCHMARK *** 
number of runs: 10, dimensions: 169647 and non-zero ratio: 0.1
number of dot products per run: 3
number of lengthsqares per run: 10
number of cosine dists per run: 3

avg
  pairs t(dot): 0.000665155, t(len2): 0.000643923, t(cos): 0.000826484
  map'd / pairs dot: 3.61124, len2: 7.90967, cos: 4.60001
  hashm / pairs dot: 4.02014, len2: 3.5281, cos: 4.08672
  class / pairs dot: 1.02877, len2: 0.965892, cos: 1.10754
  specl / pairs dot (naive map): 10.1952
  specl / pairs cos (optimised): 0.946074

 *** BENCHMARK *** 
number of runs: 10, dimensions: 169647 and non-zero ratio: 0.15
number of dot products per run: 3
number of lengthsqares per run: 10
number of cosine dists per run: 3

avg
  pairs t(dot): 0.00103057, t(len2): 0.000990735, t(cos): 0.00126902
  map'd / pairs dot: 3.52397, len2: 8.30844, cos: 4.82504
  hashm / pairs dot: 4.93329, len2: 4.31091, cos: 5.00829
  class / pairs dot: 1.01788, len2: 0.937355, cos: 1.05164
  specl / pairs dot (naive map): 10.0939
  specl / pairs cos (optimised): 0.948841

 *** BENCHMARK *** 
number of runs: 10, dimensions: 169647 and non-zero ratio: 0.25
number of dot products per run: 3
number of lengthsqares per run: 10
number of cosine dists per run: 3

avg
  pairs t(dot): 0.00178728, t(len2): 0.00205486, t(cos): 0.00232333
  map'd / pairs dot: 3.69081, len2: 7.66045, cos: 4.8268
  hashm / pairs dot: 5.75653, len2: 5.47987, cos: 6.4527
  class / pairs dot: 1.0306, len2: 0.755855, cos: 1.00221
  specl / pairs dot (naive map): 10.461
  specl / pairs cos (optimised): 0.932331
https://ideone.com/rzznp9
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!