На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Qraizer, Hsilgos
Страницы: (2) 1 [2]  все  ( Перейти к последнему сообщению )  
> Как сгруппировать элементы
    AVA12, как я понял, Majestio как раз это и сделал. Ну или очень похожее. Но задачу можно решить быстрее. Наверное. Без многократных циклов, без флагов и без возвратов. У меня один цикл... ну как один, два, но каждый со своим фильтром, непересекающимся со вторым и в точности его дополняющий. Сначала цикл пробегает по свойствам под 2-мя и более заголовками, потом ровно под одним заголовком. Так что всё равно каждое свойство получается обработанным однократно. Фактически тут O(N), где N общее количество свойств.
    Меня волнует его корректность. Betelgeuse, я б поостерёгся мой алгоритм брать без досконального тестирования.
      Если я правильно понял задачу, то к ней можно применить алгоритм Union-Find
        Цитата Qraizer @
        Но задачу можно решить быстрее. Наверное. Без многократных циклов

        Хе-хе ... Ну положим, ты тут тоже малёха лукавишь ;) В твоем варианте есть просто спрятанные "под капот" циклы, например в std::distance и keys.find :)

        Цитата MBo @
        Если я правильно понял задачу, то к ней можно применить алгоритм Union-Find

        Вполне себе. Если абстрагироваться от самих "свойств", то на первом шаге вполне можно получить "матрицу отношений", а-ля:
        0 0 1 0 0
        0 0 1 0 0
        1 1 0 0 0
        0 0 0 0 1
        0 0 0 1 0

        И вот из нее нужно получить вектор: (0, 1, 2), (3, 4) - это дезинфицированная Доместосом постановка задачи :lol:
          MBo, пасип за идею! :thanks:

          Тут я уже не стал напрягаться, зарядил эту "подзадачу" реализовать ChatGPT, получилось прикольно:

          ExpandedWrap disabled
            #include <iostream>
            #include <vector>
             
            class UnionFind {
            public:
              UnionFind(int n) {
                parent.resize(n);
                rank.resize(n, 0);
                for (int i = 0; i < n; i++) {
                  parent[i] = i;
                }
              }
             
              int find(int x) {
                if (parent[x] != x) {
                  parent[x] = find(parent[x]);
                }
                return parent[x];
              }
             
              void unite(int x, int y) {
                int rootX = find(x);
                int rootY = find(y);
                if (rootX != rootY) {
                  if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                  } else if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                  } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                  }
                }
              }
             
            private:
              std::vector<int> parent;
              std::vector<int> rank;
            };
             
            std::vector<std::vector<int>> groupElements(const std::vector<std::vector<int>>& S) {
              int n = S.size();
              UnionFind uf(n);
             
              for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                  if (S[i][j] == 1) {
                    uf.unite(i, j);
                  }
                }
              }
             
              std::vector<std::vector<int>> groups(n);
              for (int i = 0; i < n; i++) {
                int root = uf.find(i);
                groups[root].push_back(i);
              }
             
              groups.erase(std::remove_if(groups.begin(), groups.end(), [](const std::vector<int>& group) {
                return group.empty();
              }), groups.end());
             
              return groups;
            }
             
            int main() {
              std::vector<std::vector<int>> S = {
                {0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {1, 1, 0, 0, 0},
                {0, 0, 0, 0, 1},
                {0, 0, 0, 1, 0}
              };
             
              std::vector<std::vector<int>> groups = groupElements(S);
             
              for (const auto& group : groups) {
                for (int element : group) {
                  std::cout << element << " ";
                }
                std::cout << std::endl;
              }
             
              return 0;
            }


          Добавлено
          Цитата Qraizer @
          я б поостерёгся мой алгоритм брать без досконального тестирования

          И это правильно! :lol:

          Вот на таких входных данных:

          ExpandedWrap disabled
            std::map<int, std::set<int>> source = {
                                                    {1, { 1,  3,  4}}, {2, { }}, {3, {1, 4, 5}},
                                                    {4, {11, 12, 14}}, {5, {10, 18, 12}}
                                                  };

          твой алгоритм выдает результат:
          ExpandedWrap disabled
            { A : { 1 3 }:{ 1 3 4 5 } }
            { B : { 4 5 }:{ 10 11 12 14 18 } }

          А у меня на аналогичных:
          ExpandedWrap disabled
            Group [A]: 1 3
               bitset: 1 3 4 5
            Group [B]: 4 5
               bitset: 10 11 12 14 18
            Group [C]: 2
               bitset:

          Хз, может такой тест запрещён :scratch:
            Цитата Majestio @
            Хз, может такой тест запрещён
            Если подходить к вопросу с позиции формализма теории множеств, то пустое множество входит подмножеством в любое множество, а значит его элементы принадлежат любому множеству. Из этого следует, что деление на группы будет тривиальным: просто всегда запихиваем всё в одну группу. Не думаю, что это решение. Если с позиции теории графов, что не очень похоже на исходное ТЗ, но фикъегознает, то я беспонятия.
            Вообще, вопрос о выборе формализма нужно задавать Betelgeuse.

            Добавлено
            Цитата Majestio @
            Ну положим, ты тут тоже малёха лукавишь В твоем варианте есть просто спрятанные "под капот" циклы, например в std::distance и keys.find
            Логично. Тогда O(N*log(N))
              Цитата Qraizer @
              Вообще, вопрос о выборе формализма нужно задавать Betelgeuse.

              Вот тут вроде вопросов нет, читаем:
              Цитата Betelgeuse @
              Условие : если есть повторяющиеся свойства, они должны быть в одной группе.

              Т.t. если есть элемент с пустым набором свойств, он "не повторится" ни с одним другим, даже с таким же как он.
                У пустого заголовка нет свойств. ⊥ → ⊤ ≡ ⊤. Это фундаментальное свойство импликации, благодаря ему из исчисления высказываний следует, например, методика доказательств от противного.

                Добавлено
                Чтобы такого казуса не случилось, следует кванторы всегда ограничивать по ∅. Ну или как можно чаще. Впрочем, неограниченные кванторы вообще не любят из-за конфликтов вокруг аксимы выбора.
                  Цитата Qraizer @
                  У пустого заголовка нет свойств. ⊥ → ⊤ ≡ ⊤. Это фундаментальное свойство импликации, благодаря ему из исчисления высказываний следует, например, методика доказательств от противного.
                  Добавлено Вчера, 23:40
                  Чтобы такого казуса не случилось, следует кванторы всегда ограничивать по ∅. Ну или как можно чаще. Впрочем, неограниченные кванторы вообще не любят из-за конфликтов вокруг аксимы выбора.

                  Не, нафик тут высшую арифметику :lol: В чисто прикладном смысле работаем. И постановщик задачи просто должен ответить на вопросы:

                  1) Могут ли быть элементы без характеристик (ну пустое множество это)
                  2) И если "да", куда их "собирать" или вообще игнорить (твой вариант)

                  А вообще это тема важная. Нет, не именно это пустое множество. А оптимальное начало тестов реализаций, алгоритмов. Да всего, что нужно тестировать - начинаем с "граничных" значений: нуль, ничего, пусто, очень много, очень очень много. Сразу вылезают вопросы. Ну а потом уже "обычные" тесты. Это как "обычный порошок" и "Тайд".

                  Скрытый текст
                  Примерно 1996 год. Мой неспешный переход из "теоретического программинга" (до этого работал в НИИ Технической кибернетики АН БССР, с одной персоналкой на всю лабу) - в практический (пришел в чисто девелоперскую компанию, с персональной персоналкой). Тогда еще прогал на Пасквиле. Ситуация. Парень, это тот, который когда-то меня убивал своим кодом. На Пасквиле уже не помню, напишу на Сях:

                  ExpandedWrap disabled
                    switch (idx) {
                      case 65: Res = 'A'; break;
                      case 66: Res = 'B'; break;
                      case 67: Res = 'C'; break;
                      ...
                      // и так до Z, сука!!!
                    }

                  ... Говорит (не дословно) "я джва года две недели вылизывал свой модуль, написал качественную документацию. Кто сможет на тестах завалить - выставляю ящик пиваса. На тест полчаса, иначе жду ящик пиваса от тестировщика. Ну я, была-не-была, подрядился. Запустил его прогу, она требует логин и пароль. Я спросил где документация. Он показал. Я открыл, не читая скопировал все в буфер обмена, переключился на диалог "логин-пароль", вставил вместо логина и пароля содержимое буфера обмена (ну собственно, его документацию), после нажатия кнопки [Login] прога легла.... А он, бедолага, тестил свои алгоритмы... Посоны были рады внезапному пивасу, и ... ржачке :rolleyes:
                  Сообщение отредактировано: Qraizer -
                    Цитата
                    Вообще, вопрос о выборе формализма нужно задавать Betelgeuse

                    у меня задача вполне прикладная. заголовков не более 10, свойств в каждом заголовке ровно по 3.
                    Так что пустые множества рассматривать не нужно ))

                    Цитата
                    И постановщик задачи просто должен ответить на вопросы:

                    1) нет
                    2) значит неправильные входные данные, эта ситуация будет обработана до вызова функции группировки с выводом сообщения
                    Сообщение отредактировано: Betelgeuse -
                      Не даёт покоя мне это задача. Всё ж решил к ней вернуться, и не зря. И ведь было стойкое ощущение... профильник бы сразу ткнул носом. В общем, поняв, что функциями решение не выразить из-за многозначности сюръективных отношений свойств к заголовкам, начал строить решение на суръекциях, отсюда ж и всплыли мультимножества-то. Попробовав избавиться от избыточных групп, я писал реализацию постепенно шаг за шагом и удивился, получив в качестве, как мне казалось, промежуточного результата уже готовый ожидаемый. И остановился, совершенно забыв что любые многозначные отношения в природе своей индуктивны. Но у меня-то в коде нет индукции! Там только первый шаг, и мне просто "повезло" в том, что исходные данные не требовали большего их количества. Почему я этого не понял сразу :blush:, спросите лучше моё отношение к арифметике несчётных ординалов :-? , на это я хоть что-то смогу ответить.
                      Занявшись серьёзным тестированием, тут же получил баг: достаточно довести отношения свойств с заголовками до второй глубины вложенности и бац! Минимальный фэйл-сценарий:
                      {1} : {10, 11}
                      {2} : {12, 13}
                      {3} : {11, 12} <- объединение {1} и {2} в Группу 1
                      {4} : {20, 21}
                      {5} : {22, 23}
                      {6} : {20, 22} <- объединение {3} и {4} в Группу 2
                      {7} : {12, 20} <- объединение Группы 1 с Группой 2
                      (Вроде, правильно воссоздал, запамятовал уже. Не всегда такая косвенность проходит незамеченной.)
                      Последний заголовок {7} не соотносится с {1}, {2}, {4} и {5} явно, но явно соотносится с {3} и {6}. Эта косвенная связь не будет замечена моим кодом, т.к. требует минимум двух индукционных шагов. В общем, исходно нефик было пытаться избавлять от избыточных групп. Это можно было бы сделать, только если б изначально знать глубину рекурсии, и начинать следовало бы именно с такого количества совпадений, а не ровно двух.
                      В общем и целом, от дополнительного уровня косвенности никуда не деться. Держите:
                      ExpandedWrap disabled
                        #include <map>
                        #include <set>
                        #include <iostream>
                        #include <random>
                        #include <string>
                        #include <chrono>
                         
                        // исходный контейнер
                        // индексируется заголовком, содержит множества свойств для каждого
                        std::map<int, std::set<int>> source = {
                        /*                                        {1, { 1,  3,  4}}, {2, { 5,  6,  8}}, {3, {1, 4, 5}},
                                                                {4, {11, 12, 14}}, {5, {10, 18, 12}}
                        */                                      };
                        /*                                      {
                                                               {1, { 1,  3}}, {2, { 5,  6}}, {3, {2, 4}}, {9, {0}},
                                                               {4, {11, 12, 14}}, {5, {10, 18, 12}}, {8, {6, 2}}
                                                              };*/
                         
                        // контейнер групп
                        // индексируется ключём группы, для каждого содержит два множества:
                        // заголовки как first и свойства как second в паре
                        std::map<int, std::pair<std::set<int>, std::set<int>>> groups;
                         
                        void printSource()
                        {
                          for (const auto& i : source)
                          {
                            std::cout << "{ " << i.first << " : { ";
                            for (const auto& j : i.second)
                              std::cout << j << ' ';
                            std::cout << "} }\n";
                          }
                          std::cout << std::endl;
                        }
                         
                        void printGroups()
                        {
                          for (const auto& i : groups)
                          {
                            std::cout << "{ Группа " << i.first << " : { ";
                            for (const auto& j : i.second.first)
                              std::cout << j << ' ';
                            std::cout << "}:{ ";
                            for (const auto& j : i.second.second)
                              std::cout << j << ' ';
                            std::cout << "} }\n";
                          }
                          std::cout << std::endl;
                        }
                         
                        void createSource()
                        {
                          std::mt19937                    gen;
                          std::uniform_int_distribution<> numHeads(1, 10000);
                          std::uniform_int_distribution<> numbers (0, 250000000);
                         
                          // смените на false для по-настоящему случайных входных данных
                          if constexpr (true)
                            gen.seed(0);
                          else
                            gen.seed(std::random_device()());
                         
                          source.clear();
                          for (int i = 0; i < 1000; ++i)
                          {
                            decltype(source)::mapped_type set;
                            int                           n = numHeads(gen);
                         
                            for (int j = 0; j < n; ++j)
                              set.insert(numbers(gen));
                            source.insert({ i, set });
                          }
                        }
                         
                        namespace chrono = std::chrono;
                         
                        int main()
                        {
                          auto            start = std::chrono::steady_clock::now();
                          decltype(start) stop;
                         
                          createSource();
                          stop = std::chrono::steady_clock::now();
                          printSource();
                          std::cout << "Creating src: "
                                    << chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1000.f
                                    << std::endl;
                         
                          std::multimap<int, int>           temp;       // контейнер обратных связей свойств => заголовки
                          std::map     <int, int>           keys;       // заголовки к ключам групп
                          std::map     <int, std::set<int>> names;      // группы к заголовкам
                         
                          start = std::chrono::steady_clock::now();
                          // обращаем (заголовки => свойства) в (свойства => заголовки)
                          // возможны связи многих к одному
                          for (const auto& i : source)
                            for (const auto& j : i.second)
                              temp.insert({j, i.first});
                         
                          int groupName= 1;                     // будущий номер группы
                          int group    = 0;                     // первый ключ группы
                         
                          // подбор ключей на основе поиска по связям
                          for (auto it = temp.begin(); it != temp.end(); )      // для всех диапазонов свойств
                          {
                            auto res = temp.equal_range(it->first);             // диапазон заголовков для текущего свойства
                            int  val = -1;                                      // признак не найденного ключа
                         
                            // по всему диапазону заголовков для текущего свойства
                            for (auto bound = res.first; bound != res.second; ++bound)
                            {
                              auto key = keys.find(bound->second);              // ищем ключ для него
                         
                              if (key == keys.end()) continue;                  // если ещё не заводили, к следующему
                              if (val == -1)                                    // если уже завели,
                                val = key->second;                              // то ключ найден
                              else                                              // иначе он был найден ранее
                              {
                                if (val != key->second)                         // и если он не уникален,
                                {                                               // то ключи других заголовков этой группы
                                  auto oldKey = std::move(names[key->second]);  // нуждаются в коррекции
                         
                                  // oldKey всегда будет найден, т.к. names модифицируется val вместе с keys
                                  for (auto group : oldKey)                     // скорректировать ключи всех заголовов
                                    keys[group] = val;                          // этой (старой) группы
                                  names[val].merge(oldKey);                     // старые ключи удалять нельзя, т.к. на них
                                }                                               // всё ещё возможно что-то временно
                              }                                                 // ссылается, т.ч. пустые группы возможны
                            }
                            if (val == -1)              // если ключ не был найден
                              val = group++;            // завести новый
                            // распространить (возможно, новый вместо старого) ключ по всему диапазону заголовков
                            for (auto bound = res.first; bound != res.second; ++bound)
                            {
                              keys[bound->second] = val;                        // keys и names модифицируются
                              names[val].insert(bound->second);                 // совместно на основе того же val
                            }
                            it = res.second;            // прыгнуть сразу к следующему диапазону свойств
                          }
                          stop = std::chrono::steady_clock::now();
                          std::cout << "Grouping: "
                                    << chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1000.f
                                    << std::endl;
                         
                          start = std::chrono::steady_clock::now();
                          // строим контейнер групп
                          for (const auto& i : names)
                          {
                            if (i.second.empty()) continue;                             // игнорирумем пустые группы
                         
                            auto &it = groups[groupName++];                             // очередная непустая группа
                         
                            it.first.insert(i.second.begin(), i.second.end());          // множество заголовков для неё
                            for (auto set : i.second)                                   // множество свойств для этих заголовков
                              it.second.insert(source[set].begin(), source[set].end());
                          }
                          stop = std::chrono::steady_clock::now();
                          std::cout << "Creating dest: "
                                    << chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1000.f
                                    << std::endl;
                         
                          printGroups();
                        }
                      Это полный текст, вместе с тестом. Тестится 1000 заголовков с количеством свойств от 1 до 10000. Значения свойств от 0 до 250000000. Всё случайно. В коде база рандома всегда одинакова с целью детерминированности сравнительных результатов, но её легко отключить. (Там в конце ещё был код, чекающий пересечения всех групп попарно и выводящий их, если таковые найдутся, но нынче они все пустые, как и должно быть, так что я его удалил.) Должно (Win10Pro, VS2022) получиться 6 групп.
                      Основные разницы от исходной реализации:
                      • Теперь нет нужды сортировать свойства по количеству вхождений в заголовки. Изначально было непродуктивное решение, т.к. не заменяло рекурсию. Возможно немного оптимизировало процесс, но не более. В общем, лямбды больше нет за ненадобностью.
                      • Появился новый контейнер names, который хранит сюръективные отношения групп к заголовкам. Его назначение в быстром поиске заголовков, чьи свойства нужно перенести из одной группы в другую.
                      • Названия групп решил переделать из букв в числа, т.к. диапазона char банально не хватает на таких объёмах данных. Соответственно поменялись и типы данных в связях.
                      • Теперь при нахождении ключа для очередного заголовка, поиск по свойству не прекращается break, и в случае, если будет найден ещё один заголовок с этом же свойством, и при этом ссылающийся на другую группу, то это признак того, что эти группы нужно объединить, что и выполняется. Это основное изменение, реализующее индукцию.
                      Я по-прежнему не исключаю багов в реализации, но теперь я по крайней мере спокоен по поводу корректности алгоритма. Как минимум мой вывод совпадает с выводом кода Majestio (с точностью до порядка нумерации групп, т.к. я удаляю старые группы, а его код не заводит новых), так что если у него всё верно, то и у меня тоже должно.

                      Добавлено
                      P.S. Ну и особняком решил поднять вопрос производительности.
                      ExpandedWrap disabled
                        Creating src: 2.025
                        Grouping: 8.377
                        Creating dest: 5.786
                         
                        ...
                         
                        Given time = 780.224
                      Это секунды. Верхние три строчки мои. Нижняя – это лобовое решение Majestio, похожее в терминах графов было предложено AVA12, но тут я не уверен. Да, сложность у меня подросла и теперь что-то вроде O(N*log(N)*log(KM)), где N общее количество свойств во всех множествах за вычетом дубликатов, M количество заголовков, а К количество дубликатов свойств. (Это если я правильно оценил.) Но даже так супротив него полуквадратичная сложность не конкурент однозначно.

                      P.P.S. Ещё я тестил 10000 заголовков из 1000 свойств или меньше. Получилось 516 групп. И время:
                      ExpandedWrap disabled
                        Creating src: 1.157
                        Grouping: 12.877
                        Creating dest: 6.462
                         
                        ...
                         
                        Given time = 986922.066
                      Да-да, я набрался терпения и ждал 11 дней. Нужно ж было убедиться в совпадении результатов двух алгоритмов. Интересно, много ли задач из графов можно переделать в множества и применить методики оптимизации на вполне упорядоченных множествах?..
                      Сообщение отредактировано: Qraizer -
                        Цитата Qraizer @
                        Интересно, много ли задач из графов можно переделать в множества
                        Очень многие. Те, что не получается переделать, обычно в терминах теории множеств не получается даже описать. Но, как правило, такая переделка мало что даёт.
                          Хм... Чтобы что-то нельзя было бы представить в формализме ТМ... такого не бывает.
                            Цитата amk @
                            Те, что не получается переделать, обычно в терминах теории множеств не получается даже описать.

                            Не понятно, но очень интересно! :lol: А можно пример по этому утверждению?
                            0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                            0 пользователей:


                            Рейтинг@Mail.ru
                            [ Script execution time: 0,0531 ]   [ 18 queries used ]   [ Generated: 4.03.24, 21:32 GMT ]