Leg*_*end 5 php c++ python algorithm graph
我有一些这样的数据:
1 2
3 4
5 9
2 6
3 7
我正在寻找这样的输出(group-id和该组的成员):
1: 1 2 6
2: 3 4 7
3: 5 9
第一行因为1"连接"到2而2连接到6.第二行因为3连接到4而3连接到7
这对我来说就像一个图遍历,但最终的顺序并不重要所以我想知道是否有人可以建议一个更简单的解决方案,我可以在大型数据集(数十亿条目)上使用.
来自评论:
编辑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发布的版本是我尝试的样本数据集中最快的.该数据集有大约100万个条目,在双四核2.4GHz机器上花了我大约6秒.我还没有机会在整个数据集上运行它,但我会尽快发布基准测试.
我已经成功了 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;
去掉一些 typedef 后，这就是真正的内容了。我正在使用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关键操作（make_set、find_set和union_set），结构的复杂度为 O(α(n) )，这非常接近常数，因此如果只是构建结构的问题，整个算法将是 O(n α(n) ）（实际上是 O(n) ），但我们必须将其打印出来。这意味着我们必须构建一些关联容器，其性能不能优于 O(n log n)。通过选择不同的关联容器（例如等），可能会获得恒定的加速hash_set，因为一旦填充初始列表，您就可以保留最佳的空间量。