Предложение подходящей строки с использованием алгоритма расстояния Левенштейна слишком медленное

Question

У меня есть функция, которая возвращает sf :: EventType на основе строки, предоставленной пользователем. Если совпадений нет, функции возвращают sf :: nullopt. Но я хотел бы напечатать предложенный, действительный, sf :: EventType, который наиболее близок к тому, что предоставил пользователь, чтобы помочь с опечатками и т. Д. c.

Существует «только» 13 действительных sf: : EventType, которые должны быть проверены на самое близкое соответствие, и я предполагаю, что пользователь не введет какую-то смешную длинную строку.

На моем ноутбуке процессор Intel m3-7Y30 я проверил скорость функций на обеих отладках и режим выпуска:

~ 45 секунд при отладке ~ 3 секунды при выпуске

Огромная разница, но все же я чувствую, что 3 секунды - это немного, учитывая, что пользователь может предоставить от 5 до 100 типов событий.

Учитывая эти результаты, я сомневаюсь, что этот подход к предложению действительного sf :: EventType мог бы быть достаточно оптимизирован, чтобы сделать его жизнеспособным, но если это возможно, я хотел бы знать, как это сделать. Если нет, я хотел бы предложить альтернативу, которая по-прежнему печатает предложение, независимо от того, как далеко находится предоставленная строка.

Соответствующий код выглядит следующим образом:

convertToSfEvent

std::optional<sf::Event::EventType> EventFileReader::convertToSfEvent(std::string_view event)
    {
        if      (event == "Closed")              return sf::Event::EventType::Closed;
        else if (event == "Resized")             return sf::Event::EventType::Resized;
        else if (event == "LostFocus")           return sf::Event::EventType::LostFocus;
        else if (event == "GainedFocus")         return sf::Event::EventType::GainedFocus;
        else if (event == "TextEntered")         return sf::Event::EventType::TextEntered;
        else if (event == "KeyPressed")          return sf::Event::EventType::KeyPressed;
        else if (event == "KeyReleased")         return sf::Event::EventType::KeyReleased;
        else if (event == "MouseWheelScrolled")  return sf::Event::EventType::MouseWheelScrolled;
        else if (event == "MouseButtonPressed")  return sf::Event::EventType::MouseButtonPressed;
        else if (event == "MouseButtonReleased") return sf::Event::EventType::MouseButtonReleased;
        else if (event == "MouseMoved")          return sf::Event::EventType::MouseMoved;
        else if (event == "MouseEntered")        return sf::Event::EventType::MouseEntered;
        else if (event == "MouseLeft")           return sf::Event::EventType::MouseLeft;
        else
        {
            // Heres is where I search for a match, and the recursion madness starts
            auto smallest_required_change{ INT_MAX };
            auto closest_string{ std::string() };
            for (auto event_type : this->event_types)
            {
                auto result{ levensteinDistance(event, event_type, event.length(), event_type.length()) };

                if (result < smallest_required_change)
                {
                    smallest_required_change = result;
                    closest_string = event_type;
                }
            }

            std::cerr << "Could not recognize event_type token: '" << event << "' did you mean: '" << closest_string << "'?" << "\n";

            return std::nullopt;
        }
    }

levensteinDistance

std::size_t EventFileReader::levensteinDistance(std::string_view first, std::string_view second, std::size_t first_pos, std::size_t second_pos)
    {
        static auto one{ std::size_t(1) };

        if (!first_pos)
            return first_pos;

        if (!second_pos)
            return second_pos;

        if (first[first_pos - one] == second[second_pos - one])
            return levensteinDistance(first, second, first_pos - one, second_pos - one);

        return 1 + std::min({ levensteinDistance(first, second, first_pos,       second_pos - one),
                              levensteinDistance(first, second, first_pos - one, second_pos),
                              levensteinDistance(first, second, first_pos - one, second_pos - one)
                           });
    }

Answer 1

Ваша levenshtein реализация является рекурсивной и медленной, вы можете изменить ее на более быструю, например (источник: https://rosettacode.org/wiki/Levenshtein_distance):

// Compute Levenshtein Distance
// Martin Ettl, 2012-10-05

size_t uiLevenshteinDistance(const std::string &s1, const std::string &s2)
{
  const size_t m(s1.size());
  const size_t n(s2.size());

  if( m==0 ) return n;
  if( n==0 ) return m;

  size_t *costs = new size_t[n + 1];

  for( size_t k=0; k<=n; k++ ) costs[k] = k;

  size_t i = 0;
  for ( std::string::const_iterator it1 = s1.begin(); it1 != s1.end(); ++it1, ++i )
  {
    costs[0] = i+1;
    size_t corner = i;

    size_t j = 0;
    for ( std::string::const_iterator it2 = s2.begin(); it2 != s2.end(); ++it2, ++j )
    {
      size_t upper = costs[j+1];
      if( *it1 == *it2 )
      {
          costs[j+1] = corner;
      }
      else
      {
        size_t t(upper<corner?upper:corner);
        costs[j+1] = (costs[j]<t?costs[j]:t)+1;
      }

      corner = upper;
    }
  }

  size_t result = costs[n];
  delete [] costs;

  return result;
}

Или Вы можете проверить эту страницу для вдохновения: https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C