Проезд по строке для подсчета длины занимает больше времени, чем перемещение строки пару раз? - PullRequest
Новая
       21

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

0 голосов
/ 12 февраля 2020

Я написал следующие две функции. Во второй функции я использовал reserve(), чтобы не перераспределять память, но, к сожалению, вторая функция медленнее первой.

Я использовал режим выпуска и этот профилировщик ЦП в Visual Studio для подсчета времени. Во второй функции перераспределение происходит 33 раза. Итак, мой вопрос: на самом деле? Переход одной строки длины для подсчета длины занимает больше времени, чем перемещение этой строки 33 раза? 

string commpres2(string str)
{
    string strOut;
    int count = 0;
    for (int i = 0; i < str.length(); ++i)
    {
        ++count;
        if (i < str.length() - 1)
        {
            if (str[i + 1] != str[i])
            {
                strOut += str[i];
                strOut += to_string(count);
                count = 0;
            }
        }
        else
        {
            strOut += str[i] + to_string(count);
        }
    }
    return strOut.length() < str.length() ? strOut : str;
}

string commpres3(string str)
{
    int compressedLength = 0;
    int countConsecutive = 0;
    for (int i = 0; i < str.length(); ++i)
    {
        ++countConsecutive;
        if (i + 1 >= str.length() || str[i] != str[i + 1]) 
        {
            compressedLength += 1 + 
                to_string(countConsecutive).length();
            countConsecutive = 0;
        }
    }
    if (compressedLength >= str.length())
        return str;
    string strOut;
    strOut.reserve(compressedLength);
    int count = 0;
    for (int i = 0; i < str.length(); ++i)
    {
        ++count;
        if (i < str.length() - 1)
        {
            if (str[i + 1] != str[i])
            {
                strOut += str[i];
                strOut += to_string(count);
                count = 0;
            }
        }
        else
        {
            strOut += str[i] + to_string(count);
        }
    }
    return strOut;
}

int main()
{
    string str = "aabcccccaaa";

    //str.size ~ 11000000;
    for (int i = 0; i < 20; ++i)
        str += str;
    commpres2(str); //107ms //30,32% CPU
    commpres3(str); //147ms //42,58% CPU
}

Ответы [ 2 ]

0 голосов
/ 12 февраля 2020

33 выделения памяти против ~ 11000000 дополнительно, если операторы .

Вы делаете if (i < str.length() - 1) проверку в каждой итерации, но вам нужно сделать это только один раз.

Примите во внимание следующее: 

   if (str.empty()) return str;
   const auto last = str.length() - 1;
   for (size_t i = 0; i < last; ++i)
   {
       ++count;
       if (str[i + 1] != str[i])
       {
           strOut += str[i];
           strOut += to_string(count);
           count = 0;
       }
   }
   strOut += str[last] + to_string(count);

Некоторые советы по оптимизации:

  1. Вы можете избежать добавления счетчика, если он равен единице. В противном случае ваш алгоритм «сжимает» «ab c» в «a1b1c1».
  2. Добавьте индикатор того, что следующий байт является числом, а не обычным символом, чтобы различать guish между «a5» и "ааааа". Например, используйте 0xFF. Следовательно, «a5» кодируется в «a5», но «aaaaa» -> {'a', 0xFF, 5}
  3. Сохраняет счет в двоичной форме, а не в ASCII. Например, вы можете написать 3 (0x03) вместо «3» (0x33). Вы можете использовать один байт для хранения количества до 255. 
constexpr char COMPRESS_COUNT_SEPARATOR = 0xFF;

string compress(const string &str)
{
    string strOut;
    if (str.empty()) return strOut;

    unsigned char count = 0;
    const auto last = str.length() - 1;
    for (size_t i = 0; i < last; ++i)
    {
        ++count;
        if (str[i + 1] != str[i] || count == 255)
        {
            strOut += str[i];
            if (count > 1) {
               strOut += COMPRESS_COUNT_SEPARATOR;
               strOut += static_cast<char>(count);
            }
            count = 0;
        }
    }
    strOut += str[last];
    if (count) {
        strOut += COMPRESS_COUNT_SEPARATOR;
        strOut += static_cast<char>(count+1);
    }

    return strOut;
}

