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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 5.00
hofmn
Helter Skelter
 Аватар для hofmn
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
04.04.2013, 18:59     Оптимизация полного перебора #1
Пусть требуется подобрать пин-код длиной 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++
C++ Ускорение алгоритма перебора
Задача перебора элементов C++
C++ Программа метод перебора
C++ Поиск массива методом последовательного перебора
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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
Сообщений: 438
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
 Аватар для hofmn
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
05.04.2013, 15:44  [ТС]     Оптимизация полного перебора #4
Цитата Сообщение от kamre Посмотреть сообщение
Непонятно зачем что-то подбирать
Так в том и суть, чтобы подбирать. Допускается, что пин-кода я не знаю.
Его значение передано только для того, чтобы наглядно проверить правильность найденной комбинации.

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

Не по теме:

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

Ternsip
 Аватар для 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
Сообщений: 438
05.04.2013, 18:57     Оптимизация полного перебора #8

Не по теме:

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


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

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

Добавлено через 12 минут
hofmn, лично я бы сделал так.
1. Запускаю N потоков.
2. Передаю 1-ому первый вариант ключа.
3. Он проверяет его и, если он не корректен, то передает данные второму потоку. Второй делает тоже. И т.д.
Осталось решить, как это все Вы будете синхронизировать. (Первое, что напрашивается, так это специальная очередь для каждого потока)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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++
3582 / 1362 / 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
hofmn
Helter Skelter
 Аватар для hofmn
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
06.04.2013, 14:28  [ТС]     Оптимизация полного перебора #15
go, покажите еще ​​свой ​​класс ThreadPool, а то не могу разобраться с функцией enqueue.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 14:31     Оптимизация полного перебора #16
Вы можете положиться на удачу и перебирать символы рандомно, т.к. рандом действует равномерно то рано или поздно пин-код найдется.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
06.04.2013, 15:10     Оптимизация полного перебора #17
Цитата Сообщение от Dani Посмотреть сообщение
рандом действует равномерно
если сгенерировать бесконечно много чисел. А так теоретически хоть 100 одинаковых чисел подряд - на то он и рандом.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 15:56     Оптимизация полного перебора #18
Цитата Сообщение от Dani Посмотреть сообщение
Вы можете положиться на удачу
это можно, но 100 одинаковых чисел - должно сильно не везти, а вдруг пин-код и есть 100 одинаковых чисел? на то он и пин-код
pi_X_el
Заблокирован
06.04.2013, 15:58     Оптимизация полного перебора #19
1+2=3
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2013, 21:22     Оптимизация полного перебора
Еще ссылки по теме:

Объяснить алгоритм просто перебора C++
C++ При сортировке методом полного перебора массив сбивается

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

Или воспользуйтесь поиском по форуму:
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
06.04.2013, 21:22     Оптимизация полного перебора #20
Цитата Сообщение от hofmn Посмотреть сообщение
go, покажите еще ​​свой ​​класс ThreadPool, а то не могу разобраться с функцией enqueue.
Обычный пул потоков. enqueue добавляет в очередь новое задание.
Yandex
Объявления
06.04.2013, 21:22     Оптимизация полного перебора
Ответ Создать тему
Опции темы

Текущее время: 16:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru