C#表达式比较

Question

假设我有一个集合上的以下表达式：

var people = new List<Person>
{
     new Person {FullName = "Some Dude", Age = 45},
     new Person {FullName = "Another Dude", Age = 28},
     new Person {FullName = "Some Other Dude", Age = 36}
 };

var filtered = people.Where(person => person.Age > 28 && person.FullName.StartsWith("So"));
var narrowlyFiltered = people.Where(person => person.Age > 36 && person.FullName.StartsWith("Some"));

有没有一种方法可以比较这两个表达式，并在运行时推断第二个表达式是第一个表达式的子集？不需要枚举或其他任何操作。我只有表达式，想要找出这些表达式是否相交或包含彼此。

- Emre Senturk

---

你是指结果，还是所有情况？ - Willem Van Onsem

是的，只要你不让表达式转化为委托就可以了。 - Alexei Levenkov

是的，有一种方法。但需要一些操作。您确定需要这样做吗？难道没有在表达式放置之前就处理它的方法吗？ - Travis J

@EmreSenturk：并不是普遍的情况。那个问题是不可判定的。 - Willem Van Onsem

var allFiltered = people.Where(person => person.Age > 28 && person.FullName.StartsWith("So")).Where(person => person.Age > 36 && person.FullName.StartsWith("Some")); 这段代码可以更加通用化，变为 var allFiltered = people.Where(filter).Where(secondFilter); 或者将两个过滤器的表达式树压缩成一个，变为 var allFiltered = people.Where(filter.And(secondFilter)); - Travis J

Answer 1

您需要将每个表达式分解为所有可能的继承类型（MethodCallExpression，ConditionalExpression等），然后并行地遍历每个分解并检查每个可能的参数...这将需要编写一些较长的代码... 您可以从ExpressionEqualityComparer中获取灵感。

- rducom

---

谢谢！我想要解释的内容很像这个。 - Emre Senturk

这很明显是一个递归的方式...例如，MethodCallExpression内部有一个Arguments列表，因此很明显，如果要比较整个表达式，您还必须比较子表达式... - rducom

@Sharped：从表达式内部调用循环开始，问题就开始出现了。这里所述的问题是Rice定理的一个很好的例子。 - Willem Van Onsem

person.Age => 在两种情况下都是MemberExpression，针对同一类型的同一属性。person.Age > 28和person.Age > 36都是BinaryExpression，具有相同的左操作数...等等...它们有很多共同点。 - rducom

所谓子集，是指在“几乎相等”的比较中，两个表达式树之间的公共节点的小部分（如果它们是相同类型的，但不具有完全相同的参数，则可以认为这两个节点是几乎相等的）。这与严格的B-Tree代数无关。有了这种“几乎相等”的概念，我们确实可以谈论交集。 - rducom

Answer 2

如果您可以枚举您的集合，您可以先将元素放入一个 HashSet<T> 中，然后在其上运行 HashSet<T>.IsSubSet 方法。

HashSet<T> hs = new HashSet<T>(filtered);
HashSet<T> hs2 = new HashSet<T>(narrowlyFiltered);
hs.IsSubSetOf(hs2); //<- booleans saying true or false

否则，这个问题在一般情况下是一个不可判定问题。虽然有一些启发式方法可以适用于许多情况。例如，您可以尝试使用代码合同，在编译时推断出这个问题。

证明：

给定两个图灵机（方法、委托、指针），第一个语言中包含的每个字符串是否都包含在第二个语言中？ 不可判定 证明：如果它是可判定的，那么EQ_TM就是可判定的：只需先验证第一个图灵机是否是第二个图灵机的子集，反之亦然。如果两者都是子集，我们就知道它们接受相同的字符串集。

换句话说，如果您能够做到这一点，您也可以推断出两个函数是否产生相同的结果，但这是无法实现的。

- Willem Van Onsem

---

不要说像“不可判定”这样的负面话 :) 无论如何，感谢您花时间解释为什么这是不可能的。 - Emre Senturk

@EmreSenturk：在关于可计算性的每本教科书中，都使用了“不可判定”的术语。不幸的是，它既不是“半可判定”的。 - Willem Van Onsem

Answer 3

一切都取决于你如何权衡什么是相等的，比较表达式时什么更重要等等。例如，如果您有完全不同的过滤器，则在实际执行查询之前，您将无法知道查询差异。

为了完全控制比较，请创建一个带有某些属性的过滤器类，这些属性可用于过滤，然后构建表达式并使用此类进行比较，而不是使用访问者。您可以为比较整数、整数对（用于范围）等准备常见函数。

我没有检查下面的代码，但它应该是一个很好的开始。

public class PersonFilter:  IComparable<PersonFilter>
{
    public int? MinAge { get; set; }

    public int? MaxAge { get; set; }

    public string NamePrefix { get; set; }

