Попытка группировать ценности?

Мне удалось O (n log n).

Вот (несколько интенсивная) реализация на C ++:

 #include <boost/pending/disjoint_sets.hpp> #include <boost/property_map/property_map.hpp> #include <map> #include <set> #include <iostream> typedef std::map<int, int> rank_t; typedef std::map<int, int> parent_t; typedef boost::associative_property_map< rank_t > rank_pmap_t; typedef boost::associative_property_map< parent_t > parent_pmap_t; typedef boost::disjoint_sets< rank_pmap_t, parent_pmap_t > group_sets_t; typedef std::set<int> key_set; typedef std::map<int, std::set<int> > output; 

С некоторыми typedefs в сторону, вот реальное мясо. Я использую boost :: disjoint_sets , который, как оказалось, является исключительно хорошим представлением проблемы. Эта первая функция проверяет, был ли ранее обнаружен какой-либо из указанных ключей, и при необходимости добавляет их в коллекции. важной частью является действительно union_set(a, b) который связывает два множества вместе. Если один или другой набор уже находится в коллекции groups , они также связаны.

 void add_data(int a, int b, group_sets_t & groups, key_set & keys) { if (keys.count(a) < 1) groups.make_set(a); if (keys.count(b) < 1) groups.make_set(b); groups.union_set(a, b); keys.insert(a); keys.insert(b); } 

