Оптимизация кода по обращению к памяти

#cpp #c #алгоритм #оптимизация #память

Необходимо написать оптимальную по обращению к памяти функцию для обрезки пробелов
справа. Сама обрезка сложностей не вызывает, непонятно, что можно сделать для оптимизации
и можно ли вообще оптимизировать такую реализацию.

void TrimRight(char* s) {
size_t len = strlen(s);
char* iter = s + len - 1;
if (*iter != ' ') {
    // Если последний символ не пробел, 
    // то и обрезать нечего
    return;
}
while (*iter == ' ' && iter != s) {
    // Идти от конца к началу, 
    // пока не кончатся пробелы либо строка
    iter--;
}
if (iter == s) {
    // Если строка пройдена
    // и полностью состоит из пробелов
    // то результатом будет пустая строка
    *iter = '\0';
}
else {
    // Если пройдены все пробелы 
    // и поиск дошел до первого не пробела,
    // то заменить первый пробел на конец строки.
    *(iter + 1) = '\0';
}

}

    

Ответы

Ответ 1

https://ideone.com/EwHSCG

#include 
#include 

using namespace std;

char *trimRight(char *s)
{
  char *spc=0, *p=s;

  while (*p)
    if (*p == ' ')
      for (spc=p; *++p==' '; );
    else
      ++p;

  if (spc && p!=s && p[-1]==' ') *spc = 0;

  return s;
}

int main()
{
  char s[256];

  cout << '"' << trimRight(strcpy(s, ""))                  << '"' << endl;
  cout << '"' << trimRight(strcpy(s, "abc qwe zzz   "))    << '"' << endl;
  cout << '"' << trimRight(strcpy(s, "abc  qwe  zzz   "))  << '"' << endl;
  cout << '"' << trimRight(strcpy(s, "abc  qwe  zzz   u")) << '"' << endl;

  return 0;
}


Ответ 2

Альтернативный вариант - поиск последнего не пробельного символа для уменьшения количества
сравнений:

void Trim_Naive(char * p_char)
{
    auto p_begin_or_last_non_ws{p_char};
    for(;;)
    {
        switch(*p_char)
        {
            case '\0':
            {
                break;
            }
            case ' ':
            {
                ++p_char;
                continue;
            }
            default:
            {
                p_begin_or_last_non_ws = p_char;
                ++p_char;
                continue;
            }
        }
        break;
    }
    if(' ' == *p_begin_or_last_non_ws)
    {
        p_begin_or_last_non_ws[0] = '\0';
    }
    else
    {
        p_begin_or_last_non_ws[1] = '\0';
    }
    return;
}


Поглядим на производительность.:

chars count = 64000000
trailing spaces_percent = 1
spaces percent = 20
strlen 63999999 3342
strlen naive 63999999 21940
OP    3321
Q     136068
naive 27858

chars count = 64000000
trailing spaces_percent = 50
spaces percent = 20
strlen 63999999 3105
strlen naive 63999999 22620
OP    20668
Q     77093
naive 27658

chars count = 64000000
trailing spaces_percent = 99
spaces percent = 20
strlen 63999999 3064
strlen naive 63999999 22692
OP    41996
Q     20818
naive 24656


Выводы:


Библиотечный strlen оптимизирован и работает в разы быстрее наивной реализации. 
Итерация по массиву в обратную сторону медленнее.
В реалистичной ситуации, когда сравнительно длинная строка оканчивается сравнительно
небольшим количеством пробелов, код из вопроса работает отлично. Когда непробельные
символы встречаются только в начале строки, он несколько деградирует.
Вариант из ответа Qwertiy наоборот, в реалистичной ситуации работает очень плохо,
и достигает приемлемой производительности когда непробельные символы встречаются только
в начале.
Вариант с наивной реализацией из этого ответа показывает приемлемую производительность
независимо от содержимого строки.


Ответ 3

По возможности сравниваем с пробелом не по байту, а целыми словами

// trim tail spaces from `char str[]`
// return str
//   and it's new length in second argument
char *
trim2 (char str[], size_t *len)
{
  size_t dummy;
  if (!len)
    len = &dummy;
  char *t = str + strlen(str) - 1;
  size_t mask = sizeof(char *) - 1,
    blank = (sizeof(char *) == 4) ? 0x20202020 : 0x2020202020202020ULL;

  while (t >= str) {
    if (*t != ' ')
      return t[1] = 0, *len = t - str + 1, str;

    if (((size_t)t & mask) == 0 && t - str > mask) {
      // the address is aligned and the length is sufficient 
      // compare by words
      size_t *p = (size_t *)(t - (mask + 1));
      while (p >= (size_t *)str) {
    if (*p != blank) 
      break;  // somewhere in this word there is no space
    p--;
      }

      // again compare each byte
      t = (char *)p + mask;
      continue;
    }
    t--;
  }

  // empty 
  return *str = 0, *len = 0, str;
}


Ответ 4

void TrimRight(char* s) {
  char* space = null;  // Изначально пробелов нет
  // цикл до конца строки
  while (*s != '\0') {
    if (*s == ' ') {  // если нашли пробел
      // и до этого пробелов не было
      if (space == null)
        space = s;  // запомнили позицию
    } else  // если нашли не пробел
      space = null;  // забыли, что видели пробел
    s++;
  }
  // если таки нашли пробел
  if (space != null)
    *space = '\0';  // обрезали строку
}