    public Expression<Predicate<Person>> Filter
    {
        return people => people.Where(person => (!MinAge.HasValue || person.Age > MinAge.Value) && 
            (!MaxAge.HasValue || person.Age < MaxAge.Value) && 
            (string.IsNullOrEmpty(NamePrefix) || person.FullName.StartsWith(NamePrefix))
    }

    // -1 if this filter is filtering more than the other
    public int CompareTo(PersonFilter other)
    {
        var balance = 0; // equal
        if(MinAge.HasValue != other.MinAge.HasValue)
        {
            balance += MinAge.HasValue ? -1 : 1;
        }
        else if(MinAge.HasValue)
        {
            balance += MinAge.Value.CompareTo(other.MinAge.Value) ?
        }
        if(string.IsNullOrEmpty(NamePrefix) != string.IsNullOrEmpty(other.NamePrefix))
        {
            balance += string.IsNullOrEmpty(NamePrefix) ? -1 : 1;
        }
        else if(!string.IsNullOrEmpty(NamePrefix))
        {
            if(NamePrefix.StartsWith(other.NamePrefix))
            {
                balance -= 1;
            }
            else if(other.NamePrefix.StartsWith(NamePrefix))
            {
                balance += 1;
            }
            else
            {
                // if NamePrefix is the same or completely different let's assume both filters are equal
            }
        }
        return balance;
    }

    public bool IsSubsetOf(PersonFilter other)
    {
        if(MinAge.HasValue != other.MinAge.HasValue)
        {
            if(other.MinAge.HasValue)
            {
                return false;
            }
        }
        else if(MinAge.HasValue && MinAge.Value < other.MinAge.Value)
        {
            return false;
        }

        if(string.IsNullOrEmpty(NamePrefix) != string.IsNullOrEmpty(other.NamePrefix))
        {
            if(!string.IsNullOrEmpty(other.NamePrefix))
            {
                return false;
            }
        }
        else if(!string.IsNullOrEmpty(NamePrefix))
        {
            if(!NamePrefix.StartsWith(other.NamePrefix))
            {
            return false;
            }
        }

        return true;
    }
}

- too

---

谢谢！我本来打算创建一个带有筛选条件的虚拟人员实例，并将其放入集合中并对其进行评估。但是您的建议似乎更加明确。 - Emre Senturk

在这种情况下，您肯定会得出足够的自定义比较结果。祝你好运 :) - too

@too：将其与平衡进行比较有些问题。你根本无法定义一个完整的顺序以使之合理。你应该定义一个偏序，其中你可以说它是相等的、大于、小于，或者你不能对它做出任何断言。 - Willem Van Onsem

@CommuSoft：我完全同意，但这种方法只能用于检查一个过滤器是否定义了另一个子集 - 只有这样才能保证给出确定性结果，并且添加一个专用的IsSubsetOf方法会更适合这种用例。 - too

我为MinAge和NamePrefix属性添加了IsSubsetOf示例实现。 - too

Answer 4

请查看规格设计模式。

一旦实现，您在此情况下的规格就会变成：

public class PersonNamedOlderThanSpecification : CompositeSpecification<Person>
{
    private string name;
    private int age;

    public PersonNamedOlderThanSpecification(string name, int age)
    {
        this.name = name;
        this.age = age;
    }


    public override bool IsSatisfiedBy(Person entity)
    {
        return (entity.Name.Contains(this.name)) && (entity.Age > age);
    }
}

然后你可以像这样使用它：

var personSpecs = new PersonNamedOlderThanSpecification("So", 28);
var personSpecs2 = new PersonNamedOlderThanSpecification("Some", 36);

var filtered = people.FindAll(x => personSpecs.IsSatisfiedBy(x));
var adjusted = people.FindAll(x => personSpecs2.IsSatisfiedBy(x));

- CheGueVerra

---

我认为这并没有真正回答问题。虽然您确实可以在规范中实现“IsSubSetOf”逻辑... - Willem Van Onsem

我在列表过滤中使用此模式，由于值是动态的，结果列表中的所有实体都符合规范。 - CheGueVerra

但是你说得对，我误解了问题，把重点放在了过滤部分。 - CheGueVerra

创建时没有考虑到这一点，我会尝试一下的，谢谢...很抱歉帖子没有解决你的问题...我会再读一遍问题，嗯... - CheGueVerra

@CheGueVerra 不用担心 :) 是我没有清楚地陈述问题的人。 - Emre Senturk

Answer 5

你可以尝试这个：

var people = new List<Person>
{
     new Person {FullName = "Some Dude", Age = 45},
     new Person {FullName = "Another Dude", Age = 28},
     new Person {FullName = "Some Other Dude", Age = 36}
};

var filtered = people.Where(person => person.Age > 28 && person.FullName.StartsWith("So"));
var narrowlyFiltered = people.Where(person => person.Age > 36 && person.FullName.StartsWith("Some"));

var intersection = filtered.Intersect(narrowlyFiltered);
if (intersection != null)
{
    if (intersection.Count() > 0)
    {
        //narrowlyFiltered is subset of filtered
    }
}

- Carlos Iván Montes Agüero

---

是的，但它确实对其进行枚举。 - Emre Senturk

好的，如果你只是想知道 narrowlyFiltered 是否是 filtered 的子集（true 或者 false），那么在这个帖子中，解释了解决方案；在你的情况下，你可以这样做：bool subset = filtered.Any(v => narrowlyFiltered.Any()); - Carlos Iván Montes Agüero