LINUX.ORG.RU

Сортировка списка множеств по степени пересечения с данной

 , ,


0

1

В общем, есть такая задачка. Есть набор множеств. Нужно для каждого множества построить список других множеств, отсортированный по числу общих элементов с рассматриваемым.

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

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

Если это как-то поможет, то сами множества изначально задаются парами {номер_множества, элемент}. Возможно, есть способ этим воспользоваться.


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

slovazap ★★★★★ ()

А что если сначала построить матрицу вхождения элементов во множества, т.е. например строка = номер множества, столбец = номер элемента. Это займёт O(кол-во множеств * кол-во элементов). Потом для каждой пары складывать единицы (или нули) из этой матрицы. Это опять O(кол-во множеств * кол-во элементов).

anonymous ()
Ответ на: комментарий от anonymous

складывать единицы и нули можно битовыми операциями

anonymous ()

или просто подтолкните в нужную сторону.

Посмотри в сторону (топологической ©) поразрядной сортировки. ©

quickquest ★★★★★ ()

опиши задачу подробнее: дай точный формат входных данных со всеми ограничениями, а то не оч понятно, что вообще надо делать

f1u77y ★★★ ()

Отсортируй элементы в каждом множестве по возрастанию. Отсортированные множества пересекать быстрее.

anonymous ()

Понятно, что можно найти пересечение(число элементов) для каждой пары множеств, потом для каждого множества построить списки и отсортировать.

без попарного сравнения такую «схожесть» не вывести

в целом, если отказаться от полной матрицы, см. https://ru.wikipedia.org/wiki/Задача_поиска_ближайшего_соседа

anonymous ()
Ответ на: комментарий от f1u77y

дай точный формат входных данных

Набор csv-файликов с двумя колонками: категория, номер. Данные в произвольными порядке.

Категорий и номеров в системе по паре десятков миллионов штук. Один номер относится к нескольким категориям, одна категория содержит множество номеров.

Нужно для каждой категории построить список других категорий, отсортированный по числу общих номеров. По убыванию.

forCe ()
Ответ на: комментарий от forCe

для каждой категории построить список других категорий, отсортированный по числу общих номеров

так это только у вывода сложность O(n^2), где n <= 2e7. это же вроде как довольно много. или может я неправильно понял.

Категорий и номеров в системе по паре десятков миллионов штук

различных? или это размер входных данных?

f1u77y ★★★ ()
Ответ на: комментарий от f1u77y

так это только у вывода сложность O(n^2)

Ну там разряженная матрица на выходу получается. Так что пока еще есть надежда не делать квадрат.

различных?

Различных.

forCe ()
Ответ на: комментарий от forCe

Ну там разряженная матрица на выходу получается

а, т.е. надо для каждого выводить только те, с которыми у него хотя бы один общий элемент?

f1u77y ★★★ ()
Последнее исправление: f1u77y (всего исправлений: 1)
Ответ на: комментарий от f1u77y

а, т.е. надо для каждого выводить только те, с которыми у него хотя бы один общий элемент?

Да.

forCe ()

в стандартную библиотеку посмотреть, не?

например, на крестах. загоняешь в отсортированные контейнеры, а потом:

template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result)
{
  while (first1!=last1 && first2!=last2)
  {
    if (*first1<*first2) ++first1;
    else if (*first2<*first1) ++first2;
    else {
      *result = *first1;
      ++result; ++first1; ++first2;
    }
  }
  return result;
}

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.