背景:
我正在做一个项目,我需要为文本处理编写一些规则。在为这个项目工作了几天并实施了一些规则之后,我意识到我需要确定规则的顺序。没问题,我们有拓扑排序来帮忙。但后来我意识到我不能指望图表总是满的。所以我想出了这个想法,给定具有一组依赖项(或单个依赖项)的单个规则,我需要检查依赖项的依赖关系。听起来很熟悉?是的。这个主题与图的深度优先搜索非常相似。
我不是数学家,也没有学过 CS 因此,图论对我来说是一个新领域。尽管如此,我实现了一些有效的东西(见下文)(我怀疑效率低下)。
编码:
这是我的搜索和收益算法。如果你在下面的例子中运行它,你会看到它不止一次地访问了一些节点。因此,推测效率低下。
关于输入的一句话。我写的规则基本上都是python类,有一个类属性depends
。我因不使用而受到批评inspect.getmro
-但这会使事情变得非常复杂,因为该类需要相互继承(请参见此处的示例)
def _yield_name_dep(rules_deps):
global recursion_counter
recursion_counter = recursion_counter +1
# yield all rules by their named and dependencies
for rule, dep in rules_deps.items():
if not dep:
yield rule, dep
continue
else:
yield rule, dep
for ii in dep:
i = getattr(rules, ii)
instance = i()
if instance.depends:
new_dep={str(instance): instance.depends}
for dep in _yield_name_dep(new_dep):
yield dep
else:
yield str(instance), instance.depends
好的,现在您已经查看了代码,下面是一些您可以测试的输入:
demo_class_content ="""
class A(object):
depends = ('B')
def __str__(self):
return self.__class__.__name__
class B(object):
depends = ('C','F')
def __str__(self):
return self.__class__.__name__
class C(object):
depends = ('D', 'E')
def __str__(self):
return self.__class__.__name__
class D(object):
depends = None
def __str__(self):
return self.__class__.__name__
class F(object):
depends = ('E')
def __str__(self):
return self.__class__.__name__
class E(object):
depends = None
def __str__(self):
return self.__class__.__name__
"""
with open('demo_classes.py', 'w') as clsdemo:
clsdemo.write(demo_class_content)
import demo_classes as rules
rule_start={'A': ('B')}
def _yield_name_dep(rules_deps):
# yield all rules by their named and dependencies
for rule, dep in rules_deps.items():
if not dep:
yield rule, dep
continue
else:
yield rule, dep
for ii in dep:
i = getattr(rules, ii)
instance = i()
if instance.depends:
new_dep={str(instance): instance.depends}
for dep in _yield_name_dep(new_dep):
yield dep
else:
yield str(instance), instance.depends
if __name__ == '__main__':
# this is yielding nodes visited multiple times,
# list(_yield_name_dep(rule_start))
# hence, my work around was to use set() ...
rule_dependencies = list(set(_yield_name_dep(rule_start)))
print rule_dependencies
问题:
- 我尝试对我的工作进行分类,我认为我所做的与 DFS 类似。你真的可以这样分类吗?
- 如何改进此功能以跳过访问过的节点,并且仍然使用生成器?
更新:
只是为了省去你运行代码的麻烦,上面函数的输出是:
>>> print list(_yield_name_dep(rule_wd))
[('A', 'B'), ('B', ('C', 'F')), ('C', ('D', 'E')), ('D', None), ('E', None), ('F', 'E'), ('E', None)]
>>> print list(set(_yield_name_dep(rule_wd)))
[('B', ('C', 'F')), ('E', None), ('D', None), ('F', 'E'), ('C', ('D', 'E')), ('A', 'B')]
与此同时,虽然我想出了一个更好的解决方案,但上面的问题仍然存在。所以请随意批评我的解决方案:
visited = []
def _yield_name_dep_wvisited(rules_deps, visited):
# yield all rules by their name and dependencies
for rule, dep in rules_deps.items():
if not dep and rule not in visited:
yield rule, dep
visited.append(rule)
continue
elif rule not in visited:
yield rule, dep
visited.append(rule)
for ii in dep:
i = getattr(grules, ii)
instance = i()
if instance.depends:
new_dep={str(instance): instance.depends}
for dep in _yield_name_dep_wvisited(new_dep, visited):
if dep not in visited:
yield dep
elif str(instance) not in visited:
visited.append(str(instance))
yield str(instance), instance.depends
上面的输出是:
>>>list(_yield_name_dep_wvisited(rule_wd, visited))
[('A', 'B'), ('B', ('C', 'F')), ('C', ('D', 'E')), ('D', None), ('E', None), ('F', 'E')]
所以你现在可以看到节点 E 只被访问一次。