原始问题和简单算法
给定一组关系,如
a < c
b < c
b < d < e
找到一组以0开头的整数的最有效的算法是什么(尽可能多的重复整数!)这与一组关系相匹配,即在本例中
^{pr2}$简单的算法是在一组关系上反复迭代,并根据需要增加值,直到达到收敛,如下面在Python中实现的:
relations = [('a', 'c'), ('b', 'c'), ('b', 'd', 'e')]
print(relations)
values = dict.fromkeys(set(sum(relations, ())), 0)
print(values)
converged = False
while not converged:
converged = True
for relation in relations:
for i in range(1,len(relation)):
if values[relation[i]] <= values[relation[i-1]]:
converged = False
values[relation[i]] += values[relation[i-1]]-values[relation[i]]+1
print(values)
除了O(Relations²)的复杂性(如果我没弄错的话),如果给定了一个无效的关系(例如添加e<;d),这个算法也会进入一个无限循环。对于我的用例来说,检测这样的失败案例并不是绝对必要的,但这将是一个很好的奖励。在
基于Tim Peter评论的Python实现
relations = [('a', 'c'), ('b', 'c'), ('b', 'd'), ('b', 'e'), ('d', 'e')]
symbols = set(sum(relations, ()))
numIncoming = dict.fromkeys(symbols, 0)
values = {}
for rel in relations:
numIncoming[rel[1]] += 1
k = 0
n = len(symbols)
c = 0
while k < n:
curs = [sym for sym in symbols if numIncoming[sym] == 0]
curr = [rel for rel in relations if rel[0] in curs]
for sym in curs:
symbols.remove(sym)
values[sym] = c
for rel in curr:
relations.remove(rel)
numIncoming[rel[1]] -= 1
c += 1
k += len(curs)
print(values)
目前,它需要“拆分”关系(b<;d和d<;e而不是b<;d<;e),但循环的检测很容易(只要curs
为空且k<;n),并且应该可以更有效地实现它(特别是如何确定curs
和{
最坏情况下的计时(1000个元素,999个关系,倒序):
Version A: 0.944926519991
Version B: 0.115537379751
最佳情况时机(1000个元素,999个关系,转发顺序):
Version A: 0.00497004507556
Version B: 0.102511841589
平均大小写计时(1000个元素,999个关系,随机顺序):
Version A: 0.487685376214
Version B: 0.109792166323
测试数据可以通过
n = 1000
relations_worst = list((a, b) for a, b in zip(range(n)[::-1][1:], range(n)[::-1]))
relations_best = list(relations_worst[::-1])
relations_avg = shuffle(relations_worst)
<强> C++实现基于Tim Peter的回答< /强>(简化符号[0,n)]
vector<unsigned> chunked_topsort(const vector<vector<unsigned>>& relations, unsigned n)
{
vector<unsigned> ret(n);
vector<set<unsigned>> succs(n);
vector<unsigned> npreds(n);
set<unsigned> allelts;
set<unsigned> nopreds;
for(auto i = n; i--;)
allelts.insert(i);
for(const auto& r : relations)
{
auto u = r[0];
if(npreds[u] == 0) nopreds.insert(u);
for(size_t i = 1; i < r.size(); ++i)
{
auto v = r[i];
if(npreds[v] == 0) nopreds.insert(v);
if(succs[u].count(v) == 0)
{
succs[u].insert(v);
npreds[v] += 1;
nopreds.erase(v);
}
u = v;
}
}
set<unsigned> next;
unsigned chunk = 0;
while(!nopreds.empty())
{
next.clear();
for(const auto& u : nopreds)
{
ret[u] = chunk;
allelts.erase(u);
for(const auto& v : succs[u])
{
npreds[v] -= 1;
if(npreds[v] == 0)
next.insert(v);
}
}
swap(nopreds, next);
++chunk;
}
assert(allelts.empty());
return ret;
}
<强> C++实现,改进的缓存局部性>P>
vector<unsigned> chunked_topsort2(const vector<vector<unsigned>>& relations, unsigned n)
{
vector<unsigned> ret(n);
vector<unsigned> npreds(n);
vector<tuple<unsigned, unsigned>> flat_relations; flat_relations.reserve(relations.size());
vector<unsigned> relation_offsets(n+1);
for(const auto& r : relations)
{
if(r.size() < 2) continue;
for(size_t i = 0; i < r.size()-1; ++i)
{
assert(r[i] < n && r[i+1] < n);
flat_relations.emplace_back(r[i], r[i+1]);
relation_offsets[r[i]+1] += 1;
npreds[r[i+1]] += 1;
}
}
partial_sum(relation_offsets.begin(), relation_offsets.end(), relation_offsets.begin());
sort(flat_relations.begin(), flat_relations.end());
vector<unsigned> nopreds;
for(unsigned i = 0; i < n; ++i)
if(npreds[i] == 0)
nopreds.push_back(i);
vector<unsigned> next;
unsigned chunk = 0;
while(!nopreds.empty())
{
next.clear();
for(const auto& u : nopreds)
{
ret[u] = chunk;
for(unsigned i = relation_offsets[u]; i < relation_offsets[u+1]; ++i)
{
auto v = std::get<1>(flat_relations[i]);
npreds[v] -= 1;
if(npreds[v] == 0)
next.push_back(v);
}
}
swap(nopreds, next);
++chunk;
}
assert(all_of(npreds.begin(), npreds.end(), [](unsigned i) { return i == 0; }));
return ret;
}
<强> C++计时< /强> 10000个元素,9999个关系,平均超过1000次运行
“最坏情况”:
chunked_topsort: 4.21345 ms
chunked_topsort2: 1.75062 ms
“最佳案例”:
chunked_topsort: 4.27287 ms
chunked_topsort2: 0.541771 ms
“平均情况”:
chunked_topsort: 6.44712 ms
chunked_topsort2: 0.955116 ms
不同于Python版本,C++ ^ {< CD4}}明显取决于元素的顺序。有趣的是,随机顺序/平均情况是迄今为止最慢的(使用基于集合的chunked_topsort
)。在
下面是一个我之前没有时间发布的实现:
然后,例如
^{pr2}$希望有帮助。注意这里没有任何搜索(例如,没有条件列表理解)。从理论上讲,它是有效的。在
稍后:计时
在您的文章末尾生成的测试数据中,
chunked_topsort()
对输入的顺序几乎不敏感。这并不奇怪,因为算法只迭代输入一次,以构建其(固有的无序)dicts和set。总之,它比Version B
快15到20倍。3次运行的典型定时输出:使用更简单的数据结构
假设问题已经改变;-),这里有一个重写,假设输入是}也被传递。在输入关系的初始传递之后,没有集合,没有dict,也没有动态分配。在Python中,这比测试数据上的
range(n)
中的整数,并且{chunked_topsort()
快大约40%。但是我太老了,不能再和C++搏斗了。————<这在Python中同样对输入顺序不敏感。在
相关问题 更多 >
编程相关推荐