1
얼마 전 검색 알고리즘을 사용하여 몇 가지 벤치 마크를 수행 한 결과, 이전 bsearch()가 std :: binary_search()와 비교해 훨씬 빨랐다는 사실에 깊은 인상을 받았습니다. 나는 괜찮은 컴파일러가 가능하면 bsearch()에 의해 std :: binary_search()를 대체 할 수있을 것이라고 생각했지만, GCC 4.7을 사용하고 있어도 bsearch는 std :: binary_search보다 5 배 빠른 것을 수행하는 것처럼 보입니다.bsearch wrapper
그래서 나는 같은 인터페이스와 std :: binary_search를 사용하여 bsearch 용 일종의 래퍼를 만들려고 시도하는 것이 가장 좋습니다. 그러나 알려지지 않은 이유로, 나는 그것을 할 수 없었습니다. 여기 내 코드 :
template<typename InputIterator, class T>
bool binary_search(InputIterator first, InputIterator last, const T& value)
{
auto cmp = [](const void* a, const void* b)
{
return (int) ((*(T*)a) == (*(T*)b));
};
std::cout << value << std::endl;
T* res = (T*) bsearch(&value, first, last-first, sizeof(*first), cmp);
return res != nullptr;
}
코드가 잘 컴파일되고 실행시 크래시되지 않습니다. 그러나 bsearch는 하나의 내부 반복 (* res가 매개 변수로 전달 된 탭의 중간 값과 항상 동일 함) 직후 중지됩니다. 나는 그것이 효과가없는 이유를 발견 할 수 없다. 가능하다면 약간의 도움이 될 것입니다.
감사합니다. 속도를 확인하는 데 사용되는 코드를 요청하는 사람들을 위해
:
const std::string keyword_str[] = {
// Some strings
};
int cmp(const void* s1, const void* s2)
{
return (int) ((*(std::string*)s1) == (*(std::string*)s2));
}
int main()
{
time_t start, end;
double dif;
time (&start);
// Code
for (const string& str: keyword_str)
{
for (size_t i = 0 ; i < 1000000 ; ++i)
{
// std::binary_search (uncomment to check)
//bool a = std::binary_search(keyword_str, keyword_str+28, str);
// bsearch
char** st = (char**) bsearch(&str, keyword_str, 28, sizeof(keyword_str[0]), cmp);
}
}
time (&end);
dif = difftime (end, start);
printf("Time spent: %fs.\n", dif);
return 0;
}
이 5 배의 성능 차이를 보여주는 테스트 사례를 보시려면 여기를 클릭하십시오. –
당신이'InputIterator'라고 이름 붙인 것들은'RandomAccessIterator'를 구현할 필요가 있습니다 _concept_ –
'cmp'가 다른 원소들에 대해'(int) false' ('== 0')를 반환하기 때문에 빠릅니다. 'bsearch'는'0'을 보았을 때 'equal'을 의미한다고 생각하고 검색을 멈 춥니 다. 그래서'bsearch'는 보통'std :: binary_search'가 진짜 검색을하는 동안 요소를 아주 빨리 발견했다고 생각합니다. – sth