C#: 通用数学函数（Min、Max等）

Question

C#: 通用数学函数（Min、Max等）

17

我在考虑编写一些通用的函数来执行基本的数学运算，比如最小值、最大值等。但是我不知道如何比较两种通用类型：

public T Max<T>(T v1, T v2) where T: struct
{
   return (v1 > v2 ? v1 : v2);
}

这个怎么样？

谢谢。

- Feryt

2

为什么将Max限制在结构体上？它同样适用于类，例如字符串。 - Will

2

通常适用于实现 IComparable 接口的任何内容。 - Joey

你说得对，我不知道IComparable接口。谢谢。 - Feryt

1

请注意：由于存在IComparable接口，您可以对涉及比较的任何内容进行此操作，但是其他数学函数可能无法实现，因为没有INumeric接口或等效接口。 - jk.

@jk - 不是不可能，只是有点棘手；请参见Luke答案中的MiscUtil链接，以获取支持运算符（而不是IComparable[<T>]）的代码。 - Marc Gravell

new[] {v1, v2}.Max()怎么样？ - Can Bud

8个回答

26

如果您只想创建比较函数，那么可以使用类型 T 的默认比较器。例如：

public static T Max<T>(T x, T y)
{
    return (Comparer<T>.Default.Compare(x, y) > 0) ? x : y;
}

如果T实现了IComparable<T>接口，则会使用该比较器；如果T没有实现IComparable<T>但实现了IComparable接口，则会使用该比较器；如果T既没有实现IComparable<T>也没有实现IComparable接口，则会抛出运行时异常。

如果您想要/需要做更多的事情而不仅仅是比较项，则可以查看MiscUtil中的通用运算符实现和相关文章。

- LukeH

这是非常优雅和通用的解决方案。我也很喜欢它。 - Feryt

4

在我看来，这是正确的答案。另外，另一种常见的替代模式是有两个重载；其中一个将Comparer<T>.Default传递给第二个，它接受IComparer<T>（用于那些想要自定义比较器的情况）。但对于简单的情况，这就是正确的方式。 - Marc Gravell

我不同意，请看下面我的帖子。 - Fernando Pelliccioni

1

这确实是最好的解决方案。与它相关的运行时成本几乎可以忽略不计（并且仅在为类型创建默认比较器的第一次支付）。Default.Comparer也更加智能，可以更好地处理角落情况，而不是使用IComparable或IComparable<T>。不错的解决方案。这确实几乎完全是我做的方式。我只是使用>= 0，以便在排序顺序相等的情况下返回第一个“操作数”... - Loudenvier

如果添加约束T：IComparable <T>，则代码可以简化为return（x.CompareTo（y）> 0）...。更易于阅读。并且没有运行时评估或异常风险，因为您已将T限制为可比较的类型。 - ToolmakerSteve

5

让我反对一下，@LukeH的实现不是通用的。

我将解释为什么它不是通用的： Comparer<T>.Default 需要在运行时检查 T 是否实现了 IComparable<T>、IComparable 或两者都没有。虽然这种行为在http://msdn.microsoft.com/en-us/library/azhsac5f.aspx中没有得到很好的记录，但我们可以推断出来，因为当 T 既没有实现>也没有实现时，Comparer<T>.Default会抛出一个异常。如果在编译时进行检查，就不需要异常（运行时），只需使用编译时错误即可。

因此，由于Comparer<T>.Default使用了反射，这意味着运行时成本很高，那么...它不是通用的...为什么？

因为泛型编程的含义是： 一个单一的算法（通用）可以覆盖许多实现（适用于许多类型），并保持手写版本的效率。 举个例子。整数的手写版本将是：

public static int Max( int x, int y)
{
    return (x.CompareTo(y) > 0) ? x : y;
}

很简单，只涉及比较（或者可能有更多，这取决于Int32.CompareTo()的实现方式）。如果我们使用@LukeH的实现，我们会在非常简单的事情上添加反射。

简言之：

1.始终优先选择编译时错误而不是运行时异常（这不是Javascript、Ruby等语言）； 2.与手写版本相比，此实现效率较低（对于任何类型）。

另一方面，当x和y相同时，你认为Max应该返回什么？

我开始分析真正的泛型实现...

理想的实现方式应该是...

    public static T Max<T>(T x, T y, Func<T, T, int> cmp)
    {
        return (cmp(x, y) > 0) ? x : y;
    }

    //Pseudo-code ( note the 'or' next to 'where' )
    public static T Max<T>(T x, T y) where T: IComparable<T> or IComparable
    {
        return Max(x, y, (a, b) => { return a.CompareTo(b); });
    }

