연관 컨테이너는 데이터를 추가 할 때 내부에 hash table이나 tree 구조를 유지해서 많은 원소가 삽입 되더라도 원하는 값을 빠른 속도로 검색 하는것이 가능하도록 해준다.

어떤 key가 주어 졌을 때 이것이 정확히 원하는 값이 아니 더 라도 특정한 범위에 들면 해당 Block을 반환하는 코딩을 하고 있었는데, 생각보다 map이나 set 같은 연관 컨테이너에 find_if()로 조건을 주는 코드 레퍼런스들이 많았다. 예를 들면 다음과 같이 주어진 set에 대해 find_if()로 모든 원소들을 돌면서 주어진 key가 들어 갈 수 있는 Block 찾는 것과 같은 경우이다.

find_if(
  s.begin(), s.end(),
  [findKey](const Block* el) {
    return findKey >= el->blkBase \
      && findKey < (el->blkBase + el->blkSize); });

주어진 원소의 수가 얼마 없다면 이런 종류의 코드가 별 무리가 없겠지만, 원소의 수가 많아지면 두드러지는 성능 차이를 보인다. 다음은 이와 같이 find_if()로 모든 원소들을 방문해 가며 range에 속하는지 검사하는 코드를 vector, map, set에 대해서 10만개의 원소로 돌린 것인데, 오히려 vector에 비해 map과 set이 각각 4배에서 6배 정도의 느린 검색 성능을 보여 준다.

[Vector]
100000 items pushed to vector.
Insertion: 13ms
Searching: 28879ms

[Map]
100000 items pushed to map.
Insertion: 63ms
Searching: 120259ms

[Set]
100000 items pushed to set.
Insertion: 60ms
Searching: 193998ms

연관 컨테이너 들은 원소를 추가할 때 효율적인 검색을 위한 부가적인 동작을 수행해야 하므로 insertion에 시간이 조금 더 걸리는 건 그렇다 쳐도, 원소의 수에 따라 선형적으로 검색 시간이 증가하는 vector에 비해 4배에서 6배 정도의 검색 시간이 더 드는 결과는 연관 컨테이너에 대해 find_if()를 들이 대는 자체가 현명한 생각인가 하는 의구심이 들게 한다. 즉, find_if()를 사용하면 주어진 컨테이너의 구조에 맞게 효율적으로 iteration을 해 주고 그런거 없다. 적어도 g++(v7.5.0)에서는.

그렇다면 이 경우 처럼, C++에서 특정한 값이 아니라 주어진 키가 범위에 드는지 검사하고 싶은 경우는 어떻게 해야 할까? Java의 Navigatable* 만큼은 세부적이진 않지만 C++의 map과 set 모두 주어진 key에서 가장 가까운 값을 반환하는 lower_bound() / upper_bound()를 제공한다. 이를 이용해서 다음과 같이 반환된 객체에 대해서만 추가로 검사를 해서 범위에 드는지 확인하면 보다 효율적으로 구현할 수 있다.

auto re = s.lower_bound(&findBlk);
auto el = *re;
if (re != s.end()
    && (findKey >= el->blkBase && findKey < (el->blkBase + el->blkSize))) {
}

이렇게 find_if()로 모든 원소들을 방문하는 것이 아닌, lower_bound()로 반환 받은 결과만 검사하는 방법으로 위와 같은 10만개의 원소에 대해 돌려보면 기대했던 바와 같이 vector보다 훨씬 좋은 연관 컨테이너의 검색 속도를 볼 수 있다.

[Vector]
100000 items pushed to vector.
Insertion: 13ms
Searching: 29765ms

[Map]
100000 items pushed to map.
Insertion: 62ms
Searching: 35ms

[Set]
100000 items pushed to set.
Insertion: 62ms
Searching: 36ms

시험에 사용한 전체 코드는 GitHub Gist에 붙여둔다.

	/*
	* rangeserach_perf.cpp
	*
	* Demonstrate perf comparisions of find_if() on vector,
	* map and set containers and proper range searching methods.
	*
	* litcoder.com
	*/
	#include <iostream>
	#include <iomanip>
	#include <map>
	#include <set>
	#include <vector>
	#include <cstdint>
	#include <string>
	#include <algorithm>
	#include <chrono>
	using namespace std;
	using namespace chrono;
	struct Block {
	Block(uint32_t blkBase, size_t blkSize)
	: blkBase(blkBase),
	blkSize(blkSize) {
	}
	// Block size: blkBase ~ (blkBase + blkSize -1)
	const uint32_t blkBase;
	const size_t blkSize;
	};
	struct BlockCompare {
	bool operator()(const Block *lhs, const Block *rhs) const {
	return lhs->blkBase > rhs->blkBase;
	}
	};
	int main(void) {
	map<uint32_t, Block*> m;
	vector<Block*> vec;
	set<Block*, BlockCompare> s;
	uint32_t findKey = 0u;
	string input;
	const uint32_t defaultBlkSize = 10;
	const uint32_t incStep = defaultBlkSize * 2;
	const uint32_t cnt = 100000u;
	// Vector.
	cout << "[Vector]" << endl;
	auto beginInsertVec = steady_clock::now();
	for (uint32_t i=0; i < (cnt * incStep); i += incStep) {
	auto blk = new Block(i, defaultBlkSize);
	vec.push_back(blk);
	}
	auto endInsertVec = steady_clock::now();
	cout << vec.size() << " items pushed to vector." << endl;
	auto beginSearchVec = steady_clock::now();
	for (uint32_t i=0u; i < cnt; i++) {
	findKey = rand() % cnt;
	find_if(vec.begin(), vec.end(), [findKey](const Block* b) {
	return findKey >= b->blkBase && findKey < (b->blkBase + b->blkSize); });
	}
	auto endSearchVec = steady_clock::now();
	for (auto it=vec.begin(); it != vec.end(); it++) {
	vec.erase(it);
	delete *it;
	}
	vec.clear();
	cout << "Insertion: "
	<< duration_cast<milliseconds>(endInsertVec - beginInsertVec).count()
	<< "ms" << endl
	<< "Searching: "
	<< duration_cast<milliseconds>(endSearchVec - beginSearchVec).count()
	<< "ms" << endl << endl;
	// Map
	cout << "[Map]" << endl;
	auto beginInsert = steady_clock::now();
	for (uint32_t i=0; i < (cnt * incStep); i += incStep) {
	auto blk = new Block(i, defaultBlkSize);
	m.insert({i, blk});
	}
	auto endInsert = steady_clock::now();
	cout << m.size() << " items pushed to map." << endl;
	auto beginSearch = steady_clock::now();
	for (uint32_t i=0u; i < cnt; i++) {
	findKey = rand() % cnt;
	/*
	find_if(m.begin(), m.end(), [findKey](const pair<uint32_t, Block*> pair) {
	return findKey >= pair.second->blkBase && findKey < (pair.second->blkBase + pair.second->blkSize); });
	*/
	auto re = m.lower_bound(findKey);
	auto el = re->second;
	if (re != m.end()
	&& (findKey >= el->blkBase && findKey < (el->blkBase + el->blkSize))) {
	}
	}
	auto endSearch = steady_clock::now();
	// Dealloc.
	for (auto& el : m) {
	m.erase(el.first);
	delete el.second;
	}
	m.clear();
	cout << "Insertion: "
	<< duration_cast<milliseconds>(endInsert - beginInsert).count()
	<< "ms" << endl
	<< "Searching: "
	<< duration_cast<milliseconds>(endSearch - beginSearch).count()
	<< "ms" << endl << endl;
	// Set
	cout << "[Set]" << endl;
	auto beginInsertSet = steady_clock::now();
	for (uint32_t i=0; i < (cnt * incStep); i += incStep) {
	auto blk = new Block(i, defaultBlkSize);
	s.insert(blk);
	}
	auto endInsertSet = steady_clock::now();
	cout << s.size() << " items pushed to set." << endl;
	auto beginSearchSet = steady_clock::now();
	for (uint32_t i=0u; i < cnt; i++) {
	findKey = rand() % cnt;
	Block findBlk(findKey, defaultBlkSize);
	/*
	find_if(s.begin(), s.end(), [findKey](const Block* el) {
	return findKey >= el->blkBase && findKey < (el->blkBase + el->blkSize); });
	*/
	auto re = s.lower_bound(&findBlk);
	auto el = *re;
	if (re != s.end()
	&& (findKey >= el->blkBase && findKey < (el->blkBase + el->blkSize))) {
	}
	}
	auto endSearchSet = steady_clock::now();
	// Dealloc.
	for (auto& el : s) {
	s.erase(el);
	delete el;
	}
	s.clear();
	cout << "Insertion: "
	<< duration_cast<milliseconds>(endInsertSet - beginInsertSet).count()
	<< "ms" << endl
	<< "Searching: "
	<< duration_cast<milliseconds>(endSearchSet - beginSearchSet).count()
	<< "ms" << endl;
	return 0;
	}

view raw rangesearch_perf.cpp hosted with by GitHub