Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Клуб программистов > Свободное общение
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 13.08.2020, 13:23   #1
Danila96
 
Регистрация: 19.01.2014
Сообщений: 6
По умолчанию Брут-форс, много ли требуется ресурсов?

Постарался в заголовке передать максимум запроса, надеюсь его не посчитают клик-бейтным

Для начала - хотел написать ТЗ, что бы методом перебора найти наименьшую комбинацию в массиве данных. Если что, это никак не связано с криминалом и хакингом
Открыл гугл, нашел сайт, где онлайн показывает количество комбинаций. Допустим 2 из 15 дают 105 вариантов. Вроде и не большие цифры, но стОит только начать увеличивать цифры, как идет прогрессия. Например 10 из 1000 дают "263409560461970212832400" комбинаций.
С одной стороны - сумасшедшие цифры. С другой - ну так и компьютер не 16 битный 90-х годов.

Собственно вопрос местным программистам - современный домашний комп, как долго будет просчитывать такое количество вариантов?
Я знаю что "домашний комп" понятие растяжимое, но я не знаю какой характеристике ТТХ нужно в данном случае отдать предпочтение - памяти, процессору, жесткому диску, но если узнать хотя бы порядок цифр, или кто поделится хотя бы каким макаром делать прикидки - буду благодарен.
Danila96 вне форума Ответить с цитированием
Старый 13.08.2020, 15:30   #2
Arigato
Высокая репутация
СуперМодератор
 
Аватар для Arigato
 
Регистрация: 27.07.2008
Сообщений: 16,216
По умолчанию

Цитата:
Сообщение от Danila96 Посмотреть сообщение
как долго будет просчитывать такое количество вариантов?
А просто прикинуть сложно? Просто упрощенно. У ЦП тактовая частота в районе нескольких ГГц, даже если распараллелить задачу на несколько ядер, можно условно принять, что за секунду будет рассмотрено миллиард вариантов. А теперь считайте, сколько секунд потребуется для вашего значения:

263 409 560 461 970 (212 832 400) - в скобках это миллиард. То есть остается 263 409 560 461 970 секунд. В году 60 * 60 * 24 * 365 = 31 536 000 секунд. Делите - 8 352 662 лет. Если у вас есть 8 миллионов лет в запасе, то запускайте программу
Arigato вне форума Ответить с цитированием
Старый 13.08.2020, 15:58   #3
kvitaliy
Участник клуба
 
Регистрация: 17.05.2011
Сообщений: 1,660
По умолчанию

Цитата:
Сообщение от Danila96 Посмотреть сообщение
методом перебора найти наименьшую комбинацию в массиве данных.
А что означает "наименьшая комбинация в массиве данных"?
Можно пример из 5 значений массива?

Цитата:
Сообщение от Danila96 Посмотреть сообщение
Например 10 из 1000
Это означает например 10 символьный набор из 1000 возможных?
А где реально используется в компьютере 1000 различных символов?
kvitaliy вне форума Ответить с цитированием
Старый 16.08.2020, 09:06   #4
Danila96
 
Регистрация: 19.01.2014
Сообщений: 6
По умолчанию

Цитата:
Сообщение от Arigato Посмотреть сообщение
А просто прикинуть сложно? Просто упрощенно. У ЦП тактовая частота в районе нескольких ГГц, даже если распараллелить задачу на несколько ядер, можно условно принять, что за секунду будет рассмотрено миллиард вариантов. А теперь считайте, сколько секунд потребуется для вашего значения:

263 409 560 461 970 (212 832 400) - в скобках это миллиард. То есть остается 263 409 560 461 970 секунд. В году 60 * 60 * 24 * 365 = 31 536 000 секунд. Делите - 8 352 662 лет. Если у вас есть 8 миллионов лет в запасе, то запускайте программу
Спасибо за консультацию, я думал что эта цифры будет исчисляться днями - максимум неделями
Danila96 вне форума Ответить с цитированием
Старый 16.08.2020, 09:10   #5
Danila96
 
Регистрация: 19.01.2014
Сообщений: 6
По умолчанию

Цитата:
Сообщение от kvitaliy Посмотреть сообщение
А что означает "наименьшая комбинация в массиве данных"?
Можно пример из 5 значений массива?


Это означает например 10 символьный набор из 1000 возможных?
А где реально используется в компьютере 1000 различных символов?
Это не для использования в ПК, это для использования в реальной жизни.
Что бы не плодить загадок - тотализатор. Бриф системы позволяют снизить затраты. Из того что есть в открытом доступе не совсем оптимальны. Есть более грамотно подобранные системы, которые дешевле на 30% чем в открытом доступе.
Danila96 вне форума Ответить с цитированием
Старый 17.08.2020, 13:35   #6
kvitaliy
Участник клуба
 