这在C#中是不可能的，下一步可以尝试...

    //pseudo-code
    public static T Max<T>(T x, T y, Func<T, T, int> cmp)
    {
        return (cmp(x, y) > 0) ? x : y;
    }

    public static T Max<T>(T x, T y) where T: IComparable<T>
    {
        return Max(x, y, (a, b) => { return a.CompareTo(b); });
    }

    public static T Max<T>(T x, T y) where T: IComparable
    {
        return Max(x, y, (a, b) => { return a.CompareTo(b); });
    }

但是，这是不可能的，因为重载决议不会考虑泛型约束。

那么，我会有意地省略IComparable。我只会关注IComparable 。

    public static T Max<T>(T x, T y, Func<T, T, int> cmp)
    {
        return (cmp(x, y) > 0) ? x : y;
    }

    public static T Max<T>(T x, T y) where T: IComparable<T>
    {
        return Max(x, y, (a, b) => { return a.CompareTo(b); });
    }

- Fernando Pelliccioni

2

关于缺乏编译时类型安全的观点很有道理。但是，如果你要声称运行时成本高，我真的很想看到你用一些数字来支持它。我也没有测试过，但我认为传递函数也会导致一些性能损失。 - Carl Walsh

1

我的观点不是关于类型安全，而是关于泛型编程。Comparer<T>.Default使用反射。众所周知，反射在运行时具有很高的成本，我认为这里不需要证明它。特别是如果我们将反射与可以在编译时解决的东西进行比较，性能差异非常大。无论如何，几天后，我会发布一些数字更新。 - Fernando Pelliccioni

关于将函数作为参数传递，首先，接收CMP作为参数的函数需要使用等价关系比较一对元素。第二个函数使用相等性比较两个元素。其次，关于将函数作为参数传递的惩罚，任何合理的编译器都可以对CMP进行内联，因此最终代码与手动编写A.CompareTo(b)的代码相同。 - Fernando Pelliccioni

4

@FernandoPelliccioni 您的说法不是完全正确的。您应该看一下DefaultComparer的源代码。它非常聪明！它会在Comparer<T>的静态易失性变量中缓存默认比较器。因此，你只需要付出一次代价，之后它将比（或与）类型转换到IComparable<T>一样快。使用DefaultComparer将使函数比“更学术”的Comparable<T>解决方案更“通用”。而且，您不应该担心运行时异常。编译时检查不能替代单元测试。对您的代码进行单元测试并使用最佳解决方案。 - Loudenvier

3

虽然有点晚，但为什么不使用动态类型和委托作为IComparable的替代方案呢？这样，在大多数情况下，您可以获得编译时类型安全，并且只有在提供的类型都不支持运算符“<”并且未提供默认比较器作为参数时才会出现运行时错误。

public static T Max<T>(T first, T second, Func<T,T,bool> f = null)
{
    Func<dynamic,dynamic,bool> is_left_smaller = (x, y) => x < y ? true : false;

    var compare = f ?? new Func<T, T, bool>((x, y) => is_left_smaller(x, y));

    return compare(first, second) ? second : first; 
}

- Anton

1

.NET 7引入了一个新功能——通用数学（在这里和这里阅读更多信息），它基于static abstract接口方法的加法。该功能引入了许多接口，允许对数字类型和/或数学运算进行通用抽象化，从而使得可以将相关函数重写为：

public T Max<T>(T v1, T v2) where T: IComparisonOperators<T, T, bool> => v1 > v2 ? v1 : v2;

请注意，对于内置数字类型，通常您不需要定义自己的Max，因为它已经在INumber<T>接口中定义了：

public interface INumber<TSelf> : 
// ... other interfaces,
System.Numerics.IComparisonOperators<TSelf,TSelf,bool>
// ... other interfaces
 where TSelf : INumber<TSelf>

- Guru Stron

1

我在这个答案中提出的解决方案曾经可行（我实际上做了类似的事情），在问题被提出时。我很惊讶没有答案提出这种替代方案，因此我会提出它。

Linq.Expressions 可以（当时也可以）使用（它于2007年添加到.NET 3.5中，因此在问题提出时是一个有效的答案）。

首先：

using System.Linq.Expressions;

// ...

public T Max<T>(T v1, T v2)
{
    var expression = Expression.GreaterThan
        (
            Expression.Constant(v1),
            Expression.Constant(v2)
        );
    return Expression.Lambda<Func<bool>>(expression).Compile()() ? v1 : v2);
}

这不需要使用dynamic或Comparison<T>/IComparer<T>。

我认为指定自定义比较的方法更好，但这不是我们在这里做的。当然，任何适用于所提供解决方案的类型，Comparer<T>.Default都可以工作。然而，使用Linq.Expressions可以让你实现任何算术操作。将其视为该方法的示例。

