|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
29.11.2018, 13:25 | #1 |
Старожил
Регистрация: 25.08.2011
Сообщений: 2,841
|
Поиск подстроки
Здравствуйте. Есть вроде как тривиальная задачка но слишком уж много данных.
В общем задача найти комбинацию чисел в огромных списках других комбинаций. Комбинации числовые. Либо не просто найти а посчитать например сколько раз комбинация встречается в списке других комбинаций или в какие комбинации входит полностью. Сейчас все реализовано обычным перебором. И времени это занимает десятки часов. Хочу спросить существуют ли какие нибдь алгоритмы оптимизации подобного поиска? Может как то типы данных надо использовать особые.. деревья или графы... Если кто знает прошу покажите пальцем чего читать? Спасибо.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два. |
29.11.2018, 13:38 | #2 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Даже в вики есть упоминание об куче алгоритмов
https://ru.wikipedia.org/wiki/%D0%9F...BE%D0%BA%D0%B8
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
29.11.2018, 13:56 | #3 | |
Старожил
Регистрация: 25.08.2011
Сообщений: 2,841
|
Цитата:
У меня как такого алфавита нету. Числа входящие в комбинации это 0 и до бесконечности.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два. |
|
29.11.2018, 14:42 | #4 |
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,657
|
Зависит от конкретного способа комбинирования - без этого точнее названий теорий никто не подскажет. Может там вообще регулярные выражения. Так или иначе теория графов может ответить на Ваш вопрос. Можно сократить перебор динамическим программированием и/или методом ветвей и границ. Существуют оптимизации и собственно алгоритма поиска подстроки в тексте. Подобные используются для генетики.
Благими намерениями устлана дорога на programmersforum.ru
Последний раз редактировалось MihalNik; 29.11.2018 в 14:49. |
29.11.2018, 15:08 | #5 |
Лис
Старожил
Регистрация: 18.09.2015
Сообщений: 2,409
|
Для комбинаторных алгоритмов считается лучшим способом радужные таблицы.
Но если вы покажете пример или дадите больше данных можно будет сказать точнее.
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал . |
29.11.2018, 15:13 | #6 | |
Старожил
Регистрация: 25.08.2011
Сообщений: 2,841
|
Цитата:
Ну в качестве примера допустим такое: допустим есть комбинация: 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 критериям - быстро, качественно, недорого. Заказчик выбирает любые два. |
|
29.11.2018, 15:21 | #7 |
Старожил
Регистрация: 16.12.2011
Сообщений: 2,329
|
|
29.11.2018, 20:01 | #8 | |
Лис
Старожил
Регистрация: 18.09.2015
Сообщений: 2,409
|
Цитата:
Если поиск то будет оптимизировать её. Достаточно создать индекс. Заборовидную матрицу из 256 строк. Каждой строке соответствует поисковое число. А столбцы это указатели на строки в которых есть данное число. Заборовидность проявляется в переменной длине строк. Это вам ускорит вашу программу в среднем 16 раз. Если недостаточно, то можно развить идею хранить не 256 строк, а 256*256. Соответствующие 2-м первым числам из поискового запроса. Выбираем по ним строку и по строке используя её элементы в качестве указателей. И далее линейным поиском ищем. При необходимости исходные данные можно отсортировать. Тогда матрица превратиться в массив(вектор) указывающей на границы для линейного поиска. Если данные приходится часто вставлять, то лучше перейти на деревья. Идея как в квадра-деревьях. А поиск будет заключаться в альфа-бета отсечении.
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал . |
|
29.11.2018, 20:40 | #9 |
Старожил
Регистрация: 25.08.2011
Сообщений: 2,841
|
Длина строк может быть разная. Просто в привиденном примере она одинаковая. Про ваш алгоритм не очень врубился что и как строить.
А вот идея с троичным деревом понравилась. Что то такое читал давно. Вставки в комбинации не нужны. Как правило большой список загружается в начале работы и потом происходит работа.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два. |
13.12.2018, 12:36 | #10 |
Старожил
Регистрация: 25.08.2011
Сообщений: 2,841
|
люди добрые помогите идеями кто какими сможет!!
В общем результат такой: Сделал дерево взаимосвязанных элементов. Каждый элемент при построении дерева знает в какой комбинации он находится. Все строится идеально. После сортировки поиск списка просто поразительный. Но беда вылезла в другом. Когда надо проверить определенную комбинацию на предмет пересечения с другими комбинациями получается следующее: Пример: есть набор Код:
из моего дерева я быстро получаю списки: 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 критериям - быстро, качественно, недорого. Заказчик выбирает любые два. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
поиск подстроки в строке С | 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 |