성능이 높아야 하는 연산은

1. random insertion: 임의의 위치에 한 문자(길이 1) 혹은 문자열(길이 2이상)을 입력

2. 빠른 sequential read: 맨 첫 문자부터 특정 위치까지의 발생하는 문자의 개수를 세야 함

3. 삭제나 수정 연산은 발생하지 않습니다.

기본적으로 vector<char>나 string을 통해서 삽입, 읽기를 수행해 보면 임의의 위치에 삽입 하는 것은 매우 느립니다.

가령 다음과 같은 코드가 있다고 하죠.

vector<char> vec;

.... 4 Gigabyte의 push_back() 연산 수행

vec.insert(vec.begin() + 1, 'A');

map<char, uint64_t> occ;

for(auto c : vec) {

   ++occ[c];

}

삽입 연산에 대한 대안물로 rope라는 자료 구조를 찾아서 적용해 봤더니 좀 더 빨라 지더군요..

다행인 것은 입력되는 문자열에서 나타날 수 있는 문자의 갯수가 한정되어 있습니다(01234567) <- 이것만 나타납니다.

예를 들어서, 11111222222222000000033334343444444444444444222233312343213435677777777766666666

이런 식입니다.

run length 인코딩을 수행하면 좀 더 읽고 쓰기 하는데 들어가는 비용을 줄일 수 있을 것 같습니다.

정리하면, 이런 문자열은 임의의 위치에서 다시 새로운 문자를 삽입 해야 하고, 특정 위치까지 문자 별 발생 횟수를 세어야 합니다. 이런 연산의 성능이 높은 자료 구조가 있다면 정보 공유좀 부탁 드립니다.