Prolog 中的高效可变图表示？
我想以有效的方式在 Prolog 中表示可变图。我将在图中搜索子集并用其他子集替换它们。
我已经成功地使用数据库作为我的“图形存储”来工作。例如，我有：
:- dynamic step/2.
% step(Type, Name).
:- dynamic sequence/2.
% sequence(Step, NextStep).
然后，我使用一些规则来收回我匹配的子集，并使用assert将它们替换为新步骤。我真的很喜欢这种方法……它很容易阅读和处理，而且我让 Prolog 完成很多繁重的模式匹配工作。
我知道的表示图的另一种方法是使用节点和邻接连接的列表。我见过很多网站使用这种方法，但我有点犹豫，因为它的开销更大。
执行时间对我来说很重要，开发的难易程度对我来说也很重要。
这两种方法的优缺点是什么？
I would like to represent a mutable graph in Prolog in an efficient manner. I will searching for subsets in the graph and replacing them with other subsets.
I've managed to get something working using the database as my 'graph storage'. For instance, I have:
:- dynamic step/2.
% step(Type, Name).
:- dynamic sequence/2.
% sequence(Step, NextStep).
I then use a few rules to retract subsets I've matched and replace them with new steps using assert. I'm really liking this method... it's easy to read and deal with, and I let Prolog do a lot of the heavy pattern-matching work.
The other way I know to represent graphs is using lists of nodes and adjacency connections. I've seen plenty of websites using this method, but I'm a bit hesitant because it's more overhead.
Execution time is important to me, as is ease-of-development for myself.
What are the pros/cons for either approach?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
像往常一样：使用动态数据库可以为您提供索引，这可能会加快速度（查找时）并减慢速度（断言时）。一般来说，当断言次数多于查找次数时，动态数据库就不太好。但主要缺点是它也使测试和调试变得非常复杂，因为您无法单独测试谓词，并且需要记住数据库的当前隐式状态。在许多情况下，节点和邻接连接的列表是一个很好的表示。我非常喜欢的另一种表示方式，特别是如果您需要存储节点和边的更多属性，是为每个节点使用一个变量，并使用变量属性（SWI-Prolog 中的 get_attr/3 和 put_attr/3）来存储边在它们上，例如 [edge_to(E1,N_1),edge_to(E2,N_2),...] 其中 N_i 是代表其他节点（具有自己的属性）的变量，E_j 也是如果需要，您可以附加更多属性来存储有关每条边的附加信息（重量、容量等）的变量。
As usual: Using the dynamic database gives you indexing, which may speed things up (on look-up) and slow you down (on asserting). In general, the dynamic database is not so good when you assert more often than you look up. The main drawback though is that it also significantly complicates testing and debugging, because you cannot test your predicates in isolation, and need to keep the current implicit state of the database in mind. Lists of nodes and adjacancy connections are a good representation in many cases. A different representation I like a lot, especially if you need to store further attributes for nodes and edges, is to use one variable for each node, and use variable attribtues (get_attr/3 and put_attr/3 in SWI-Prolog) to store edges on them, for example [edge_to(E1,N_1),edge_to(E2,N_2),...] where N_i are the variables representing other nodes (with their own attributes), and E_j are also variables onto which you can attach further attributes to store additional information (weight, capacity etc.) about each edge if needed.
您是否考虑过使用 SWI-Prolog 的 RDF 数据库？ http://www.swi-prolog.org/pldoc/package/semweb.html
Have you considered using SWI-Prolog's RDF database ? http://www.swi-prolog.org/pldoc/package/semweb.html
正如 mat 所说，动态谓词有额外的成本。
但是，如果您可以构造图，然后不需要更改它，您可以编译谓词，它将与普通谓词一样快。
通常在 sw-prolog 中，谓词查找是使用第一个参数上的哈希表完成的。 （在动态谓词的情况下调整它们的大小）
另一个解决方案是 关联列表，其中查找等的成本是o(log(n))
了解它们的工作原理后，如果需要，您可以轻松编写界面。
最后，您始终可以使用 SQL 数据库并使用 ODBC 接口 提交查询（尽管这听起来对于您提到的应用程序来说有点大材小用）
as mat said, dynamic predicates have an extra cost.
in case however you can construct the graph and then you dont need to change it, you can compile the predicate and it will be as fast as a normal predicate.
usually in sw-prolog the predicate lookup is done using hash tables on the first argument. (they are resized in case of dynamic predicates)
another solution is association lists where the cost of lookup etc is o(log(n))
after you understand how they work you could easily write an interface if needed.
in the end, you can always use a SQL database and use the ODBC interface to submit queries (although it sounds like an overkill for the application you mentioned)