姿势的有效增量实现
|
我正在根据SQLAlchemy实现一种具有部分排序集数学特征的结构,在该结构中,我需要能够一次添加和删除边。
在我目前的最佳设计中,我使用两个邻接列表,一个是分配列表(在Hass图中大约是边),因为我需要保留哪些节点对已明确设置为有序,而另一个邻接列表是可传递的首先关闭,以便我可以高效地查询一个节点是否相对于另一个节点排序。现在,每次在分配邻接列表中添加或删除边时,我都会重新计算可传递闭包。
看起来像这样:
assignment = Table(\'assignment\', metadata,
Column(\'parent\', Integer, ForeignKey(\'node.id\')),
Column(\'child\', Integer, ForeignKey(\'node.id\')))
closure = Table(\'closure\', metadata,
Column(\'ancestor\', Integer, ForeignKey(\'node.id\')),
Column(\'descendent\', Integer, ForeignKey(\'node.id\')))
class Node(Base):
__tablename__ = \'node\'
id = Column(Integer, primary_key=True)
parents = relationship(Node, secondary=assignment,
backref=\'children\',
primaryjoin=id == assignment.c.parent,
secondaryjoin=id == assignment.c.child)
ancestors = relationship(Node, secondary=closure,
backref=\'descendents\',
primaryjoin=id == closure.c.ancestor,
secondaryjoin=id == closure.c.descendent,
viewonly=True)
@classmethod
def recompute_ancestry(cls.conn):
conn.execute(closure.delete())
adjacent_values = conn.execute(assignment.select()).fetchall()
conn.execute(closure.insert(), floyd_warshall(adjacent_values))
其中“ 1”是同名算法的实现。
这导致我遇到两个问题。首先是它似乎效率不高,但是我不确定我可以使用哪种算法。
第二个更多的是关于每次分配发生时都必须显式调用“ 2”的实用性,并且只有在分配被冲刷到会话中并具有正确的连接之后才必须显式调用“ 2”。如果我想查看ORM中反映的更改,则必须再次刷新会话。我认为,如果我可以按照orm表示重新计算祖先操作,那会容易得多。
没有找到相关结果
已邀请:
2 个回复
感秆暴壳
春驹晴陪
如果您需要删除分配,则在纯sql中这会更快: