C++ как ускорить алгоритм - работа со строками

Question

Я делаю программу, которая суммирует два двоичных числа. Все в порядке, и все работает, но мне нужно несколько советов, как ускорить алгоритм.

Я думаю об изменении всех переменных на динамически распределенные переменные. Это хорошая идея? Сделать все переменные динамическими, даже если я использую только одну или только длинные строки?

Мне нужен совет относительно использования динамических распределенных переменных.

Это пример один из моей функции проверки:

bool Correct(string v1, string v2){ 
for (unsigned int i = 0; i < v1.size(); ++i) { 
      if ((cin.fail())||((v1[i] != '1')&&(v1[i] != '0'))) 
       return false; 
       } 
for (unsigned int i = 0; i < v2.size(); ++i) { 
      if ((cin.fail())||((v2[i] != '1')&&(v2[i] != '0'))) 
       return false; 
       } 
    return true; 
} 

Когда я использую это:

bool JsouVstupySpravne(string *v1, string *v2){...} 

все обычаи, как v1.size() перестают работать.

Answer 1

Вы можете дать ссылки входных аргументов для начала:

bool Correct(string v1, string v2){ 

может быть

bool Correct(const string &v1, const string &v2){ 

Answer 2

При использовании указателя на строку вместо строки вам нужно изменить

string1.size() → string1->size() 
string1[x] → (*string1)[x] 

потому что синтаксис C++ требует другого.

Однако C++ позволяет также использовать «ссылки», которые не позволяют делать копии, сохраняя синтаксис строкового объекта. Для этого вы можете просто изменить:

bool Correct(string v1, string v2){ ... } 

в

bool Correct(const string& v1, const string& v2){ ... } 

Однако обратите внимание, что при сегодняшних компьютерах скорость выполнения зависит от многих факторов, «оптимизируя» код без предварительного твердые меры просто бред какой то. Вам нужно сначала найти, где время тратится (профилирование), и только потом вкладывать средства в создание кода быстрее (иногда, делая его более уродливым, к сожалению).

Answer 3

Если вы ищете рекомендации по оптимизации производительности, вам необходимо опубликовать код, отвечающий за большую часть времени выполнения. Вы не сказали, какую ОС вы используете, но должен быть доступен профайлер, который говорит вам об этом. В Linux это gprof, VC++ включает в себя один. Используйте это, чтобы узнать, где потрачено время, а также оптимизировать горячие точки.

Наилучшее повышение производительности обычно достигается с помощью эффективных алгоритмов, а затем оптимизирует реализацию. Как преобразовать строку бит в число? The Horner scheme приходит мне на ум как эффективный алгоритм, который уменьшает умножения.

Две точки стоит упомянуть в вашем коде:

1. Строки копируются каждый раз функция вызывается, но они не изменяются. Используйте ссылку const.
2. Угадав фрагмент, вы, похоже, используете std :: cin, чтобы преобразовать символ 0/1 в число.Это, вероятно, не очень эффективно, так как iostreams делают вещи, которые вам, вероятно, не нужны в вашем случае, например. обработка локали.

Наконец, есть std::bitset типа, который реализует то, что вы хотите делать, если вы можете жить с фиксированной длиной двоичной строки и размером макс. 64 бит.

unsigned long long Correct(const string &v1, const string &v2){ 
    auto const bits1 = std::bitset<64>(v1); 
    auto const bits2 = std::bitset<64>(v2); 

    return bits1.to_ullong() + bits2.to_ullong(); 
} 

boost::dynamic_bitset должна быть альтернатива, если вам нужно более длинные строки битов.