На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Пересечение двух Set , Оптимальный алгоритм
    Здравствуйте!

    Есть некая задача:

    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

    В случае когда множество одно, и в нём нужно найти такие пересечения, я могу использовать сортировку, и вся задача сводится к одному проходу по списку.

    Но, теперь множества два, оба имеют гигантские размеры, и это начало серьёзно влиять на производительность (я же сделал решение в лоб, двумя циклами).
    Прошу подсказки, есть ли какие нибудь алгоритмы, которые помогут решить задачу быстрее чем два вложенных цикла? В какую сторону копать? Насколько целесообразно использовать сортировку + реверс, или тут они ни к чему?
      Если элементы выглядят именно так и нетрудно по ходу программы отсекать от элементов первого множества части до очередной точки, то можно загнать второй набор в хэш-таблицу и искать в ней по очереди my.domain.ru, domain.ru, ru.
      Тогда получается линейное от количества элементов решение (с множителем КоличествоСимволов*Среднее количество частей).

      Если количество частей (уровней поддоменов) велико, то может быть выгоднее, как ты и сказал, перевернуть строки, отсортировать один из списков, и искать бинарным поиском. получив NlogN (множитель КоличествоСимволов никуда не денется)
        Цитата MBo @
        можно загнать второй набор в хэш-таблицу и искать в ней по очереди my.domain.ru, domain.ru, ru.

        Просто гениально!! Как я не подумал о таком... Точно, и в разы шустрее будет, с учётом того, что доменов 1 уровня, в моём случае, не существует в принципе! Завтра прогоню тесты)) Огромное спасибо за такое решение))

        Буду посматривать в тему, может даже что нибудь ещё появится.
          Цитата MBo @
          можно загнать второй набор в хэш-таблицу и искать в ней по очереди my.domain.ru, domain.ru, ru.

          Придётся считать от каждого испытуемого несколько хэшей разной длины - в зависимости от набора длин элементов второго сета. И вместе с хэшами хранить длины, чтобы знать, с чем сравнивать.

          Хотя всё одно это будет O(n*m). Реверс плюс O(n*logn)-сортировка плюс билинейный поиск мне кажутся оптимальным вариантом.
          Сообщение отредактировано: Akina -
            Всё прошло на ура. Теперь поиск занимает по времени меньше секунды. Это потрясающий результат)

            Цитата Akina @
            Придётся считать от каждого испытуемого несколько хэшей разной длины - в зависимости от набора длин элементов второго сета. И вместе с хэшами хранить длины, чтобы знать, с чем сравнивать.

            И это, всё равно, вышло в сотни раз быстрее чем вложенные циклы. Длины хранить не нужно, для того чтобы узнать, с чем было сравнение изначально (например, test.ru попался, но, это сгенерированная строка, исходной была my.test.ru) сделал чрез HashMap. Его разные ключи {test.ru, my.test.ru} указывают на одно исходное значение my.test.ru. Весь поиск вхождения сетов свёлся к containsKey, и если ключ есть, извлекаем значение чтобы получить адрес, который попал в оба сета.

            Ещё раз огромное спасибо MBo)

            Akina, Вариант с бинарным поиском кажется сложнее, если текущий вариант с картой начнёт забирать всю память, придётся проверять этот... Возможно искать другие способы.
            0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
            0 пользователей:


            Рейтинг@Mail.ru
            [ Script execution time: 0,0232 ]   [ 15 queries used ]   [ Generated: 28.03.24, 08:22 GMT ]