Или вы можете даже использовать 0x00 как COMPRESS_COUNT_SEPARATOR, потому что C -строки не могут содержать нулевые терминаторы, но std :: string может .

0 голосов
/ 12 февраля 2020

2-я функция выполняет больше работы, чем 1-я, поэтому, конечно, это займет больше времени. Профилирование кода должно было показать вам, где именно код тратит свое время. Например, 1-я функция циклически повторяет str самое большее 1 раз, но 2-я функция может l oop через те же str 2 раза, что по определению занимает больше времени.

И у вас есть Также не исключены все выделения памяти из 2-й функции. to_string() выделяет память, и вы вызываете ее много раз до и после вызова reserve(). Устранить все выделения to_string() довольно просто, используя std::snprintf() в локальном буфере и затем std::string::append(), чтобы добавить этот буфер к вашему выводу std::string.

Вы можете за go все предварительные вычисления и просто reserve() полную str длину, даже если вы не используете всю эту память. Вы не собираетесь использовать больше, чем исходная длина str в худшем случае (сжатие вообще невозможно): 

inline int to_buffer(size_t number, char *buf, size_t bufsize)
{
    return snprintf(buf, bufsize, "%zu", number);
}

string commpres3(const string &str)
{
    string::size_type strLen = str.length();
    string strOut;
    strOut.reserve(strLen);
    size_t count = 0;
    char buf[25];
    for (string::size_type i = 0; i < strLen; ++i)
    {
        ++count;
        if (i < strLen - 1)
        {
            if (str[i + 1] != str[i])
            {
                strOut += str[i];
                strOut.append(buf, to_buffer(count, buf, sizeof(buf)));
                count = 0;
            }
        }
        else
        {
            strOut += str[i];
            strOut.append(buf, to_buffer(count, buf, sizeof(buf)));
        }
        if (strOut.length() >= strLen)
            return str;
    }
    return strOut;
}

Или, если необходимо предварительно рассчитать, вы можете заменить 1-й набор to_string() вызывает что-то еще, что возвращает необходимую длину без динамического выделения памяти ( см. для идей). При расчете размера для резервирования вам не нужно фактически преобразовывать целое число 123 в выделенную строку «123», чтобы знать, что это займет 3 символа. 

inline int to_buffer(size_t number, char *buf, size_t bufsize)
{
    return snprintf(buf, bufsize, "%zu", number);
}

inline int to_buffer_length(size_t number)
{
    return to_buffer(number, nullptr, 0);
}

string commpres3(const string &str)
{
    string::size_type strLen = str.length();
    string::size_type compressedLength = 0;
    size_t countConsecutive = 0;
    for (string::size_type i = 0; i < strLen; ++i)
    {
        ++countConsecutive;
        if (i < (strLen - 1))
        {
            if (str[i + 1] != str[i])
            {
                strOut += 1 + to_buffer_length(countConsecutive);
                countConsecutive = 0;
            }
        }
        else
        {
            strOut += 1 + to_buffer_length(countConsecutive);
        }
    }
    if (compressedLength >= strLen)
        return str;
    string strOut;
    strOut.reserve(compressedLength);
    size_t count = 0;
    char buf[25];
    for (string::size_type i = 0; i < strLen; ++i)
    {
        ++count;
        if (i < strLen - 1)
        {
            if (str[i + 1] != str[i])
            {
                strOut += str[i];
                strOut.append(buf, to_buffer(count, buf, sizeof(buf)));
                count = 0;
            }
        }
        else
        {
            strOut += str[i];
            strOut.append(buf, to_buffer(count, buf, sizeof(buf)));
        }
    }
    return strOut;
}
...