当然，这会增加一些开销。让我们制定一个编译成带参数函数的版本，稍后再考虑如何缓存它：

using System.Linq.Expressions;

// ...

public T Max<T>(T v1, T v2)
{
    var a = Expression.Parameter(typeof(int), "a");
    var b = Expression.Parameter(typeof(int), "b");
    var lambda = Expression.Lambda<Func<T, T, bool>>
    (
        Expression.GreaterThan(a, b),
        new[]{a, b}
    );
    return ((Func<T, T, bool>)lambda.Compile())(v1, v2) ? v1 : v2;
}

好的，为了缓存它，让我们从通用类方法开始，这更容易编写：

using System.Linq.Expressions;

class GenericMath<T>
{
    private static Func<T, T, bool>? _greaterThan;
    
    public static Func<T, T, bool> GetGreaterThan()
    {
        if (_greaterThan == null)
        {
            var a = Expression.Parameter(typeof(int), "a");
            var b = Expression.Parameter(typeof(int), "b");
            var lambda = Expression.Lambda<Func<T, T, bool>>
            (
                Expression.GreaterThan(a, b),
                new[]{a, b}
            );
            _greaterThan = (Func<T, T, bool>)lambda.Compile();
        }
        
        return _greaterThan;
    }

    public static T Max(T v1, T v2)
    {
        return GetGreaterThan()(v1, v2) ? v1 : v2;
    }
}

当然，使用泛型的静态方法存在一些缺点（会有性能成本，而且内存永远不会被释放）。我们可以通过使用字典缓存来开始寻找更好的解决方案：

using System.Linq.Expressions;

class GenericMath
{
    private readonly static Dictionary<Type, Delegate> _gtCache = new Dictionary<Type, Delegate>();
    
    public static Func<T, T, bool> GetGreaterThan<T>()
    {
        if (!_gtCache.TryGetValue(typeof(T), out var @delegate) || @delegate == null)
        {
            var a = Expression.Parameter(typeof(int), "a");
            var b = Expression.Parameter(typeof(int), "b");
            var lambda = Expression.Lambda<Func<T, T, bool>> 
            (
                Expression.GreaterThan(a, b),
                new[]{a, b}
            );
            @delegate = lambda.Compile();
            _addCache[typeof(T)] = @delegate;
        }
        
        return (Func<T, T, bool>)@delegate;
    }

    public static T Max<T>(T v1, T v2)
    {
        return GetGreaterThan<T>()(v1, v2) ? v1 : v2;
    }
}

好的，我听到你了，我引入了一个新的问题：该解决方案不是线程安全的。

我们可以使用ConcurrentDictionary（在.NET 4.0中添加，如果我没有记错的话，在提问时还处于测试版），但我们仍然不会释放内存。相反，我们可以为此使用自定义类：

public sealed class TypeCacheDict<TValue>
{
    private const int Capacity = 256;
    private readonly Entry[] _entries;

    public TypeCacheDict()
    {
        _entries = new Entry[Capacity];
    }

    public TValue this[Type key]
    {
        get
        {
            if (TryGetValue(key, out var value))
            {
                return value;
            }

            throw new KeyNotFoundException();
        }
        set => Add(key, value);
    }

    public void Add(Type key, TValue value)
    {
        if (key == null)
        {
            throw new ArgumentNullException(nameof(key));
        }

        var hash = key.GetHashCode();
        var index = hash & (_entries.Length - 1);
        var entry = _entries[index];
        Thread.MemoryBarrier();
        if (entry?.Hash != hash || !entry.Key.Equals(key))
        {
            Interlocked.Exchange(ref _entries[index], new Entry(hash, key, value));
        }
    }

    public bool TryGetValue(Type key, out TValue value)
    {
        if (key == null)
        {
            throw new ArgumentNullException(nameof(key));
        }

        var hash = key.GetHashCode();
        var index = hash & (_entries.Length - 1);
        var entry = _entries[index];
        Thread.MemoryBarrier();
        if (entry?.Hash == hash && entry.Key.Equals(key))
        {
            value = entry.Value;
            return value != null;
        }

        value = default;
        return false;
    }

    private sealed class Entry
    {
        internal readonly int Hash;
        internal readonly Type Key;
        internal readonly TValue Value;

        internal Entry(int hash, Type key, TValue value)
        {
            Hash = hash;
            Key = key;
            Value = value;
        }
    }
}

这个 TypeCacheDict 是线程安全的。首先，Entry 是不可变的，我们不需要担心对它的共享访问。此外，它是一个引用类型，因此替换它是原子操作。我们使用 Thread.MemoryBarrier 和 Interlocked.Exchange 来模仿 Volatile.Read 和 Volatile.Write，因为 Volatile 不可用（而 Thread.Volatile* 缺乏泛型重载，我不想引入额外的转换）。

