C++ - токенизатор очень медленный

Question

Я просто не понимаю, что делаю неправильно. Показанная ниже функция токенизатора Unicode очень медленная. Может быть, кто-нибудь может дать мне подсказку, как ускорить его? Спасибо за любую помощь. Кстати, ustring - Glib::ustring. sep1 являются сепараторы, которые не должны отображаться в результатах sep2 являются сепараторы, которые должны быть одиночные маркеры в результате

void tokenize(const ustring & u, const ustring & sep1, 
     const ustring & sep2, vector<ustring> & tokens) { 
    ustring s; 
    s.reserve(100); 
    ostringstream os; 
    gunichar c; 
    for (int i = 0; i < u.length(); i++) { 
     c = u[i]; 
     if (sep1.find(c) != ustring::npos) { 
      tokens.push_back(s); 
      s = ""; 
     } 
     else if (sep2.find(c) != ustring::npos) { 
      tokens.push_back(s); 
      s = ""; 
      s.append(1, c); 
      tokens.push_back(s); 
      s = ""; 
     } 
     else { 
      s.append(1, c); 
     } 
    } 
    if (s!="") 
    tokens.push_back(s); 
} 

теперь я изменил его (в настоящее время от 1 до 2-х секунд):

ustring s; 
s.reserve(100); 
ostringstream os; 
gunichar c; 

set<gunichar> set_sep1; 
int i=0; 

for (i=0;i<sep1.size();i++) 
{ 
    set_sep1.insert(sep1[i]); 
} 

set<gunichar> set_sep2; 
for (i=0;i<sep2.size();i++) 
{ 
    set_sep2.insert(sep2[i]); 
} 

int start_index=-1; 
int ulen=u.length(); 
i=0; 
for (ustring::const_iterator it=u.begin();it!=u.end();++it) 
{ 
    c=*it; 
    if (set_sep1.find(c)!=set_sep1.end()) 
    { 
     if (start_index!=-1 && start_index<i) 
      tokens.push_back(u.substr(start_index,i-start_index)); 
     start_index=i+1; 
     s=""; 
    } 
    else if (set_sep2.find(c)!=set_sep2.end()) 
    { 
     tokens.push_back(s); 
     s=""; 
     tokens.push_back(s); 
     start_index=i+1; 
     s=""; 
    } 
    i++; 
} 
if (start_index!=-1 && start_index<ulen) 
    tokens.push_back(u.substr(start_index,ulen-start_index)); 

Answer 1

к вещам, которые могут быть "очень-очень медленно" здесь:

1. ustring::length()
2. ustring::append()
3. Произвольный доступ к ustring через operator[]: например, c=u[i];

Попробуйте следующее:

1. Вместо вызова u.length() в цикле, сохранить длину в переменном и в цикле по сравнению с этим переменной
2. Добавляют символы текущих маркеров в a ostringstream или wostringstream вместо ustring
3. Итерация через ustring с использованием итераторов вместо индексов с произвольным доступом.

Пример:

for(ustring::const_iterator it = u.cbegin(); it != u.cend(); it++) 
{ 
    c = *it; 
    //implementation follows 
} 

Answer 2

Я думаю, что следующее значительно ускорит ваш код, но это небольшая работа, чтобы узнать. В настоящее время вы находитесь:

1. Итерирование каждого символа u.
2. выполнить поиск в sep1, чтобы увидеть, является ли этот символ среди разделителей.
3. добавление один знак одновременно, при необходимости.

Предполагая, что ваш список разделителей меньше строк вы разбор, вы, вероятно, лучше делать следующее:

1. Для каждого разделителя, сделать находку, чтобы увидеть, если разделитель в string
2. Если найдено, добавьте всю подстроку за один раз и выполните поиск на подстроке remaing.

Вторая оптимизация - заказать ваши разделители с точки зрения наиболее вероятных результатов. Если, например, «,» является наиболее часто используемым разделителем, убедитесь, что поиск выполняется первым. Если один разделитель намного горяче других, это будет иметь большое значение.