Почему оператор == для сравнения строк по линейному времени (на первый взгляд) относительно длины любой строки? - PullRequest
Новая
       49

Почему оператор == для сравнения строк по линейному времени (на первый взгляд) относительно длины любой строки?

3 голосов
/ 08 февраля 2020 
#include <iostream>
#include <chrono>
#include <string>
using namespace std::chrono;
int main(int arc, char* argv[]) {
    const std::string password = "a";
    int correct = 1;
    auto start = high_resolution_clock::now();
    if(password != argv[1])
        correct = 0;
    auto end = high_resolution_clock::now();
    auto elapsed = duration_cast<nanoseconds> (end-start).count();
    std::cout << "time: " << elapsed << "\n";
    return correct;
}

В среднем требуется> 50% больше времени для сравнения "a" == "b" и "a" == "bbbbbbbbbbbbb ..." (длина ~ 250).

Почему это тот случай? Разве функция сравнения строк не должна прерываться сразу же после того, как увидит, что первые символы не равны (или что длина строк не равна)?

В ряде ссылок также упоминается, что сравнение строк является линейной сложностью в длине обеих входных строк (например, https://en.cppreference.com/w/cpp/string/basic_string/operator_cmp). Я не понимаю, почему это так. Любая помощь очень ценится.

Ответы [ 2 ]

2 голосов
/ 08 февраля 2020

Строка == operator основана на методе compare(). Глядя на реализацию, доступную на моем TDMG * ​​1012 *, я обнаружил следующее: 

// This is the overloaded one called when you compare to argv[1]
  template<typename _CharT, typename _Traits, typename _Alloc>
    int
    basic_string<_CharT, _Traits, _Alloc>::
    compare(const _CharT* __s) const
    {
      __glibcxx_requires_string(__s);
      const size_type __size = this->size();
      const size_type __osize = traits_type::length(__s);
      const size_type __len = std::min(__size, __osize);
      int __r = traits_type::compare(_M_data(), __s, __len);
      if (!__r)
    __r = _S_compare(__size, __osize);
      return __r;
    }

Как вы можете видеть, перед сравнением длин, которые он сначала вызывает, это traits_type::compare(), что в основном является memcmp(): 

      static int
      compare(const char_type* __s1, const char_type* __s2, size_t __n)
      { return __builtin_memcmp(__s1, __s2, __n); }

Поэтому, если я не ошибаюсь, сравнение будет линейным временем, как вы упомянули.

1 голос
/ 08 февраля 2020

Первое, что следует здесь отметить, это то, что operator==() внутренне использует метод compare(), как упоминалось здесь .

Как отмечалось здесь и здесь , многие реализации метода compare() полагаются на memcmp. (или некоторая эквивалентная функция) В этой реализации C вы можете видеть, что алгоритм, используемый memcmp, имеет линейную сложность по времени. Эта конкретная реализация приведена ниже. 

int
memcmp (const PTR str1, const PTR str2, size_t count)
{
  register const unsigned char *s1 = (const unsigned char*)str1;
  register const unsigned char *s2 = (const unsigned char*)str2;

  while (count-- > 0)
  {
    if (*s1++ != *s2++)
      return s1[-1] < s2[-1] ? -1 : 1;
  }
  return 0;
}

Из-за этой внутренней реализации метода compare() и задействованных оптимизаций вам, вероятно, потребуются строки большего размера, чтобы иметь возможность наблюдать линейный тренд в время, необходимое для выполнения метода.

...