Сложность токенизатора C++ против strtok_r

Я задаю этот вопрос, потому что я переместил свой токенизатор из strtok_r в эквивалентную версию на C++. Я должен использовать strtok_r вместо strtok, потому что большую часть времени мне приходится выполнять две вложенные токенизации.

Алгоритм strtok_r примерно такой:

char *end_token, *token, *word ;
// fill 'word'
token = strtok_r (word, " ", &end_token) ;
while (token != NULL) {
  // do something
  token = strtok_r (NULL, " ", &end_token) ;
}

И версия C++ выглядит так (взято из другого поста здесь):

string mystring, token ;
size_t next_token ;
// fill 'mystring'
while (token != mystring) {
    next_token = mystring.find_first_of (" ") ;
    token = mystring.substr (0, next_token) ;
    mystring = mystring.substr (next_token + 1) ;
    // do something
}

Теперь вопрос: почему версия C++ так сильно относится к версии C? Для длинных строк мне приходится ждать около 10 секунд с версией C++, в то время как версия C выполняется мгновенно с теми же строками. Итак, похоже, что версия C++ имеет более высокую сложность... Что вы думаете об этом?


c c++ tokenize strtok
person nicolati    schedule 19.08.2015    source источник
comment
strtok изменяет входную строку, в то время как версия C++ делает копии. Хотя у них может быть один и тот же конечный результат, две версии идут совершенно разными путями, чтобы достичь цели.   -  person Chad    schedule 19.08.2015
comment
Возможно, вы захотите увидеть, как разбить строку С++, так как это более эффективно: stackoverflow.com /questions/236129/split-a-string-in-c Как выглядят ваши данные и что вы пытаетесь с ними сделать?   -  person NathanOliver    schedule 19.08.2015
comment
Если вы тестируете постоянные строки, функции с эквивалентными _builtin всегда будут выигрывать, потому что они свернуты.   -  person technosaurus    schedule 19.08.2015
comment
Может быть, потому что библиотека C была написана в то время, когда ресурсы были ограничены, а эффективность предпочиталась аккуратному дизайну, в то время как C++ больше заботился о надежности и дизайне - но это только мое мнение :-)   -  person Serge Ballesta    schedule 19.08.2015

Ответы (1)


arrow_upward
2
arrow_downward

strtok() изменяет строку, заменяя разделитель токена нулевым ограничителем. Если ваша длинная строка имеет n токенов, функция просто выполняет итерацию по строке, изменяя n символов на нуль, что очень быстро.

В вашей альтернативе C++ вы делаете 2 * n копий строк, что означает потенциально 2 * n операций выделения плюс полную копию (очень длинной) оставшейся строки, которая намного тяжелее, чем первая альтернатива. Разница в том, что вы не обязаны изменять исходную строку.

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

string mystring, token ;
size_t cur_token=0, next_token ;
// fill 'mystring'
do {
    next_token = mystring.find_first_of (" ", cur_token) ;
    token = mystring.substr (cur_token, next_token-cur_token);  // next_token-(nex_token==string::npos ? 0:cur_token) would be cleaner
    if (next_token!=string::npos) 
        cur_token = next_token+1; 
    // do something with token;
} while (next_token!=string::npos);

Демо

person Christophe    schedule 19.08.2015
comment
Благодарю вас! Я попробую. Кажется очень интересным! Я не уловил, что мой алгоритм должен был выполнять такое большое количество копий и распределений... :( - person nicolati; 20.08.2015
comment
Привет, Кристоф, я попробовал твой алгоритм. Это намного лучше, чем у меня, но все же хуже, чем strtok. Поскольку он примерно в 5 раз быстрее моего и, возможно, в 2 раза медленнее, чем strtok, я все равно буду его использовать. Я могу выжить с 2X :) Спасибо - person nicolati; 21.08.2015