1

Подскажите пожалуйста, можно ли оптимизировать мою функцию перебора массива ?

vector<string> brute(vector<string> alphabet, unsigned int max)
{
    vector<int> temp{ -1 };
    vector<string> result;

    for (size_t i = 0; i < max; i++)
    {
        bool over = true;

        for (size_t n = 0; n < temp.size(); n++)
        {
            if (abs(temp[n]) < alphabet.size() - 1) {
                over = false;
            }
        }

        if (over == true)
        {
            for (int n = 0; n < temp.size(); n++)
            {
                temp[n] = 0;
            }
            temp.resize(temp.size() + 1);
            string str;
            for (int n = 0; n < temp.size(); n++)
            {
                str = str + alphabet[temp[n]];
            }
            result.push_back(str);
        }
        else
        {
            temp[0] = temp[0] + 1;
            for (int n = 0; n < temp.size() - 1; n++)
            {
                if (temp[n] > alphabet.size() - 1)
                {
                    temp[n] = 0;
                    temp[n + 1] = temp[n + 1] + 1;
                }
            }

            string str;
            for (int n = 0; n < temp.size(); n++)
            {
                str = str + alphabet[temp[n]];
            }
            result.push_back(str);
        }

    }
    return result;

}
2
  • 1
    а что именно было задачей, лучше условие приложите, возможно есть другой алгоритм.
    – pavel
    15 мая 2016 в 20:49
  • @pavel ну я просто бы хотел перебирать всевозможные комбинации строк с определёнными символами, так то оно отлично всё работает но мне кажется что это можно сделать проще и ускорить работу алгоритма 15 мая 2016 в 20:56

2 ответа 2

1

Ну, я бы поступил так:

vector<string> brute(const vector<string>& al, int max)
{
    vector<string> res = al;
    for(int pos = 0; res.size() < max; ++pos)
    {
        for(int sym = 0; sym < al.size() && res.size() < max; ++sym)
            res.push_back(res[pos] + al[sym]);
    }
    return res;
}

Правда, не понимаю логики перебора с подстроками (почему алфавит - набор строк, а не символов), ну да хозяин-барин, вдруг он точно знает, что пароль состоит только из подстрок "khren" и "podberesh" в каком-то порядке...

1

Правильный ответ на Ваш вопрос: конечно можно. Для начала нужно избавиться от выделения динамической памяти. Она выделяется там, где вы добавляете что-то к строке или к вектору или делаете resize. Память нужно выделить сразу где-то в глобальной области. Затем нужно избавиться от операторов типа + и им подобных, кроме дикой траты ресурсов в угоду удобству от них мало пользы. Короче, напишите всё как будто на чистом Си, тогда будет значительно быстрее. Если бы я понимал суть алгоритма, то, скорее всего, сообщил бы, что он написан не оптимально, но я не знаю, что Вы хотите, а читать код без пояснений как-то не хочется.

2
  • я думаю имелось ввиду оптимизировать сложность алгоритма, иначе универсальный ответ - напиши на ассемблере :)
    – pavel
    16 мая 2016 в 16:04
  • Ну тогда пусть человек даст алгоритм в некоем описании, а не только код. Когда дают код, я смотрю код, а в годе полно "очевидных универсальных замедлителей", о чём я и сообщил. Если там перебор, то алгоритм-то скорее всего теоретически уже не ускоряется, нужно смотреть контекст его использования и играть на этом.
    – Zealint
    16 мая 2016 в 16:07

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.