![>](style_images/1/nav_m.gif)
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.224.66.18] |
![]() |
|
Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
![]() |
Сообщ.
#16
,
|
|
AVA12, как я понял, Majestio как раз это и сделал. Ну или очень похожее. Но задачу можно решить быстрее. Наверное. Без многократных циклов, без флагов и без возвратов. У меня один цикл... ну как один, два, но каждый со своим фильтром, непересекающимся со вторым и в точности его дополняющий. Сначала цикл пробегает по свойствам под 2-мя и более заголовками, потом ровно под одним заголовком. Так что всё равно каждое свойство получается обработанным однократно. Фактически тут O(N), где N общее количество свойств.
Меня волнует его корректность. Betelgeuse, я б поостерёгся мой алгоритм брать без досконального тестирования. |
Сообщ.
#17
,
|
|
|
Если я правильно понял задачу, то к ней можно применить алгоритм Union-Find
|
Сообщ.
#18
,
|
|
|
Цитата Qraizer @ Но задачу можно решить быстрее. Наверное. Без многократных циклов Хе-хе ... Ну положим, ты тут тоже малёха лукавишь ![]() ![]() Цитата 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) - это дезинфицированная Доместосом постановка задачи ![]() |
Сообщ.
#19
,
|
|
|
MBo, пасип за идею!
![]() Тут я уже не стал напрягаться, зарядил эту "подзадачу" реализовать ChatGPT, получилось прикольно: ![]() ![]() #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 @ я б поостерёгся мой алгоритм брать без досконального тестирования И это правильно! ![]() Вот на таких входных данных: ![]() ![]() std::map<int, std::set<int>> source = { {1, { 1, 3, 4}}, {2, { }}, {3, {1, 4, 5}}, {4, {11, 12, 14}}, {5, {10, 18, 12}} }; твой алгоритм выдает результат: ![]() ![]() { A : { 1 3 }:{ 1 3 4 5 } } { B : { 4 5 }:{ 10 11 12 14 18 } } А у меня на аналогичных: ![]() ![]() Group [A]: 1 3 bitset: 1 3 4 5 Group [B]: 4 5 bitset: 10 11 12 14 18 Group [C]: 2 bitset: Хз, может такой тест запрещён ![]() |
![]() |
Сообщ.
#20
,
|
|
Цитата Majestio @ Если подходить к вопросу с позиции формализма теории множеств, то пустое множество входит подмножеством в любое множество, а значит его элементы принадлежат любому множеству. Из этого следует, что деление на группы будет тривиальным: просто всегда запихиваем всё в одну группу. Не думаю, что это решение. Если с позиции теории графов, что не очень похоже на исходное ТЗ, но фикъегознает, то я беспонятия.Хз, может такой тест запрещён Вообще, вопрос о выборе формализма нужно задавать Betelgeuse. Добавлено Цитата Majestio @ Логично. Тогда O(N*log(N)) Ну положим, ты тут тоже малёха лукавишь В твоем варианте есть просто спрятанные "под капот" циклы, например в std::distance и keys.find |
Сообщ.
#21
,
|
|
|
Цитата Qraizer @ Вообще, вопрос о выборе формализма нужно задавать Betelgeuse. Вот тут вроде вопросов нет, читаем: Т.t. если есть элемент с пустым набором свойств, он "не повторится" ни с одним другим, даже с таким же как он. |
![]() |
Сообщ.
#22
,
|
|
У пустого заголовка нет свойств. ⊥ → ⊤ ≡ ⊤. Это фундаментальное свойство импликации, благодаря ему из исчисления высказываний следует, например, методика доказательств от противного.
Добавлено Чтобы такого казуса не случилось, следует кванторы всегда ограничивать по ∅. Ну или как можно чаще. Впрочем, неограниченные кванторы вообще не любят из-за конфликтов вокруг аксимы выбора. |
Сообщ.
#23
,
|
|
|
Цитата Qraizer @ У пустого заголовка нет свойств. ⊥ → ⊤ ≡ ⊤. Это фундаментальное свойство импликации, благодаря ему из исчисления высказываний следует, например, методика доказательств от противного. Добавлено Вчера, 23:40 Чтобы такого казуса не случилось, следует кванторы всегда ограничивать по ∅. Ну или как можно чаще. Впрочем, неограниченные кванторы вообще не любят из-за конфликтов вокруг аксимы выбора. Не, нафик тут высшую арифметику ![]() 1) Могут ли быть элементы без характеристик (ну пустое множество это) 2) И если "да", куда их "собирать" или вообще игнорить (твой вариант) А вообще это тема важная. Нет, не именно это пустое множество. А оптимальное начало тестов реализаций, алгоритмов. Да всего, что нужно тестировать - начинаем с "граничных" значений: нуль, ничего, пусто, очень много, очень очень много. Сразу вылезают вопросы. Ну а потом уже "обычные" тесты. Это как "обычный порошок" и "Тайд". Скрытый текст Примерно 1996 год. Мой неспешный переход из "теоретического программинга" (до этого работал в НИИ Технической кибернетики АН БССР, с одной персоналкой на всю лабу) - в практический (пришел в чисто девелоперскую компанию, с персональной персоналкой). Тогда еще прогал на Пасквиле. Ситуация. Парень, это тот, который когда-то меня убивал своим кодом. На Пасквиле уже не помню, напишу на Сях: ![]() ![]() switch (idx) { case 65: Res = 'A'; break; case 66: Res = 'B'; break; case 67: Res = 'C'; break; ... // и так до Z, сука!!! } ... Говорит (не дословно) "я ![]() |
Сообщ.
#24
,
|
|
|
Цитата Вообще, вопрос о выборе формализма нужно задавать Betelgeuse у меня задача вполне прикладная. заголовков не более 10, свойств в каждом заголовке ровно по 3. Так что пустые множества рассматривать не нужно )) Цитата И постановщик задачи просто должен ответить на вопросы: 1) нет 2) значит неправильные входные данные, эта ситуация будет обработана до вызова функции группировки с выводом сообщения |
![]() |
Сообщ.
#25
,
|
|
Не даёт покоя мне это задача. Всё ж решил к ней вернуться, и не зря. И ведь было стойкое ощущение... профильник бы сразу ткнул носом. В общем, поняв, что функциями решение не выразить из-за многозначности сюръективных отношений свойств к заголовкам, начал строить решение на суръекциях, отсюда ж и всплыли мультимножества-то. Попробовав избавиться от избыточных групп, я писал реализацию постепенно шаг за шагом и удивился, получив в качестве, как мне казалось, промежуточного результата уже готовый ожидаемый. И остановился, совершенно забыв что любые многозначные отношения в природе своей индуктивны. Но у меня-то в коде нет индукции! Там только первый шаг, и мне просто "повезло" в том, что исходные данные не требовали большего их количества. Почему я этого не понял сразу
![]() ![]() Занявшись серьёзным тестированием, тут же получил баг: достаточно довести отношения свойств с заголовками до второй глубины вложенности и бац! Минимальный фэйл-сценарий: {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}. Эта косвенная связь не будет замечена моим кодом, т.к. требует минимум двух индукционных шагов. В общем, исходно нефик было пытаться избавлять от избыточных групп. Это можно было бы сделать, только если б изначально знать глубину рекурсии, и начинать следовало бы именно с такого количества совпадений, а не ровно двух. В общем и целом, от дополнительного уровня косвенности никуда не деться. Держите: ![]() ![]() #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(); } Основные разницы от исходной реализации: Я по-прежнему не исключаю багов в реализации, но теперь я по крайней мере спокоен по поводу корректности алгоритма. Как минимум мой вывод совпадает с выводом кода Majestio (с точностью до порядка нумерации групп, т.к. я удаляю старые группы, а его код не заводит новых), так что если у него всё верно, то и у меня тоже должно. Добавлено P.S. Ну и особняком решил поднять вопрос производительности. ![]() ![]() Creating src: 2.025 Grouping: 8.377 Creating dest: 5.786 ... Given time = 780.224 P.P.S. Ещё я тестил 10000 заголовков из 1000 свойств или меньше. Получилось 516 групп. И время: ![]() ![]() Creating src: 1.157 Grouping: 12.877 Creating dest: 6.462 ... Given time = 986922.066 |
Сообщ.
#26
,
|
|
|
Цитата Qraizer @ Очень многие. Те, что не получается переделать, обычно в терминах теории множеств не получается даже описать. Но, как правило, такая переделка мало что даёт. Интересно, много ли задач из графов можно переделать в множества |
![]() |
Сообщ.
#27
,
|
|
Хм... Чтобы что-то нельзя было бы представить в формализме ТМ... такого не бывает.
|
Сообщ.
#28
,
|
|
|
Цитата amk @ Те, что не получается переделать, обычно в терминах теории множеств не получается даже описать. Не понятно, но очень интересно! ![]() |