Это не слишком захватывающе, он просто выполняет все ключи, которые мы видели, и получает представительский ключ для этого ключа, а затем добавляет пару (представитель, ключ) к карте. Как только это будет сделано, распечатайте карту.

 void build_output(group_sets_t & groups, key_set & keys) { output out; for (key_set::iterator i(keys.begin()); i != keys.end(); i++) out[groups.find_set(*i)].insert(*i); for (output::iterator i(out.begin()); i != out.end(); i++) { std::cout << i->first << ": "; for (output::mapped_type::iterator j(i->second.begin()); j != i->second.end(); j++) std::cout << *j << " "; std::cout << std::endl; } } int main() { rank_t rank; parent_t parent; rank_pmap_t rank_index(rank); parent_pmap_t parent_index(parent); group_sets_t groups( rank_index, parent_index ); key_set keys; int a, b; while (std::cin >> a) { std::cin >> b; add_data(a, b, groups, keys); } build_output(groups, keys); //std::cout << "number of sets: " << // groups.count_sets(keys.begin()), keys.end()) << std::endl; } 

Я много часов учился тому, как использовать boost::disjoint_sets для решения этой проблемы. На нем, похоже, не много документации.

О производительности. Структура disjoint_sets – это O (α (n)) для его ключевых операций ( make_set , find_set и union_set ), которая довольно близка к константе, и поэтому, если бы это было всего лишь вопрос построения структуры, весь алгоритм был бы O (n α (n)) (что эффективно O (n)), но мы должны его распечатать. Это означает, что мы должны создать некоторые ассоциативные контейнеры, которые не могут работать лучше, чем O (n log n). Можно было бы получить постоянный коэффициент ускорения, выбирая различные ассоциативные контейнеры (скажем, hash_set т. Д.), Так как после заполнения начального списка вы можете зарезервировать оптимальное пространство.

Итак, у меня есть что-то, работающее параллельно с другим решением, отправленным @Jonathan (прежде всего, большое спасибо за ваше время). Мое решение выглядит обманчиво простым, но мне бы хотелось, чтобы некоторые предложения о том, правильно ли это (может быть, я где-то упускаю уголок?), Потому что он, кажется, производит вывод, который я хотел, но мне придется разбирать его во втором проходе в группу те же групповые числа, которые тривиальны. Логика заключается в том, что каждый раз, когда он находит новое число, а не в массиве, он увеличивает счетчик group_id:

Мой код в PHP:

 <?php //$fp = fopen("./resemblance.1.out", "r"); $fp = fopen("./wrong", "r"); $groups = array(); $group["-1"] = 1; $groups[] = $group; $map = array(); //Maintain a count $group = 1; while(!feof($fp)) { $source = trim(fgets($fp, 4096)); //echo $source."\n"; $source = explode(" ", $source); if(array_key_exists($source[0], $map) && !array_key_exists($source[1], $map)) { $map[$source[1]] = $map[$source[0]]; } else if(array_key_exists($source[1], $map) && !array_key_exists($source[0], $map)) { $map[$source[0]] = $map[$source[1]]; } else if(array_key_exists($source[1], $map) && array_key_exists($source[0], $map) && $map[$source[1]] != $map[$source[0]]) { // Adjust the groups - change the groups of one of the elements to the other $keys = array_keys($map, $map[$source[1]]); print_r($keys); foreach($keys as $key) { $map[$key] = $map[$source[0]]; } } else { $group++; $map[$source[0]] = $group; $map[$source[1]] = $group; } } print_r($map); ?> 

Вывод:

 Array ( [1] => 2 [2] => 2 [3] => 3 [4] => 3 [5] => 4 [9] => 4 [6] => 2 [7] => 3 [] => 5 ) 

EDIT: Исправлена ​​ошибка, о которой упоминалось в комментарии. Просто играя из любопытства 🙂 Не стесняйтесь указывать на любые другие ошибки. В настоящее время я тестирую, какое решение выполняется быстрее.

Вот пример решения Perl, которое работает с исходным набором данных:

 1 2 3 4 5 9 2 6 3 7 Group 1: 1 2 6 Group 2: 3 4 7 Group 3: 5 9 

В большом наборе данных он выводит результат:

 Group 1: 1 27 134 137 161 171 275 309 413 464 627 684 744 Group 2: 2 135 398 437 548 594 717 738 783 798 912 Group 3: 5 74 223 Group 4: 7 53 65 122 237 314 701 730 755 821 875 884 898 900 930 Group 5: 8 115 Group 6: 9 207 305 342 364 493 600 676 830 941 Group 7: 10 164 283 380 423 468 577 Group 8: 11 72 132 276 306 401 515 599 Group 9: 12 95 126 294 Group 10: 13 64 172 528 Group 11: 14 396 Group 12: 15 35 66 210 226 360 588 Group 13: 17 263 415 474 648 986 Group 14: 21 543 771 Group 15: 22 47 Group 16: 23 70 203 427 590 Group 17: 24 286 565 Group 18: 25 175 Group 19: 26 678 Group 20: 29 787 

Насколько это достаточно эффективно, это отдельный вопрос …

 use strict; use warnings; my %cache = (); while (<>) { chomp; my($x,$y) = split /\s+/; #print "$x $y\n"; $cache{$x}{$y} = 1; $cache{$y}{$x} = 1; } my $grp = 1; foreach my $key (sort { $a <=> $b } keys %cache) { #print "key: $key\n"; if (defined $cache{$key}) { my %result = (); subkey_search(\%result, $key); print "Group $grp:"; $grp++; foreach my $val (sort { $a <=> $b } keys %result) { print " $val"; } print "\n"; } } sub subkey_search { my($resultref, $key) = @_; my %hash = %{$cache{$key}}; delete $cache{$key}; $resultref->{$key} = 1; foreach my $subkey (sort keys %hash) { #print "subkey: $subkey\n"; subkey_search($resultref, $subkey) if (defined $cache{$subkey}); } } 

Вот немного другая версия в Python, которая строит график, содержащий указанные ребра, а затем преобразует его в список связанных подграфов.

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

 def graph_to_connected_subgraphs(graph): trees = [] for start in graph.keys(): if start in graph: list = [start] append_tree_from(graph, start, list) trees.append(list) return trees def append_tree_from(graph, node, list): if node in graph: for endpoint in graph[node]: list.append(endpoint) append_tree_from(graph, endpoint, list) del graph[node] return list def add_edge(graph, f, s): if s < f: # ensure f < s to handle cyclic graphs f, s = s, f if f not in graph: graph[f] = [s] else: graph[f].append(s) graph = {} add_edge(graph, 1,2) add_edge(graph, 2,6) add_edge(graph, 3,4) add_edge(graph, 5,9) add_edge(graph, 3,7) print graph_to_connected_subgraphs(graph) 

Вывод

 [[1, 2, 6], [3, 4, 7], [5, 9]] 

Это типичное приложение алгоритма DFS (Depth First Search), выполняемого на графиках. Попробуйте прочитать это dfs. Сложность этого алгоритма – O (| V | + | E |), где V – число вершин и E – число ребер

Вот мой удар в ответ. Python.

 groups = [] infile = open("so2.txt") for line in infile.readlines(): newset = set(line.split()) matchgroups = [] excludegroups = [] for group in groups: if len(newset & group): newset |= group else: excludegroups.append(group) groups = excludegroups groups.append( newset) for i, s in enumerate(groups): print "%d: %s"%(i, " ".join(s)) 

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

Моя версия на PHP фактически является рефакторингом вашего кода. Он исправляет одну проблему в вашем коде (у вас есть одна группа слишком много) и реализована немного более эффективно (время Exec падает с 0.0035 до 0.0020 на медленной машине):

 $group = 0; $map = array(); do { list($a, $b) = explode(' ', fgets($file)); $a = (int) $a; $b = (int) $b; if (!isset($map[$a]) && !isset($map[$b])) { $map[$a] = $map[$b] = ++$group; } elseif (!isset($map[$b])) { $map[$b] = $map[$a]; } elseif (!isset($map[$a])) { $map[$a] = $map[$b]; } elseif ($map[$a] != $map[$b]) { // move one group to the other foreach ($map as $n => $g) { if ($g == $map[$b]) { $map[$n] = $map[$a]; } } } } while (!feof($file)); // print results $results = array(); foreach ($map as $val => $group) { $results[$group][] = $val; } echo '<pre>'; $i = 0; foreach ($results as $result) { sort($result); echo 'Group ', ++$i, ': ', implode(' ', $result), "\n"; } 

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

Это очень быстро, потому что:

• он сохраняет хэш-карту от узла до своего «конечного владельца» (который является узлом с наименьшим идентификатором в подключенном компоненте), который позволяет искать и вставлять «1-й владелец».
• он сохраняет хеш-карту от каждого «конечного владельца» до строки результата, которая позволяет Ο (1) искать и вводить строку результатов.
• каждая строка результата является связанным списком, который позволяет добавлять (1).
• он хранит связанный список строк результатов, который позволяет:
  • Ο (1) добавление.
  • доступ к нему, не обойдя расходы, связанные с запросом предыдущей хэш-карты для всех ее значений

 import java.util.Scanner; import java.util.Map; import java.util.HashMap; import java.util.List; import java.util.LinkedList; public final class Solver { public static void main(String[] args) { Scanner in = new Scanner(System.in); final Map<Integer, Integer> ultimateOwners = new HashMap<Integer, Integer>(); final Map<Integer, List<Integer>> ownerToOwned = new HashMap<Integer, List<Integer>>(); final List<List<Integer>> results = new LinkedList<List<Integer>>(); while (in.hasNextInt()) { // Get ultimate owner. int owner = in.nextInt(); if (ultimateOwners.containsKey(owner)) owner = ultimateOwners.get(owner); // Get owned and register its ultimate owner. final int owned = in.nextInt(); ultimateOwners.put(owned, owner); // Add owned to result. if (ownerToOwned.containsKey(owner)) ownerToOwned.get(owner).add(owned); else { final List<Integer> resultLine = new LinkedList<Integer>(); resultLine.add(owner); resultLine.add(owned); ownerToOwned.put(owner, resultLine); results.add(resultLine); } } int lineNumber = 1; for (final List<Integer> line : results) { System.out.printf("%d: ", lineNumber++); for (final Integer value : line) { System.out.printf("%d ", value); } System.out.println(); } } } в import java.util.Scanner; import java.util.Map; import java.util.HashMap; import java.util.List; import java.util.LinkedList; public final class Solver { public static void main(String[] args) { Scanner in = new Scanner(System.in); final Map<Integer, Integer> ultimateOwners = new HashMap<Integer, Integer>(); final Map<Integer, List<Integer>> ownerToOwned = new HashMap<Integer, List<Integer>>(); final List<List<Integer>> results = new LinkedList<List<Integer>>(); while (in.hasNextInt()) { // Get ultimate owner. int owner = in.nextInt(); if (ultimateOwners.containsKey(owner)) owner = ultimateOwners.get(owner); // Get owned and register its ultimate owner. final int owned = in.nextInt(); ultimateOwners.put(owned, owner); // Add owned to result. if (ownerToOwned.containsKey(owner)) ownerToOwned.get(owner).add(owned); else { final List<Integer> resultLine = new LinkedList<Integer>(); resultLine.add(owner); resultLine.add(owned); ownerToOwned.put(owner, resultLine); results.add(resultLine); } } int lineNumber = 1; for (final List<Integer> line : results) { System.out.printf("%d: ", lineNumber++); for (final Integer value : line) { System.out.printf("%d ", value); } System.out.println(); } } } 

Не будучи полностью удовлетворенными моими 2-мя попытками этого и некоторыми исследованиями, я наткнулся на этот рецепт для непересекающихся множеств в Python, с благословением и вкладом Раймонда Хеттингера. (Раймонд Хеттингер – давний очень активный разработчик Python).

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

Сбор должен быть максимально эффективным для очень больших наборов данных, так как большая часть заданных операций в Python реализована на C. Вводные данные не нужно сортировать. Для печати я сортировал выходы исключительно для удобства чтения, но если это влияет на производительность, соединения могут печататься без сортировки.

 # ~~~~~ # data, setup input = ''' 1 2 3 4 2 3 ''' # etc. def lgen(): for l in input.splitlines(): l = l.strip() if l: yield tuple(int(i) for i in l.split()) # ~~~~~ # collect connections = {} # this is a mapping of values to the connections they are in # each node will map to a shared object instance of the connection it is in # eg {1: set([1,2]), 2: set([1,2])}, where the 2 sets are the same object for x, y in lgen(): cx = connections.setdefault(x, set([x])) # if not found, create new connection with this single value cy = connections.get(y) # defaults to None if not found if not cy: # if we haven't come across this value yet... cx.add(y) # ...add it to the current connection... connections[y] = cx # ...and update the reference elif cy is not cx: # if the cy connection is not the exact same object as the cx connection... if len(cy) > len(cx): # \ cx, cy = cy, cx # >... merge them ... cx |= cy # / connections[y] = cx # ...and update the reference # ~~~~~ # print seen = set() for key in sorted(connections.keys()): if key not in seen: c = connections[key] print sorted(c) seen |= c 

Это действительно классический союз-находка .

Если M – количество ребер, N – количество узлов, то временная сложность O (M * α (M)), которая является O (M) для всех практических M и пространственной сложности, если O (N) с N количество узлов.

Алгоритм находится в режиме онлайн и не обязательно должен знать все края (по сравнению с другими решениями об обратном графике) и, следовательно, может очень хорошо масштабироваться. Также нет необходимости заказывать ребра , их можно указывать в любом порядке.

Для графа с миллиардами узлов вам потребуется 64 бит / длинный int и много ОЗУ, но он должен обрабатывать миллионы узлов и миллиарды ребер очень хорошо.

Реализация выполняется на C ++, но используется только вектор / карта, которую вы можете найти практически на любом языке, который вы, возможно, захотите использовать.

Но поскольку у вас есть уникальный идентификатор для каждого элемента, нам нужно сопоставить эти id с целыми (непрерывными).

Первая версия без отображения (предположим, что все узлы между 1 и N существуют):

 #include <cstdio> #include <algorithm> #include <vector> using namespace std; const int MAX_N = 1000*1000; int p[MAX_N],f[MAX_N]; int parent(int a) { return p[a] == a ? a : p[a] = parent(p[a]); } bool join(int a, int b) { p[a = parent(a)] = parent(b); return p[a] != a; } int main() { // First integer in the file : number of nodes in the graph int N; scanf("%d",&N); // Union-find in O(M * alpha(M)) ~= O(M) // M = number of lines in the file for(int i = 1; i <= N ; i++) { p[i] = i; f[i] = -1; } int a,b; while(scanf("%d%d",&a,&b) != EOF) join(a,b); // Determine the number of groups : O(M) int nG = 0; for(int i = 1 ; i <= N ; i++) { p[i] = parent(p[i]); if(f[p[i]] == -1) f[p[i]] = nG++; } // Build groups : O(M) vector< vector<int> > Groups(N+1); for(int i = 1 ; i <= N ; i++) Groups[ f[p[i]] ].push_back(i); // Output result for(int i = 0 ; i < Groups.size() ; i++) { if(!Groups[i].size()) continue; printf("%d : ",i); for(int j = 0 ; j < Groups[i].size() ; j++) printf("%d ",Groups[i][j]); printf("\n"); } } к #include <cstdio> #include <algorithm> #include <vector> using namespace std; const int MAX_N = 1000*1000; int p[MAX_N],f[MAX_N]; int parent(int a) { return p[a] == a ? a : p[a] = parent(p[a]); } bool join(int a, int b) { p[a = parent(a)] = parent(b); return p[a] != a; } int main() { // First integer in the file : number of nodes in the graph int N; scanf("%d",&N); // Union-find in O(M * alpha(M)) ~= O(M) // M = number of lines in the file for(int i = 1; i <= N ; i++) { p[i] = i; f[i] = -1; } int a,b; while(scanf("%d%d",&a,&b) != EOF) join(a,b); // Determine the number of groups : O(M) int nG = 0; for(int i = 1 ; i <= N ; i++) { p[i] = parent(p[i]); if(f[p[i]] == -1) f[p[i]] = nG++; } // Build groups : O(M) vector< vector<int> > Groups(N+1); for(int i = 1 ; i <= N ; i++) Groups[ f[p[i]] ].push_back(i); // Output result for(int i = 0 ; i < Groups.size() ; i++) { if(!Groups[i].size()) continue; printf("%d : ",i); for(int j = 0 ; j < Groups[i].size() ; j++) printf("%d ",Groups[i][j]); printf("\n"); } } 

Версия с отображением: для этой версии нам нужно построить отображение. Поскольку я ничего не знаю о ваших данных, я использую классическую map для ее создания в O (M log (N)) , если вы можете отправить идентификатор всех узлов в начале входного файла, это может быть O (N log (N)) или даже лучше, если вы используете Hash-карту ( O (N) ), или если вы можете сами построить сопоставление, с некоторым пониманием графика.

Во всяком случае, вот код:

 #include <cstdio> #include <algorithm> #include <vector> #include <map> using namespace std; const int MAX_N = 1000*1000; int p[MAX_N],f[MAX_N]; int parent(int a) { return p[a] == a ? a : p[a] = parent(p[a]); } bool join(int a, int b) { p[a = parent(a)] = parent(b); return p[a] != a; } // Mapping int N = 0; map<int,int> indMap,invMap; int IND(int x) { if(indMap.find(x) == indMap.end()) { N++; p[N] = N; f[N] = -1; indMap[x] = N; } invMap[ indMap[x] ] = x; return indMap[x]; } int main() { // Union-find in O(M * alpha(M)) ~= O(M) // M = number of lines in the file int a,b; while(scanf("%d%d",&a,&b) != EOF) join(IND(a),IND(b)); // Determine the number of groups : O(M) int nG = 0; for(int i = 1 ; i <= N ; i++) { p[i] = parent(p[i]); if(f[p[i]] == -1) f[p[i]] = nG++; } // Build groups : O(M) vector< vector<int> > Groups(N+1); for(int i = 1 ; i <= N ; i++) Groups[ f[p[i]] ].push_back(i); // Output result for(int i = 0 ; i < Groups.size() ; i++) { if(!Groups[i].size()) continue; printf("%d : ",i+1); for(int j = 0 ; j < Groups[i].size() ; j++) printf("%d ", invMap[ Groups[i][j] ]); printf("\n"); } }