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

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

Вернуться   Форум программистов > IT форум > Общие вопросы по программированию, компьютерный форум
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 29.11.2018, 13:25   #1
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию Поиск подстроки

Здравствуйте. Есть вроде как тривиальная задачка но слишком уж много данных.

В общем задача найти комбинацию чисел в огромных списках других комбинаций. Комбинации числовые.
Либо не просто найти а посчитать например сколько раз комбинация встречается в списке других комбинаций или в какие комбинации входит полностью.

Сейчас все реализовано обычным перебором. И времени это занимает десятки часов. Хочу спросить существуют ли какие нибдь алгоритмы оптимизации подобного поиска? Может как то типы данных надо использовать особые.. деревья или графы... Если кто знает прошу покажите пальцем чего читать?
Спасибо.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.
WorldMaster вне форума Ответить с цитированием
Старый 29.11.2018, 13:38   #2
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Даже в вики есть упоминание об куче алгоритмов
https://ru.wikipedia.org/wiki/%D0%9F...BE%D0%BA%D0%B8
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 29.11.2018, 13:56   #3
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Даже в вики есть упоминание об куче алгоритмов
https://ru.wikipedia.org/wiki/%D0%9F...BE%D0%BA%D0%B8
Да уж прям куча. ))) Ну мало ли что еще есть малоизвестное.
У меня как такого алфавита нету. Числа входящие в комбинации это 0 и до бесконечности.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.
WorldMaster вне форума Ответить с цитированием
Старый 29.11.2018, 14:42   #4
MihalNik
МегаМодератор
СуперМодератор
 
Регистрация: 27.11.2012
Сообщений: 5,723
По умолчанию

Зависит от конкретного способа комбинирования - без этого точнее названий теорий никто не подскажет. Может там вообще регулярные выражения. Так или иначе теория графов может ответить на Ваш вопрос. Можно сократить перебор динамическим программированием и/или методом ветвей и границ. Существуют оптимизации и собственно алгоритма поиска подстроки в тексте. Подобные используются для генетики.
Благими намерениями устлана дорога на programmersforum.ru

Последний раз редактировалось MihalNik; 29.11.2018 в 14:49.
MihalNik вне форума Ответить с цитированием
Старый 29.11.2018, 15:08   #5
Pavia
Лис
Старожил
 
Аватар для Pavia
 
Регистрация: 18.09.2015
Сообщений: 2,409
По умолчанию

Для комбинаторных алгоритмов считается лучшим способом радужные таблицы.
Но если вы покажете пример или дадите больше данных можно будет сказать точнее.
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал .
Pavia вне форума Ответить с цитированием
Старый 29.11.2018, 15:13   #6
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

Цитата:
Сообщение от Pavia Посмотреть сообщение
Для комбинаторных алгоритмов считается лучшим способом радужные таблицы.
Но если вы покажете пример или дадите больше данных можно будет сказать точнее.

Ну в качестве примера допустим такое:

допустим есть комбинация:
2,5

и есть огромный список вида:
2,7,11,15,19,25,27
3,6,14,17,18,25,31
1,2,11,15,23,26,33
2,8,11,15,21,30,37
3,8,22,26,27,31,34
2,3,10,20,27,33,36
2,5,10,18,27,29,37
6,9,28,29,35,36,39
7,8,20,22,24,26,39
2,6,17,21,24,27,38
5,7,12,18,21,24,25
....

Надо посчитать количество комбинаций которые полностью содержат 2,5.

Про радужные таблицы почитал но непонятно как их в данном случае применять.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.
WorldMaster вне форума Ответить с цитированием
Старый 29.11.2018, 15:21   #7
_Bers
Старожил
 
Регистрация: 16.12.2011
Сообщений: 2,329
По умолчанию

троичное дерево.

https://habr.com/post/111874/
_Bers вне форума Ответить с цитированием
Старый 29.11.2018, 20:01   #8
Pavia
Лис
Старожил
 