有了这个新类型，我们现在可以写：

private readonly static TypeCacheDict<Delegate> _gtCache = new TypeCacheDict<Delegate>();

其余代码可以不变。虽然还有改进的空间：TryGetOrAdd:

    public TValue TryGetOrAdd(Type key, Func<TValue> valueFactory)
    {
        if (key == null)
        {
            throw new ArgumentNullException(nameof(key));
        }
        
        if (valueFactory == null)
        {
            throw new ArgumentNullException(nameof(valueFactory));
        }

        var hash = key.GetHashCode();
        var index = hash & (_entries.Length - 1);
        var entry = _entries[index];
        Thread.MemoryBarrier();
        if (entry?.Hash == hash && entry.Key.Equals(key))
        {
            return entry.Value;
        }
        
        var value = valueFactory();
        Interlocked.Exchange(ref _entries[index], new Entry(hash, key, value));
        return value;
    }

这使我们能够编写以下内容：

    public static Func<T, T, bool> GetGreaterThan<T>()
    {
        return (Func<T, T, bool>)_gtCache.TryGetOrAdd
        (
            typeof(T),
            ()=>
            {
                var a = Expression.Parameter(typeof(int), "a");
                var b = Expression.Parameter(typeof(int), "b");
                var lambda = Expression.Lambda<Func<T, T, bool>>(Expression.GreaterThan(a, b), new[]{a, b});
                return lambda.Compile();
            }
        );
    }

当然，这是使用它的方式：

Console.WriteLine(GenericMath.Max<int>(90, 100)); // 100

为了展示这种方法的强大之处，这里是Add：

    private readonly static TypeCacheDict<Delegate> _addCache = new TypeCacheDict<Delegate>();
    
    public static Func<T, T, T> GetAdd<T>()
    {
        return (Func<T, T, T>)_addCache.TryGetOrAdd
        (
            typeof(T),
            ()=>
            {
                var a = Expression.Parameter(typeof(int), "a");
                var b = Expression.Parameter(typeof(int), "b");
                var lambda = Expression.Lambda<Func<T, T, T>>(Expression.Add(a,b), new[]{a, b});
                return lambda.Compile();
            }
        );
    }

    public static T Add<T>(T v1, T v2)
    {
        return GetAdd<T>()(v1, v2);
    }

这是使用它的方法：

Console.WriteLine(GenericMath.Add<int>(90, 100)); // 190

- Theraot

0

从记忆中来看，T 还需要是 IComparable（将其添加到 where 中），然后您可以使用 v1.CompareTo(v2) > 0 等等。

- Will

0

死灵法术。您可以在任意数量的参数上使用最大/最小函数：

public static T Min<T>(params T[] source) 
    where T: struct, IComparable<T>
{
    if (source == null) 
        throw new System.ArgumentNullException("source");

    T value = default(T);
    bool hasValue = false;
    foreach (T x in source)
    {
        if (hasValue)
        {
            // if (x < value) // https://learn.microsoft.com/en-us/dotnet/api/system.icomparable-1?view=netcore-3.1
            // Less than zero This object precedes the object specified by the CompareTo method in the sort order.
            // Zero This current instance occurs in the same position in the sort order as the object specified by the CompareTo method argument.
            // Greater than zero
            if (x.CompareTo(value) < 0)
                value = x;
        }
        else
        {
            value = x;
            hasValue = true;
        }
    }

    if (hasValue) 
        return value;

    throw new System.InvalidOperationException("Sequence contains no elements");
}


public static T Max<T>(params T[] source) 
    where T : struct, IComparable<T>
{
    if (source == null) 
        throw new System.ArgumentNullException("source");

    T value = default(T);
    bool hasValue = false;
    foreach (T x in source)
    {
        if (hasValue)
        {
            // if (x > value) // https://learn.microsoft.com/en-us/dotnet/api/system.icomparable-1?view=netcore-3.1
            // Less than zero This object precedes the object specified by the CompareTo method in the sort order.
            // Zero This current instance occurs in the same position in the sort order as the object specified by the CompareTo method argument.
            // Greater than zero
            if (x.CompareTo(value) > 0)
                value = x;
        }
        else
        {
            value = x;
            hasValue = true;
        }
    }

    if (hasValue) 
        return value;

    throw new System.InvalidOperationException("Sequence contains no elements");
}

- Stefan Steiger

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joey · Accepted Answer

您可能希望限制泛型类型实现IComparable：

public T Max<T>(T v1, T v2) where T: struct, IComparable<T>

然后使用CompareTo方法：

{
    return (v1.CompareTo(v2) > 0 ? v1 : v2);
}