Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.222.205.211] |
|
Сообщ.
#1
,
|
|
|
Здравствуйте!
Есть некая задача: Set<String> set1 = ...; Set<String> set2 = ...; В обоих сетах есть много элементов. Тривиальная задача - найти пересечение двух сетов, но, есть один не тривиальный момент: пересечение может быть даже если элемент первого сета заканчивается на элемент второго сета. Более подробно. Представим что первый и второй сеты содержат URL-ы с wildcard-ами: Цитата Set<String> set1 = ...; - test.ru - my.domain.ru - host.com - address.net Цитата Set<String> set2 = ...; - test.ru - domain.ru Результатом пересечения должны быть элементы первого множества: test.ru my.domain.ru Потому что test.ru - содержится в обоих множествах, и my.domain.ru соответствует wildcard домену *.domain.ru В случае когда множество одно, и в нём нужно найти такие пересечения, я могу использовать сортировку, и вся задача сводится к одному проходу по списку. Но, теперь множества два, оба имеют гигантские размеры, и это начало серьёзно влиять на производительность (я же сделал решение в лоб, двумя циклами). Прошу подсказки, есть ли какие нибудь алгоритмы, которые помогут решить задачу быстрее чем два вложенных цикла? В какую сторону копать? Насколько целесообразно использовать сортировку + реверс, или тут они ни к чему? |
Сообщ.
#2
,
|
|
|
Если элементы выглядят именно так и нетрудно по ходу программы отсекать от элементов первого множества части до очередной точки, то можно загнать второй набор в хэш-таблицу и искать в ней по очереди my.domain.ru, domain.ru, ru.
Тогда получается линейное от количества элементов решение (с множителем КоличествоСимволов*Среднее количество частей). Если количество частей (уровней поддоменов) велико, то может быть выгоднее, как ты и сказал, перевернуть строки, отсортировать один из списков, и искать бинарным поиском. получив NlogN (множитель КоличествоСимволов никуда не денется) |
Сообщ.
#3
,
|
|
|
Цитата MBo @ можно загнать второй набор в хэш-таблицу и искать в ней по очереди my.domain.ru, domain.ru, ru. Просто гениально!! Как я не подумал о таком... Точно, и в разы шустрее будет, с учётом того, что доменов 1 уровня, в моём случае, не существует в принципе! Завтра прогоню тесты)) Огромное спасибо за такое решение)) Буду посматривать в тему, может даже что нибудь ещё появится. |
Сообщ.
#4
,
|
|
|
Цитата MBo @ можно загнать второй набор в хэш-таблицу и искать в ней по очереди my.domain.ru, domain.ru, ru. Придётся считать от каждого испытуемого несколько хэшей разной длины - в зависимости от набора длин элементов второго сета. И вместе с хэшами хранить длины, чтобы знать, с чем сравнивать. Хотя всё одно это будет O(n*m). Реверс плюс O(n*logn)-сортировка плюс билинейный поиск мне кажутся оптимальным вариантом. |
Сообщ.
#5
,
|
|
|
Всё прошло на ура. Теперь поиск занимает по времени меньше секунды. Это потрясающий результат)
Цитата Akina @ Придётся считать от каждого испытуемого несколько хэшей разной длины - в зависимости от набора длин элементов второго сета. И вместе с хэшами хранить длины, чтобы знать, с чем сравнивать. И это, всё равно, вышло в сотни раз быстрее чем вложенные циклы. Длины хранить не нужно, для того чтобы узнать, с чем было сравнение изначально (например, test.ru попался, но, это сгенерированная строка, исходной была my.test.ru) сделал чрез HashMap. Его разные ключи {test.ru, my.test.ru} указывают на одно исходное значение my.test.ru. Весь поиск вхождения сетов свёлся к containsKey, и если ключ есть, извлекаем значение чтобы получить адрес, который попал в оба сета. Ещё раз огромное спасибо MBo) Akina, Вариант с бинарным поиском кажется сложнее, если текущий вариант с картой начнёт забирать всю память, придётся проверять этот... Возможно искать другие способы. |