我是Haskell的新手(几个月).我有一个Haskell程序,它组装一个大表达式DAG(不是树,DAG),可能很深,并且有多个合并路径(即,从根到叶的不同路径的数量很大).我需要一种快速的方法来测试这些dag是否相等.默认的Eq推导只会递归,多次探索相同的节点.目前这导致我的程序对于相对较小的表达式需要60秒,而对于较大的表达式甚至不能完成.分析器指示它正忙于在大多数时间检查相等性.我想实现一个没有这个问题的自定义Eq.我没有办法解决这个不涉及大量重写的问题.所以我想听听你的想法.
我的第一次尝试是使用Data.Hashable.hash我在构建树时使用我逐步计算的哈希"检测"树节点.这种方法给了我一个简单的方法来测试两个不相等的东西而不深入研究结构.但通常在这个DAG中,由于DAG合并中的路径,结构确实相等.所以哈希是平等的,我恢复全面的平等测试.
如果我有办法实现身体平等,那么我的很多问题都会消失:如果它们在物理上是平等的,那就是它.否则,如果哈希值不同,那就是它.只有在物理上不一样的情况下才会更深入,但他们的哈希同意.
我也可以模仿git,并计算每个节点的SHA1以确定它们是否是相等的周期(无需递归).我知道这会有所帮助,因为如果我在哈希等式方面完全决定等式,那么程序在几十毫秒内运行最大的表达式.这种方法还有一个很好的优点,即如果由于某种原因有两个相等的dag在物理上不相同但是内容相等,那么我也能够在这种情况下快速检测到它.(对于Ids,Id仍然需要在那时进行遍历).所以我更喜欢语义.
然而,这种方法涉及的工作比调用Data.Hashable.hash函数要多得多,因为我必须为dag节点类型的每个变体派生它.而且,我有多个dag表示,节点定义略有不同,所以如果我决定添加更多表示,我需要基本上做两次或更多的散列技巧.
你会怎么做？
Pau*_*son 10
这里的部分问题是Haskell没有对象标识的概念,所以当你说你有一个DAG,你引用同一个节点两次时,就Haskell而言,它只涉及树上不同位置的两个值.这与OO概念根本不同,在OO概念中,对象通过其在内存中的位置来索引,因此"相同对象"和"具有相等字段的不同对象"之间的区别是有意义的.
要解决您的问题,您需要检测何时访问前面看到的同一个对象,并且为了做到这一点,您需要具有与该值无关的"相同对象"的概念.攻击方法有两种基本方法:
将所有对象存储在向量(即数组)中,并使用向量索引作为对象标识.在整个数据结构中用索引替换值.
为每个对象提供一个唯一的"标识"字段,这样您就可以在遍历DAG之前判断是否已经看过这个字段.
前者是容器包中的Data.Graph模块如何实现它.一个优点是,如果你有一个从DAG到vector的映射,那么DAG相等就变成了向量相等.