Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 5.00
hofmn
Helter Skelter
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
#1

Оптимизация полного перебора - C++

04.04.2013, 18:59. Просмотров 2253. Ответов 19
Метки нет (Все метки)

Пусть требуется подобрать пин-код длиной 4 символа (может содержать как цифры и буквы, так и другие символы). Использую метод полного перебора:
ааа
ааб
...
яяя
Как оптимизировать этот алгоритм? Какие есть альтернативы такому способу?

Моя реализация:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
string Find (string realPin)  // передаем код, который нужно подобрать
{
    string findedPin = "****";
 
    for (uint j = 32; j < 126; ++j)
    {
        findedPin[0] = j; // [a][*][*][*]
        for (uint k = 32; k < 126; ++k)
        {
            findedPin[1] = k; // [a][a][*][*]
            for (uint l = 32; l < 126; ++l)
            {
                findedPin[2] = l; // [a][a][a][*]
                for (uint m = 32; m < 126; ++m)
                {
                    findedPin[3] = m; // [a][a][a][a] 
                    if (findedPin == realPin) // aaaa == pin ? 
                    {
                        return findedPin;
                    }
                }
            }
        }
    }
    return "FATAL ERROR";
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2013, 18:59     Оптимизация полного перебора
Посмотрите здесь:

При сортировке методом полного перебора массив сбивается - C++
Массив сбивается ровно на единицу при сортировке. Понять не могу где же. Может у кого-нибудь была похожая проблема? #include...

Задача о рюкзаке методом полного перебора. Нужно пояснение по коду - C++
Здравствуйте, нужно пояснение по этому коду. Код не мой, также в нем много ошибок. Заранее спасибо. #include &lt;memory.h&gt; #include...

Поиск наибольшей общей подпоследовательности методом методом полного перебора - C++
Здравствуйте! Помогите пожалуйста с этим адом :wall: Нужно решить задачу о поиске наибольшей общей подпоследовательности методом...

Алгоритм перебора - C++
Всем доброго времени суток! Уважаемые форумчане подскажите алгоритм полного перебора, можно без кода, лишь ход действий. Конкретнее. В...

Ускорение алгоритма перебора - C++
Здравствуйте! В общем есть такая задачка: Имеются N(1 ≤ N ≤ 18) камней с массами W1, W2 , … WN. И, короче, нужно разложить камни на...

Задача перебора элементов - C++
Всем привет! Собственно есть задача с которой я не могу совладать. Загвоздка не в программировании, а в том чтоб придумать алгоритм, чтобы...

Программа метод перебора - C++
&quot;Составить программу, находящую максимальное и минимальное значе-ние функции F(x) с заданной точ-ностью , при этом применяется метод...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.04.2013, 19:06     Оптимизация полного перебора #2
Я бы немного разогнал сравнение.
Как-то так.
C++
1
if (*(int*)&findedPin[0] == *(int*)&realPin[0] )
На современных процессорах с предсказателями переходов это даст неслабое ускорение.
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
04.04.2013, 19:52     Оптимизация полного перебора #3
Цитата Сообщение от hofmn Посмотреть сообщение
Как оптимизировать этот алгоритм? Какие есть альтернативы такому способу?
Непонятно зачем что-то подбирать, если и так уже передано искомое значение. Фактически нужно только проверки добавить, которые есть в вашем коде.
C++
1
2
3
4
5
6
7
8
9
10
string Find (string realPin)  // передаем код, который нужно подобрать
{
  if (realPin.length() != 4)
    return "FATAL ERROR";
  for (int i = 0; i < 4; ++i) {
    if (realPin[i] < 32 || realPin[i] >= 126)
      return "FATAL ERROR";
  }
  return realPin;
}
hofmn
Helter Skelter
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
05.04.2013, 15:44  [ТС]     Оптимизация полного перебора #4
Цитата Сообщение от kamre Посмотреть сообщение
Непонятно зачем что-то подбирать
Так в том и суть, чтобы подбирать. Допускается, что пин-кода я не знаю.
Его значение передано только для того, чтобы наглядно проверить правильность найденной комбинации.

Добавлено через 19 часов 39 минут
Актуально.
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
05.04.2013, 16:10     Оптимизация полного перебора #5
о чём вообще речь? если условие стоит перебрать все 4хзначные коды, то и перебирай их все! Какая вообще может быть оптимизация, если про эти коды ничего не известно, кроме того, что они четырёхзначные?
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
05.04.2013, 16:12     Оптимизация полного перебора #6
diagon,
C++
1
2
3
if (isCheckPassword(findedPin))
{  
}
В идеале все выглядит так. Поэтому вряд ли это как-то ускорит алгоритм.

Не по теме:

kamre, Вам это тоже адресуется.

Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
05.04.2013, 16:26     Оптимизация полного перебора #7
Ваш алгоритм (функция) ничем не отличается от простой проверки -- если каждый элемент строки аргумента является буквой, тогда вернуть этот пин, иначе вернуть fatal error
Вот ваша функция :
C++
1
2
3
4
5
6
7
string Find (string realPin)  // передаем код, который нужно подобрать
{
    for (int i = 0; i < 4; i++)
        if (realPin[i] >= 126 || realPin[i] < 32)
            return "FATAL ERROR";
    return realPin;
}
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
05.04.2013, 18:57     Оптимизация полного перебора #8

Не по теме:

Цитата Сообщение от go Посмотреть сообщение
kamre, Вам это тоже адресуется.
Ну так если код изначально не соответствующий задаче был показан...


Если у функции isCheckPassword нет проблем с реентерабельностью, то можно весь диапазон вариантов разбить на части и запускать проверки параллельно.
hofmn
Helter Skelter
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
05.04.2013, 19:06  [ТС]     Оптимизация полного перебора #9
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Какая вообще может быть оптимизация
Собственно оптимизация перебора.

Цитата Сообщение от kamre Посмотреть сообщение
можно весь диапазон вариантов разбить на части и запускать проверки параллельно
Это интересно. Можно по подробнее о самой реализации?
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
05.04.2013, 19:13     Оптимизация полного перебора #10
Цитата Сообщение от hofmn Посмотреть сообщение
Собственно оптимизация перебора.
и что ты мне это дал? Я тебя спрашиваю, как эти методы применять к твоей задаче, а не ты меня.
Ты сказал, что
Цитата Сообщение от hofmn Посмотреть сообщение
Пусть требуется подобрать пин-код длиной 4 символа
Вот и подбирай! Никаких же ограничений нету на этот код. Следовательно, любой 4хсимвольный код может подходить. Следовательно, любая попытка отсечь часть кодов может лишить нас нужного. Ты сам то внимательно читал ссылки, которые даёшь?
hofmn
Helter Skelter
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
05.04.2013, 19:29  [ТС]     Оптимизация полного перебора #11
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Ты сам то внимательно читал ссылки, которые даёшь?
Да. Метод ветвей и границ отсеивает "нужное", а распараллеливание может существенно ускорить работу алгоритма (о его реализации для данного случая я и хочу услышать).
Почему же я не внимательно читаю?
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
05.04.2013, 19:52     Оптимизация полного перебора #12
Цитата Сообщение от hofmn Посмотреть сообщение
Собственно оптимизация перебора.
Да. Это и есть то, что Вам надо.

Добавлено через 12 минут
hofmn, лично я бы сделал так.
1. Запускаю N потоков.
2. Передаю 1-ому первый вариант ключа.
3. Он проверяет его и, если он не корректен, то передает данные второму потоку. Второй делает тоже. И т.д.
Осталось решить, как это все Вы будете синхронизировать. (Первое, что напрашивается, так это специальная очередь для каждого потока)
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.04.2013, 20:08     Оптимизация полного перебора #13
Самая простая оптимизация - заменить все циклы вида

C++
1
2
for (uint j = 32; j < 126; ++j)
    findedPin[0] = j; // [a][*][*][*]
на
C++
1
for (findedPin[0] = 32; findedPin[0] < 126; ++findedPin[0])
Чуть сложнее - запараллелить.

Немного более сложная оптимизация - работать с одним интом вместо 4 символов.

Ну и можно спустится до асма и поиграться с регистрами и прочей лоулевельщиной.
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
05.04.2013, 23:03     Оптимизация полного перебора #14
hofmn, самый простой ThreadPool дает выйгрышь в производительности в среднем в 2 раза(в лучшем случаи где-то в 3 раза).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <thread>
#include <string>
#include <queue>
#include <mutex>
#include <ctime>
 
static bool isCheck(const std::string& key)
{
    static std::string cur_key = "SAQZ"; // Password
    return key == cur_key;
}
 
std::string Find()  // передаем код, который нужно подобрать
{
    std::string findedPin = "****";
    
    for (char j = 'A'; j <= 'Z'; ++j)
    {
        findedPin[0] = j; // [a][*][*][*]
        for (char k = 'A'; k <= 'Z'; ++k)
        {
            findedPin[1] = k; // [a][a][*][*]
            for (char l = 'A'; l <= 'Z'; ++l)
            {
                findedPin[2] = l; // [a][a][a][*]
                for (char m = 'A'; m <= 'Z'; ++m)
                {
                    findedPin[3] = m; // [a][a][a][a] 
                    if (isCheck(findedPin)) // aaaa == pin ? 
                    {
                        return findedPin;
                    }
                }
            }
        }
    }
    return "FATAL ERROR";
}
 
#include "ThreadPool.h"
 
bool Work(std::string key)
{
    for (; key[1] <= 'Z'; ++(key[1]), key[2] = 'A') 
    {
        for (; key[2] <= 'Z'; ++(key[2]), key[3] = 'A')
        {
            for (; key[3] <= 'Z'; ++(key[3]))
            {
                if (isCheck(key))
                {   
                    andrey::ThreadPool::result = key;
                    return true;
                }
            }
        }
    }
    return false;
}
 
int main()
{
    clock_t time;
 
    std::string res;
    clock_t t1 = 0, t2 = 0;
 
    for (int i = 0; i < 100; ++i) 
    {
 
        time = clock();
 
        res = Find();
 
        time = clock() - time;
        t1 += time;
 
        time = clock();
 
        andrey::ThreadPool thrpl(9);
 
        // algorithm
        for (std::string key = "AAAA"; key[0] <= 'Z'; ++(key[0]))
        {
            thrpl.enqueue(Work, key);
        }
 
        time = clock() - time;
        t2 += time;
    }
 
    printf("%lf\n", (double)t1 / CLOCKS_PER_SEC);
    printf("%lf\n", (double)t2 / CLOCKS_PER_SEC);
 
    std::cout << res << std::endl;
    std::cout << andrey::ThreadPool::result << std::endl;
 
    return 0;
}
Добавлено через 5 минут
http://d.pr/i/dWAC
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2013, 14:28     Оптимизация полного перебора
Еще ссылки по теме:

Объяснить алгоритм просто перебора - C++
доброго времени суток! мой вопрос, наверное, покажется Вам очень глупым, но очень нужна ваша помощь! задачка не сложная:У Вас есть N...

Алгоритм перебора цифр 0 и 1 в четырехзначном числе - C++
Всем привет, помогите пожалуйста, уже третий день не могу придумать алгоритм перебора чисел 0 и 1. Должно получиться к примеру вот так: ...

Решение нелинейного уравнения методом перебора - C++
Решить уравнение sin(1/x)=0 методом перебора на промежутке x = .

Найти все варианты перебора циклов - C++
Народ помогите написать часть программы кто сможет Условие: Найти все варианты перебора циклов с условием что A&gt;C&gt;B к примеру......

Алгоритм перебора всех возможных значений - C++
Здравствуйте, суть задачи алгоритма состоит в поиске всех возможных сочетаний букв в слове. Параметром в функцию передаются вектор,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
hofmn
Helter Skelter
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
06.04.2013, 14:28  [ТС]     Оптимизация полного перебора #15
go, покажите еще ​​свой ​​класс ThreadPool, а то не могу разобраться с функцией enqueue.
Yandex
Объявления
06.04.2013, 14:28     Оптимизация полного перебора
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru