제가 현재 찾으려고 하는 것은 문자열에 대한 처리를 할 때 가장 고성능을 낼 수 있는 자료 구조 입니다. <div><span style="font-size:9pt;line-height:1.5;">사용하고 있는 언어가 C++인지라 C++에 있는 자료 구조로 말씀 드리죠..</span></div> <div><br></div> <div>성능이 높아야 하는 연산은</div> <div>1. random insertion: 임의의 위치에 한 문자(길이 1) 혹은 문자열(길이 2이상)을 입력</div> <div>2. 빠른 sequential read: 맨 첫 문자부터 특정 위치까지의 발생하는 문자의 개수를 세야 함</div> <div>3. 삭제나 수정 연산은 발생하지 않습니다.</div> <div><br></div> <div>기본적으로 vector<char>나 string을 통해서 삽입, 읽기를 수행해 보면 임의의 위치에 삽입 하는 것은 매우 느립니다.</div> <div>가령 다음과 같은 코드가 있다고 하죠.</div> <div><br></div> <div>vector<char> vec;</div> <div>.... 4 Gigabyte의 push_back() 연산 수행</div> <div>vec.insert(vec.begin() + 1, 'A');</div> <div><br></div> <div>map<char, uint64_t> occ;</div> <div>for(auto c : vec) {</div> <div> ++occ[c];</div> <div>}</div> <div><br></div> <div>삽입 연산에 대한 대안물로 rope라는 자료 구조를 찾아서 적용해 봤더니 좀 더 빨라 지더군요..</div> <div><br></div> <div>다행인 것은 입력되는 문자열에서 나타날 수 있는 문자의 갯수가 한정되어 있습니다(01234567) <- 이것만 나타납니다.</div> <div>예를 들어서, 11111222222222000000033334343444444444444444222233312343213435677777777766666666</div> <div>이런 식입니다.</div> <div><br></div> <div>run length 인코딩을 수행하면 좀 더 읽고 쓰기 하는데 들어가는 비용을 줄일 수 있을 것 같습니다.</div> <div><br></div> <div>정리하면, 이런 문자열은 임의의 위치에서 다시 새로운 문자를 삽입 해야 하고, 특정 위치까지 문자 별 발생 횟수를 세어야 합니다. 이런 연산의 성능이 높은 자료 구조가 있다면 정보 공유좀 부탁 드립니다.</div>
댓글 분란 또는 분쟁 때문에 전체 댓글이 블라인드 처리되었습니다.