1

是否有一种普遍接受的方法来比较可能包含长值列表的不可变对象？

到目前为止，我的界面如下：

interface Formula : IEquatable<Formula> {
   IList<Symbol> Symbols {get;}
}

interface Symbol : IEquatable<Symbol> {
   String Value {get;}
}

在这里，不可变数据类型Formula表示Symbol's 的序列。所以在一个公式中：

x -> y

符号将是x, ->, y.

我想根据它们的内容（例如符号列表）比较两个公式。所以对于一些任意的符号列表new Formula(symbols)来说是相等的。new Formula(symbols)

但是，我不想一直迭代地比较两个列表。

在实现中，我正在考虑在初始化期间创建某种计算值Formula- 并使用它进行比较。但是，这将需要我向我的界面添加某种方法。我会怎么称呼这种方法？

我不确定是否适合为此使用哈希码，因为它似乎仅限于整数。

任何帮助表示赞赏 - 如果有不清楚的地方，我会修改我的问题。谢谢！

4

5 回答 5

5

您绝对可以为此使用哈希码。不要忘记哈希码不必是唯一的- 如果它不经常产生冲突（具有相同哈希码的两个不相等序列），它只会有帮助。（至少，尝试提出一种方法，在明显的情况下避免使用相等的哈希码。）

因此，您可以在构造时计算一次哈希码（通过依次组合每个符号的哈希码），然后将其返回，GetHashCode而无需每次都重新计算。这意味着您只需要比较具有相等哈希码的序列 - 这对于不相等的序列很少发生。

于 2012-05-29T20:40:17.003 回答
2

不，您必须比较所有元素。您不能使用哈希码或类似方法，因为可能的公式集是无限的，而可能的哈希码集是有限的。

正如 Jon Skeet 所指出的，您可以使用哈希码来减少逐个元素比较公式的需要，但您不能消除这种需要。当两个公式的哈希码不相等时，您知道这些公式不相等，但是当它们的哈希码相等时，您需要逐个元素地比较它们是否相等。

于 2012-05-29T20:41:46.410 回答
1

我相信这不是你需要做的全部......

a+b = (a+b)

会导致你的方法是错误的。

我相信你必须为两边的表达式构建 AST（抽象语法树），然后比较表达式。AST 将取消括号，因为它们在 AST 中表示为层次结构。

hth

马里奥

于 2012-05-29T20:41:12.097 回答
1

这有点像覆盖 GetHashCode 的另一个答案，但我有不同的方法......因为公式似乎有一个字符串表示......

你不能覆盖 GetHashCode 并在覆盖中做一个

foreach(char c in ToString().ToCharArray()){

int hashCode |= c;

}

这样做的结果将产生一个 4 字节代码，它是等式中符号的打包表示......

如果每个符号都有可以在 HashTable 中查找的特定 OpCode，则可以采取进一步措施。

我会用每个 OpCode 的别名构建 HashTable，这样每个 Symbol 就不必声明属性 OpCode。

然后，我将在 Symbol 类上创建一个 Extension ToOpCode，该类在上述 HashTable 中进行查找。

然后我会在 GetHashCode 中使用 Extension 方法，例如

公式....

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 + bandb + a和（((a) + (b))如果需要）。

例如，您可能想知道方程式是否与某种方法完全相同，但在另一种方法中，您可能想知道方程式是否在做同样的事情，但不是以完全相同的方式写成。

这也将允许您以不同的方式确定相等性，例如检查范围深度是否匹配以及等式中的步数是否完全相同，而不仅仅是基于哈希码假设。

例如，您可以按如下方式转换以确定以下内容：

hash << 8 将是 parens 的部门 hash << 16 将是堆栈的上一个或下一个等式指针 hash << 24 将是等式中的符号或代码值延续或变量数（不包括）

你也可以只做 hash == anotherHash 但是这种方式给你更多的灵活性，几乎没有开销。

如果您在 Hash 中需要更多空间，则创建一个返回 long 的新方法 GetExtendedHashCode，然后在 GetHashCode 中移位/向下转换或重新格式化 ExtendedHashCode 以匹配 CLR 所需的 int 格式。

您还可以获得符号能够以这种方式表示变量和值的好处，方法是将它们留在堆栈上并像 CLR 一样使用它们。

于 2012-05-29T21:00:31.543 回答
0

首先，我建议不要IEquatable<T>对任何非密封类型实施T。在非密封类型上实现的唯一安全方法IEquatable<T>.Equals通常是调用虚方法Object.Equals。否则，其父类IEquatable<T>为一种或多种类型实现的类可能T会覆盖Object.Equals而不Object.GetHashCode重新实现其所有IEquatable<T>接口；因此，任何未重新实现的此类接口都将被破坏。

其次，如果在比较两个Formula实例中的列表时，发现一对对应的Symbol引用是等价的但引用不同的实例，调用System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode()每个实例可能会有所帮助。如果一个比较大于另一个，则将具有较大RunTimeHelpers.GetHashCode()值的引用替换为另一个列表中的引用。这将加速这些列表的任何未来比较。此外，如果重复比较具有相同项目的多个列表，则所有列表将“倾向于”具有相同的Symbol实例。

最后，如果发现列表是相等的，并且列表应该是“语义上”不可变的，则可以使用相同的RuntimeHelpers.GetHashCode()技巧来选择一个List实例。这将加快未来的比较。

于 2012-06-01T21:14:15.997 回答