Пытаетесь сгруппировать значения?

Question

У меня есть такие данные:

1 2
3 4
5 9
2 6
3 7

и ищу вывод, подобный этому (идентификатор группы и члены этой группы):

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

Первый ряд, потому что 1 «связан» с 2, а 2 - с 6. Второй ряд, потому что 3 подключен к 4, а 3 подключен к 7

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

---

Из комментариев:

• Задача состоит в том, чтобы найти множество непересекающихся подграфов по заданному набору ребер.
• Края не направлены; линия «1 2» означает, что 1 подключен к 2, а 2 подключен к 1.
• «1:» в примере вывода может быть «A:» без изменения значения ответа.

РЕДАКТИРОВАТЬ 1:

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

РЕДАКТИРОВАТЬ 2:

Тестовый входной файл:

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

Тесты:

Я опробовал все, и версия, опубликованная TokenMacGuy, является самой быстрой в наборе образцов данных, который я пробовал. В наборе данных содержится около 1 миллиона записей, на что мне потребовалось около 6 секунд на двухъядерном 2,4-ГГц компьютере. У меня еще не было возможности запустить его на всем наборе данных, но я опубликую эталонный тест, как только он станет доступен.

Answer 1

Мне удалось 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;

С некоторыми определениями типов, вот настоящее мясо. Я использую 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 (& alpha; (n)) для ее ключевых операций (make_set, find_set и union_set), которая довольно близка к постоянной, и поэтому, если бы это было просто вопросом построения структуры весь алгоритм был бы O (n & alpha; (n)) (что фактически равно O (n)), но мы должны распечатать его. Это означает, что мы должны создать несколько ассоциативных контейнеров, которые не могут работать лучше, чем O (n log n). Может быть возможно получить постоянное ускорение коэффициента, выбрав различные ассоциативные контейнеры (скажем, hash_set и т. Д.), Поскольку после заполнения начального списка вы можете зарезервировать оптимальный объем пространства.

Answer 2

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

Answer 3

Вот немного другая версия в 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]]

Answer 4

Хорошо, я получил что-то, работающее параллельно с другим решением, опубликованным @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
)

РЕДАКТИРОВАТЬ: Исправлена ​​ошибка, упомянутая в комментарии.Просто играю из любопытства :) Не стесняйтесь указывать на любые другие ошибки.В настоящее время я проверяю, какое решение быстрее.

Answer 5

Вот пример решения 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});
    }
}

Answer 6

Это на самом деле очень классический Union-find .

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

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

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

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

---

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

Первая версия без сопоставления (предположим, что существуют все узлы от 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");
    }

}

Версия с отображением: для этой версии нам нужно построить отображение. Поскольку я ничего не знаю о ваших данных, я использую классический map, чтобы встроить его в O (M log (N)) , если вы можете отправить идентификатор всех узлов на начало входного файла, это может быть O (N log (N)) или даже лучше, если вы используете Hash Map ( 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");
    }

}

Answer 7

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

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

Сбор должен быть максимально эффективным для очень больших наборов данных, так как большая часть операций над множествами в 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
                 # e.g. {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

Answer 8

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

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

• хранит хеш-карту от узла к своему «конечному владельцу» (который является узлом с самым низким идентификатором в подключенном компоненте), что позволяет & Omicron; (1) поиск и вставку «конечного владельца».
• хранит хэш-карту от каждого «конечного владельца» в строке результатов, что позволяет & Omicron; (1) искать и вставлять строку результатов.
• каждая строка результатов представляет собой связанный список, который позволяет & Omicron; (1) добавлять.
• хранит связанный список строк результатов, который позволяет:
  • & Omicron; (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();
    }
  }
}

Answer 9

Моя версия в PHP на самом деле является лишь рефакторингом вашего кода.Это исправляет одну проблему в вашем коде (у вас слишком много одной группы) и реализована несколько более эффективно (время выполнения уменьшается с 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";
}

Answer 10

Вот мой ответ на вопрос.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))

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