Аватар для Pavia
 
Регистрация: 18.09.2015
Сообщений: 2,409
По умолчанию

Цитата:
Сообщение от WorldMaster Посмотреть сообщение
2,7,11,15,19,25,27
3,6,14,17,18,25,31
1,2,11,15,23,26,33
2,8,11,15,21,30,37
3,8,22,26,27,31,34
2,3,10,20,27,33,36
2,5,10,18,27,29,37
6,9,28,29,35,36,39
7,8,20,22,24,26,39
2,6,17,21,24,27,38
5,7,12,18,21,24,25
Какая операция происходит чаще? Вставка удаление или поиск?
Если поиск то будет оптимизировать её.
Достаточно создать индекс.
Заборовидную матрицу из 256 строк.
Каждой строке соответствует поисковое число.
А столбцы это указатели на строки в которых есть данное число.
Заборовидность проявляется в переменной длине строк.

Это вам ускорит вашу программу в среднем 16 раз.
Если недостаточно, то можно развить идею хранить не 256 строк, а 256*256. Соответствующие 2-м первым числам из поискового запроса.

Выбираем по ним строку и по строке используя её элементы в качестве указателей.
И далее линейным поиском ищем.

При необходимости исходные данные можно отсортировать. Тогда матрица превратиться в массив(вектор) указывающей на границы для линейного поиска.

Если данные приходится часто вставлять, то лучше перейти на деревья. Идея как в квадра-деревьях. А поиск будет заключаться в альфа-бета отсечении.
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал .
Pavia вне форума Ответить с цитированием
Старый 29.11.2018, 20:40   #9
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

Длина строк может быть разная. Просто в привиденном примере она одинаковая. Про ваш алгоритм не очень врубился что и как строить.
А вот идея с троичным деревом понравилась. Что то такое читал давно.
Вставки в комбинации не нужны. Как правило большой список загружается в начале работы и потом происходит работа.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.
WorldMaster вне форума Ответить с цитированием
Старый 13.12.2018, 12:36   #10
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

люди добрые помогите идеями кто какими сможет!!

В общем результат такой:
Сделал дерево взаимосвязанных элементов. Каждый элемент при построении дерева знает в какой комбинации он находится. Все строится идеально. После сортировки поиск списка просто поразительный.

Но беда вылезла в другом. Когда надо проверить определенную комбинацию на предмет пересечения с другими комбинациями получается следующее:

Пример:

есть набор
Код:
4,6,8,10,13,23,24,33,34
16,18,20,24,26,35,36
13,14,15,17,24,33,34,19,23
14,16,18,20,23,24,33,34
23,24,25,27,29,33,34
1,3,5,7,9,10,19,20,29,30,39,40
2,4,6,8,17,18,27,28,37,38
11,13,15,16,25,26,35,36
12,14,16,25,26,35,36
2,4,6,8,10,19,20,29,30,39,40
11,13,15,17,19,20,29,30,39,40
12,14,16,18,20,29,30,39,40
21,23,25,27,29,30,39,40
22,24,26,28,30,39,40
Мне надо посчитать в скольких комбинациях подгруппа 11,15,19,20 содержится целиком

из моего дерева я быстро получаю списки:
11 - №7,10
15 - №2,7,10
19 - №5,6,10
20 - №1,3,5,9,10,11

Дальше нужно вроде как найти пересечения всех этих списков. Но это очень и очень долго. Когда списки наборов для состоят из 1000 и более строк или когда комбинация для проверки более длинная время затрачиваемое на поиск пересечения перекрывает время которое затрачивается на тупой перебор.

Может быть я чего то не уловил?? Есть идеи как сделать лучше и быстрее??
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.
WorldMaster вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
поиск подстроки в строке С pepsik66 Помощь студентам 10 12.11.2012 19:25
поиск подстроки в строке Aina Utebekova Помощь студентам 27 11.10.2012 04:24
Поиск подстроки int 20h Win Api 2 09.08.2010 20:37