Регистрация: 17.05.2011
Сообщений: 1,660
По умолчанию

Цитата:
Сообщение от Danila96 Посмотреть сообщение
тотализатор
Ну тут да, рулят хитрые формулы и верные выигрыши
kvitaliy вне форума Ответить с цитированием
Старый 26.08.2020, 11:55   #7
Danila96
 
Регистрация: 19.01.2014
Сообщений: 6
По умолчанию

Тут еще вопрос возник по данной теме, я правильно понимаю что перебор и распараллеливание это не совместимые вещи?
Danila96 вне форума Ответить с цитированием
Старый 26.08.2020, 12:29   #8
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

перебрать от 00001 до 00999
перебрать от 01000 до 01999
перебрать от 02000 до 02999
...

вполне параллельные переборы, ЕСЛИ...
то что внутри не требует одного и того же ресурса в исключительном(монопольном) доступе ОДНОВРЕМЕННО.
например одновременная запись в один и тот же файл.
программа — запись алгоритма на языке понятном транслятору
evg_m на форуме Ответить с цитированием
Старый 27.08.2020, 07:41   #9
Danila96
 
Регистрация: 19.01.2014
Сообщений: 6
По умолчанию

Цитата:
Сообщение от evg_m Посмотреть сообщение
перебрать от 00001 до 00999
перебрать от 01000 до 01999
перебрать от 02000 до 02999
...

вполне параллельные переборы, ЕСЛИ...
то что внутри не требует одного и того же ресурса в исключительном(монопольном) доступе ОДНОВРЕМЕННО.
например одновременная запись в один и тот же файл.
Спасибо за ответ, по моим прикидкам не получается такой вариант.
Вот пример:
Комбинация из трех переменных в три ряда (надеюсь выразился не слишком криво):
А-В-С
А-В-С
А-В-С
дает нам 27 возможных комбинаций:
В-В-В
В-В-А
В-В-С
В-А-В
В-А-А
В-А-С
В-С-В
В-С-А
В-С-С
А-В-В
А-В-А
А-В-С
А-А-В
А-А-А
А-А-С
А-С-В
А-С-А
А-С-С
С-В-В
С-В-А
С-В-С
С-А-В
С-А-А
С-А-С
С-С-В
С-С-А
С-С-С
Если мы начнем искать минимально возможное количество комбинаций, что бы при любом исходе гарантированно в одном из вариантов цепляло 2 исхода мы получаем такой пакет вариантов.
С-С-С
В-В-В
А-А-В
А-В-А
В-А-А
Как видим, они разбросаны по всему столбцу из 27 вариантов. То есть если этот столбец "распилить" (распараллелить) на три подзадачи по 9 вариантов в каждом, мы получаем что задача не выполнится, так как в "своем" участке программы не найдут оптимальных комбинаций, или найдут, но там уже будет на 5, а 6 или 7 вариантов.

Я поразмышляв пришел что "распилить" можно, но другим путем. Берем основу из 27 вариантов, и начинаем формировать новые варианты. Нулевую строку вырезаем и переносим в конец, строка что шла за ней становится нулевым. Следующим шагом, из нового списка формируем таким же образом еще один такой список.
Таким образом мы формируем к основе еще 26 новых списков.
То есть перебор ускоряется на порядок.
Но я думаю, что есть еще варианты, просто мне из-за своего скудоумия это не очевидно.
Danila96 вне форума Ответить с цитированием
Старый 27.08.2020, 20:50   #10
сфинкс
Форумчанин
 
Аватар для сфинкс
 
Регистрация: 17.06.2012
Сообщений: 953
По умолчанию

Проверим 2 из 15:

= 15 * (15-1) / ( 2 * (2-1) )
= 105

Да автор темы считает там правильно

Визуализация в 3-ем ютюбе "Комбинаторика просто"
в моём сообщении
https://www.programmersforum.ru/show...41#post1806541

Количество перестановок простейшее: факториал

Например переставить 3 книги: 3! = 6 вариантов

123 132 213 231 312 321
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую

Последний раз редактировалось сфинкс; 27.08.2020 в 21:02.
сфинкс вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
слишком много аргументов в вызове функции или как создать много файлов на рабочем столе ON Mikhail Общие вопросы C/C++ 1 07.03.2018 21:02
брут oteccc Работа с сетью в Delphi 3 04.01.2014 12:01
Opera слишком много кушает ресурсов alex(21) Софт 12 13.01.2013 13:42
Требуется написать брут под сайт. ZammI Фриланс 0 25.10.2012 16:23