C++에서 StringBuilder 류 의 실현 과 성능 최적화
14374 단어 C++StringBuilder
클 라 이언 트 들 이 달팽이 처럼 프로그램 이 느리다 고 불평 하 는 경우 가 많다.가능 한 의문점 을 검사 하기 시작 합 니 다:파일 IO,데이터베이스 접근 속도,심지어 웹 서 비 스 를 봅 니 다.그러나 이 가능 한 의문점 들 은 모두 정상 적 이 고 전혀 문제 가 없다.
가장 손 쉬 운 성능 분석 도 구 를 사용 하여 분석 한 결과 병목 은 작은 함수 에 있 습 니 다.이 함수 의 역할 은 긴 문자열 링크 를 파일 에 쓰 는 것 입 니 다.
이 함수 에 대해 다음 과 같은 최 적 화 를 했 습 니 다.모든 작은 문자열 을 긴 문자열 로 연결 하고 파일 기록 작업 을 수행 하여 수천 번 의 작은 문자열 이 파일 을 쓰 는 것 을 피 합 니 다.
이 최 적 화 는 반 만 맞 췄 다.
먼저 큰 문자열 로 파일 을 쓰 는 속 도 를 테스트 해 보 세 요.번개 처럼 빠 릅 니 다.그리고 모든 문자열 의 연결 속 도 를 테스트 하 세 요.
여러 해.
어떻게 된 거 야?당신 은 이 문 제 를 어떻게 극복 할 것 입 니까?
.net 프로그래머 가 StringBuilder 를 사용 하여 이 문 제 를 해결 할 수 있다 는 것 을 알 고 있 을 지도 모른다.이것 도 본문의 출발점 이다.
배경
구 글 이'C++StringBuilder'를 사용 하면 많은 답 을 얻 을 수 있 습 니 다.std::accumulate 를 사용 하 는 것 을 권장 합 니 다.이것 은 당신 이 실현 하고 자 하 는 거의 모든 것 을 완성 할 수 있 습 니 다.
#include <iostream>// for std::cout, std::endl
#include <string> // for std::string
#include <vector> // for std::vector
#include <numeric> // for std::accumulate
int main()
{
using namespace std;
vector<string> vec = { "hello", " ", "world" };
string s = accumulate(vec.begin(), vec.end(), s);
cout << s << endl; // prints 'hello world' to standard output.
return 0;
}
std::string 은 함수 reserver()에서 해결 방안 에 기 초 를 제공 합 니 다.이것 도 바로 우리 의 의도 이다.한 번 의 분배,마음대로 연결 하 는 것 이다.
문자열 연결 은 무 겁 고 둔 한 도구 로 인해 성능 에 심각 한 영향 을 줄 수 있 습 니 다.지난번 에 존 재 했 던 위험 으로 인해 이 특수 한 괴짜 가 나 에 게 문 제 를 일 으 켰 기 때문에 나 는 인디고 를 포기 했다.(나 는 C++11 의 새로운 특성 을 시도 하고 싶다)그리고 StringBuilder 류 의 일부 실현 을 썼 다.
// Subset of http://msdn.microsoft.com/en-us/library/system.text.stringbuilder.aspx
template <typename chr>
class StringBuilder {
typedef std::basic_string<chr> string_t;
typedef std::list<string_t> container_t; // Reasons not to use vector below.
typedef typename string_t::size_type size_type; // Reuse the size type in the string.
container_t m_Data;
size_type m_totalSize;
void append(const string_t &src) {
m_Data.push_back(src);
m_totalSize += src.size();
}
// No copy constructor, no assignement.
StringBuilder(const StringBuilder &);
StringBuilder & operator = (const StringBuilder &);
public:
StringBuilder(const string_t &src) {
if (!src.empty()) {
m_Data.push_back(src);
}
m_totalSize = src.size();
}
StringBuilder() {
m_totalSize = 0;
}
// TODO: Constructor that takes an array of strings.
StringBuilder & Append(const string_t &src) {
append(src);
return *this; // allow chaining.
}
// This one lets you add any STL container to the string builder.
template<class inputIterator>
StringBuilder & Add(const inputIterator &first, const inputIterator &afterLast) {
// std::for_each and a lambda look like overkill here.
// <b>Not</b> using std::copy, since we want to update m_totalSize too.
for (inputIterator f = first; f != afterLast; ++f) {
append(*f);
}
return *this; // allow chaining.
}
StringBuilder & AppendLine(const string_t &src) {
static chr lineFeed[] { 10, 0 }; // C++ 11. Feel the love!
m_Data.push_back(src + lineFeed);
m_totalSize += 1 + src.size();
return *this; // allow chaining.
}
StringBuilder & AppendLine() {
static chr lineFeed[] { 10, 0 };
m_Data.push_back(lineFeed);
++m_totalSize;
return *this; // allow chaining.
}
// TODO: AppendFormat implementation. Not relevant for the article.
// Like C# StringBuilder.ToString()
// Note the use of reserve() to avoid reallocations.
string_t ToString() const {
string_t result;
// The whole point of the exercise!
// If the container has a lot of strings, reallocation (each time the result grows) will take a serious toll,
// both in performance and chances of failure.
// I measured (in code I cannot publish) fractions of a second using 'reserve', and almost two minutes using +=.
result.reserve(m_totalSize + 1);
// result = std::accumulate(m_Data.begin(), m_Data.end(), result); // This would lose the advantage of 'reserve'
for (auto iter = m_Data.begin(); iter != m_Data.end(); ++iter) {
result += *iter;
}
return result;
}
// like javascript Array.join()
string_t Join(const string_t &delim) const {
if (delim.empty()) {
return ToString();
}
string_t result;
if (m_Data.empty()) {
return result;
}
// Hope we don't overflow the size type.
size_type st = (delim.size() * (m_Data.size() - 1)) + m_totalSize + 1;
result.reserve(st);
// If you need reasons to love C++11, here is one.
struct adder {
string_t m_Joiner;
adder(const string_t &s): m_Joiner(s) {
// This constructor is NOT empty.
}
// This functor runs under accumulate() without reallocations, if 'l' has reserved enough memory.
string_t operator()(string_t &l, const string_t &r) {
l += m_Joiner;
l += r;
return l;
}
} adr(delim);
auto iter = m_Data.begin();
// Skip the delimiter before the first element in the container.
result += *iter;
return std::accumulate(++iter, m_Data.end(), result, adr);
}
}; // class StringBuilder
함수 join()은 std:accumulate()를 사용 하고 첫 번 째 조작 수 에 메모 리 를 미리 남 겨 둔 사용자 정의 함수 입 니 다.
왜 StringBuilder::mdata 는 std::list 가 아 닌 std::vector 를 사용 합 니까?다른 용 기 를 사용 할 좋 은 이유 가 있 는 경 우 를 제외 하고 보통 std:vector 를 사용 합 니 다.
좋아,나 는 두 가지 이유 가 있어.
1.문자열 은 항상 용기 의 끝 에 추 가 됩 니 다.std::list 는 메모리 재분배 가 필요 없 는 상황 에서 이렇게 할 수 있 습 니 다.vector 는 연속 적 인 메모리 블록 을 사용 하여 이 루어 지기 때문에 하 나 를 사용 할 때마다 메모리 재 분 배 를 초래 할 수 있 습 니 다.
2.std::list 는 순차 액세스 에 상당히 유리 하고 mData 에서 하 는 유일한 액세스 작업 도 순서 입 니 다.
이 두 가지 실 현 된 성능 과 메모리 점용 상황 을 동시에 테스트 한 후에 그 중 하 나 를 선택 하 는 것 을 건의 할 수 있다.
성능 평가
성능 을 테스트 하기 위해 서,나 는 위 키 백과 에서 웹 페이지 를 얻 었 고,그 중 일 부 를 string 의 vector 에 썼 다.
그 다음 에 저 는 두 개의 테스트 함 수 를 작 성 했 습 니 다.첫 번 째 는 두 순환 에서 표준 함수 clock()을 사용 하고 std:accumulate()와 StringBuilder::ToString()을 호출 한 다음 에 결 과 를 인쇄 합 니 다.
void TestPerformance(const StringBuilder<wchar_t> &tested, const std::vector<std::wstring> &tested2) {
const int loops = 500;
clock_t start = clock(); // Give up some accuracy in exchange for platform independence.
for (int i = 0; i < loops; ++i) {
std::wstring accumulator;
std::accumulate(tested2.begin(), tested2.end(), accumulator);
}
double secsAccumulate = (double) (clock() - start) / CLOCKS_PER_SEC;
start = clock();
for (int i = 0; i < loops; ++i) {
std::wstring result2 = tested.ToString();
}
double secsBuilder = (double) (clock() - start) / CLOCKS_PER_SEC;
using std::cout;
using std::endl;
cout << "Accumulate took " << secsAccumulate << " seconds, and ToString() took " << secsBuilder << " seconds."
<< " The relative speed improvement was " << ((secsAccumulate / secsBuilder) - 1) * 100 << "%"
<< endl;
}
#ifdef __USE_POSIX199309
// Thanks to <a href="http://www.guyrutenberg.com/2007/09/22/profiling-code-using-clock_gettime/">Guy Rutenberg</a>.
timespec diff(timespec start, timespec end)
{
timespec temp;
if ((end.tv_nsec-start.tv_nsec)<0) {
temp.tv_sec = end.tv_sec-start.tv_sec-1;
temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;
} else {
temp.tv_sec = end.tv_sec-start.tv_sec;
temp.tv_nsec = end.tv_nsec-start.tv_nsec;
}
return temp;
}
void AccurateTestPerformance(const StringBuilder<wchar_t> &tested, const std::vector<std::wstring> &tested2) {
const int loops = 500;
timespec time1, time2;
// Don't forget to add -lrt to the g++ linker command line.
////////////////
// Test std::accumulate()
////////////////
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
for (int i = 0; i < loops; ++i) {
std::wstring accumulator;
std::accumulate(tested2.begin(), tested2.end(), accumulator);
}
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
using std::cout;
using std::endl;
timespec tsAccumulate =diff(time1,time2);
cout << tsAccumulate.tv_sec << ":" << tsAccumulate.tv_nsec << endl;
////////////////
// Test ToString()
////////////////
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
for (int i = 0; i < loops; ++i) {
std::wstring result2 = tested.ToString();
}
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
timespec tsToString =diff(time1,time2);
cout << tsToString.tv_sec << ":" << tsToString.tv_nsec << endl;
////////////////
// Test join()
////////////////
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
for (int i = 0; i < loops; ++i) {
std::wstring result3 = tested.Join(L",");
}
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);
timespec tsJoin =diff(time1,time2);
cout << tsJoin.tv_sec << ":" << tsJoin.tv_nsec << endl;
////////////////
// Show results
////////////////
double secsAccumulate = tsAccumulate.tv_sec + tsAccumulate.tv_nsec / 1000000000.0;
double secsBuilder = tsToString.tv_sec + tsToString.tv_nsec / 1000000000.0;
double secsJoin = tsJoin.tv_sec + tsJoin.tv_nsec / 1000000000.0;
cout << "Accurate performance test:" << endl << " Accumulate took " << secsAccumulate << " seconds, and ToString() took " << secsBuilder << " seconds." << endl
<< " The relative speed improvement was " << ((secsAccumulate / secsBuilder) - 1) * 100 << "%" << endl <<
" Join took " << secsJoin << " seconds."
<< endl;
}
#endif // def __USE_POSIX199309
다른 버 전:
이 백분율 봤 어?스 팸 메 일의 발 송 량 이 이 단계 에 이 르 지 못 합 니 다!
코드 사용
이 코드 를 사용 하기 전에 ostring 흐름 을 사용 하 는 것 을 고려 합 니 다.제 프 씨 의 논평 을 아래 에서 보 았 듯 이,그것 은 이 글 의 코드 보다 좀 빠르다.
이 코드 를 사용 하고 싶 을 수도 있 습 니 다.만약:
C\#경험 이 있 는 프로그래머 가 관리 하 는 코드 를 만 들 고 있 으 며,인터페이스 에 익숙 한 코드 를 제공 하고 싶 습 니 다.
앞으로.net 으로 전환 할 코드 를 만 들 고 있 습 니 다.가능 한 경 로 를 알려 주 고 싶 습 니 다.
어떤 이유 로,당신 은
이 코드 를 사용 하려 면 main 함수 에 따라 만 가능 합 니 다.StringBuilder 의 인 스 턴 스 를 만 들 고 Append(),AppendLine(),Add()로 값 을 부여 한 다음 ToString 함수 검색 결 과 를 호출 합 니 다.
아래 처럼:
int main() {
////////////////////////////////////
// 8-bit characters (ANSI)
////////////////////////////////////
StringBuilder<char> ansi;
ansi.Append("Hello").Append(" ").AppendLine("World");
std::cout << ansi.ToString();
////////////////////////////////////
// Wide characters (Unicode)
////////////////////////////////////
// http://en.wikipedia.org/wiki/Cargo_cult
std::vector<std::wstring> cargoCult
{
L"A", L" cargo", L" cult", L" is", L" a", L" kind", L" of", L" Melanesian", L" millenarian", L" movement",
// many more lines here...
L" applied", L" retroactively", L" to", L" movements", L" in", L" a", L" much", L" earlier", L" era.
"
};
StringBuilder<wchar_t> wide;
wide.Add(cargoCult.begin(), cargoCult.end()).AppendLine();
// use ToString(), just like .net
std::wcout << wide.ToString() << std::endl;
// javascript-like join.
std::wcout << wide.Join(L" _
") << std::endl;
////////////////////////////////////
// Performance tests
////////////////////////////////////
TestPerformance(wide, cargoCult);
#ifdef __USE_POSIX199309
AccurateTestPerformance(wide, cargoCult);
#endif // def __USE_POSIX199309
return 0;
}
지금 잠깐 만!
당신 은 우리 가 미리 최적화 하도록 설득 하려 고 하 는 것 입 니까?라 고 물 을 수 있 습 니 다.
아 닙 니 다.나 는 앞 당 겨 최적화 하 는 것 이 나 쁜 것 에 찬성한다.이런 최 적 화 는 결코 앞 당 긴 것 이 아니다.제때에 하 는 것 이다.이것 은 경험 을 바탕 으로 하 는 최적화 이다.나 는 내 가 과거 에 이런 특수 한 괴물 과 싸 웠 다 는 것 을 알 게 되 었 다.경험 에 기초 한 최적화(같은 곳 에서 두 번 넘 어 지지 않 음)는 미리 최적화 하 는 것 이 아니다.
좋은 웹페이지 즐겨찾기
