比较不可变的数据类型
本文关键字:数据类型 不可变 比较 | 更新日期: 2023-09-27 18:35:44
是否有一种普遍接受的方法来比较可能包含长值列表的不可变对象?
到目前为止,我的界面如下:
interface Formula : IEquatable<Formula> {
IList<Symbol> Symbols {get;}
}
interface Symbol : IEquatable<Symbol> {
String Value {get;}
}
在这里,不可变数据类型Formula
表示Symbol
的序列。所以在一个公式中:
x -> y
符号将是x
、->
、y
。
我想根据其内容(例如符号列表)比较两个公式。因此,对于某些任意的符号列表,new Formula(symbols)
等于new Formula(symbols)
。
但是,我不想一直反复比较两个列表。
在实现过程中,我正在考虑在Formula
初始化期间创建某种计算值 - 并将其用于比较。但是,这将需要我向我的界面添加某种方法。我该怎么称呼这种方法?
我不确定为此使用哈希代码是否合适,因为它似乎仅限于整数。
任何帮助表示赞赏 - 如果有什么不清楚的地方,我会修改我的问题。谢谢!
您绝对可以使用哈希代码。不要忘记,哈希代码不一定是唯一的 - 如果它不经常发生冲突(具有相同哈希代码的两个不相等序列),它就会有所帮助。(至少,尝试想出一种方法,避免在明显的情况下使用相等的哈希码。
因此,您可以在构造时计算一次哈希代码(通过依次组合每个符号的哈希代码),然后从GetHashCode
返回该哈希代码,而无需每次都重新计算它。这意味着您只需要比较具有相等哈希码的序列 - 这对于不相等的序列很少发生。
不,您必须比较所有元素。 不能使用哈希代码或类似的方法,因为可能的公式集是无限的,而可能的哈希代码集是有限的。
正如 Jon Skeet 所指出的,您可以使用哈希代码来减少逐个元素比较公式的需要,但您无法消除这种需求。 当两个公式具有不相等的哈希代码时,您知道公式是不相等的,但是当它们具有相等的哈希代码时,您需要逐个元素进行比较以查看它们是否相等。
我相信这不是你需要做的全部......
a+b = (a+b)
会导致您的方法错误。
我相信您必须为两边的表达式构建 AST(抽象语法树),然后比较表达式。 AST 将消除参数,因为它们在 AST 中表示为层次结构。
呵呵
马里奥
有点像覆盖GetHashCode的另一个答案,但我有不同的方法......由于公式似乎具有字符串表示形式....
您不能覆盖GetHashCode并在覆盖中执行
foreach(char c in ToString().ToCharArray()){
int hashCode |= c;
}
这样做的结果将产生一个 4 字节代码,它是等式中符号的打包表示......
如果每个符号都有特定的操作码,可以在哈希表中查找,则可以进一步采取。
我会用每个操作码的别名构建哈希表,这样每个符号就不必声明属性 OpCode。
然后,我将在符号类上创建一个扩展ToOpCode,该扩展在上述HashTable中进行查找。
然后,我将在GetHashCode中使用扩展方法,例如
公式。。。。
public override int GetHashCode(){
foreach(Symbol c in Symbols){
int hashCode |= c.ToOpCode();
}
}
象征。。。。
public override int GetHashCode(){
retuurn Extensions.ToOpCode(this);
}
此实现将为 a + b 和 b + a 产生相同的哈希值,这在您的问题中非常重要......
此外,如果您正确地连续指定了OpCode,则在技术上能够以以下形式比较方程:
(a) + (b)
== (a+b)
这将通过确保括号操作码在哈希码中与数字不同的地方被赋予一个值来实现......
例如,如果您有 4 个字节(整数),则作用域深度可以保留在第一个字节中,堆栈中上一个或下一个等式/符号的索引将是下一个,接下来的两个字节将保留用于符号数据和等式中的值/延续或变量数量(不包括)。
这允许您告诉某些事情,例如嵌套级别的数量等,因此您基本上也可以覆盖 Equals,以确保您可以区分a + b
和b + a
,并在需要时((a) + (b))
。
与某种方法完全相同,但在另一种方法中,您可能想知道方程是否在做同样的事情,但写法并不完全相同。
这也将允许您以不同的方式确定相等性,例如检查范围深度是否匹配以及等式中是否有完全相同的步骤数,而不仅仅是基于哈希代码假设。
例如,您可以按如下方式进行切换以确定诸如:
哈希<<8 将是括号的部门哈希<<16 将是堆栈的上一个或下一个等式指针哈希<<24 将是等式中的符号或代码值延续或变量数(不包括)
你也可以只做哈希 == 另一个哈希,但这种方式给你提供了更大的灵活性,几乎没有开销。
如果你在哈希中需要更多空间,那么创建一个新的方法GetExtendedHashCode,它返回long,然后在GetHashCode中移动/向下转换或重新格式化ExtendedHashCode,以匹配CLR所需的int格式。
您还具有符号能够以这种方式表示变量和值的好处,方法是将它们保留在堆栈上并像 CLR 一样使用它们。
首先,我建议不要为任何非密封型T
实施IEquatable<T>
。 在未密封类型上实现IEquatable<T>.Equals
的唯一安全方法通常是调用虚拟方法Object.Equals
。 否则,其父类为一个或多个类型实现IEquatable<T>
的类可能会覆盖Object.Equals
和Object.GetHashCode
T
而无需重新实现其所有IEquatable<T>
接口;因此,任何未重新实现的此类接口都将被破坏。
其次,如果在比较两个Formula
实例中的列表时,发现一对相应的Symbol
引用是等效的,但引用不同的实例,则在每个实例上调用System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode()
可能会有所帮助。 如果一个比较大于另一个,请将具有较大RunTimeHelpers.GetHashCode()
值的引用替换为另一个列表中的引用。 这将加速今后对这些名单的任何比较。 此外,如果反复比较具有相同项目的多个列表,则所有列表都将"倾向于"具有相同的Symbol
实例。
发现列表是相等的,并且如果列表应该是"语义上"不可变的,则可以使用相同的RuntimeHelpers.GetHashCode()
技巧来选择List
实例。 这将加快未来的比较。