如何使用公差因子的数值对GroupBy对象进行分组？

Question

我有一个C#对象列表,其中包含以下简化数据:

ID, Price
2, 80.0
8, 44.25
14, 43.5
30, 79.98
54, 44.24
74, 80.01

我正在尝试GroupBy最小的数字,同时考虑容差因子.例如,在容差= 0.02的情况下,我的预期结果应该是:

44.24 -> 8, 54
43.5 -> 14
79.98 -> 2, 30, 74

如何在实现大型数据集的良好性能的同时做到这一点？在这种情况下,LINQ是否可行？

Answer 1

在我看来，如果您有一个大型数据集，您将希望避免对值进行排序然后在迭代排序列表时收集它们的直接解决方案，因为对大型集合进行排序可能会很昂贵。我能想到的不进行任何显式排序的最有效的解决方案是构建一棵树，其中每个节点包含键落在“连续”范围内的项目（其中所有键都在tolerance彼此之内） -每次添加超出范围小于 的项目时，每个节点的范围都会扩展tolerance。我实现了一个解决方案 - 结果比我预期的更复杂和有趣 - 并且根据我的粗略基准测试，这样做似乎需要比直接解决方案大约一半的时间。

这是我作为扩展方法的实现（因此您可以链接它，尽管像普通方法一样，一旦迭代结果，Group它就会完全迭代）。sourceIEnumerable

public static IEnumerable<IGrouping<double, TValue>> GroupWithTolerance<TValue>(
    this IEnumerable<TValue> source,
    double tolerance, 
    Func<TValue, double> keySelector) 
{
    if(source == null)
        throw new ArgumentNullException("source");
        
    return GroupWithToleranceHelper<TValue>.Group(source, tolerance, keySelector);
}

private static class GroupWithToleranceHelper<TValue>
{
    public static IEnumerable<IGrouping<double, TValue>> Group(
        IEnumerable<TValue> source,
        double tolerance, 
        Func<TValue, double> keySelector)
    {
        Node root = null, current = null;
        foreach (var item in source)
        {
            var key = keySelector(item);
            if(root == null) root = new Node(key);
            current = root;
            while(true){
                if(key < current.Min - tolerance) { current = (current.Left ?? (current.Left = new Node(key))); }
                else if(key > current.Max + tolerance) {current = (current.Right ?? (current.Right = new Node(key)));}
                else 
                {
                    current.Values.Add(item);
                    if(current.Max < key){
                        current.Max = key;
                        current.Redistribute(tolerance);
                    }
                    if(current.Min > key) {
                        current.Min = key;
                        current.Redistribute(tolerance);
                    }       
                    break;
                }   
            }
        }

        if (root != null)
        {
            foreach (var entry in InOrder(root))
            {
                yield return entry;
            }
        }
        else
        {
            //Return an empty collection
            yield break;
        }
    }
    
    
    private static IEnumerable<IGrouping<double, TValue>> InOrder(Node node)
    {
        if(node.Left != null)
            foreach (var element in InOrder(node.Left))
                yield return element;
        
        yield return node;
        
        if(node.Right != null)
            foreach (var element in InOrder(node.Right))
                yield return element;       
    }   
    
    private class Node : IGrouping<double, TValue>
    {
        public double Min;
        public double Max;
        public readonly List<TValue> Values = new List<TValue>();       
        public Node Left;
        public Node Right;
        
        public Node(double key) {
            Min = key;
            Max = key;
        }   
        
        public double Key { get { return Min; } }
        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }     
        public IEnumerator<TValue> GetEnumerator() { return Values.GetEnumerator(); }   
        
        public IEnumerable<TValue> GetLeftValues(){
            return Left == null ? Values : Values.Concat(Left.GetLeftValues());
        }
        
        public IEnumerable<TValue> GetRightValues(){
            return Right == null ? Values : Values.Concat(Right.GetRightValues());
        }
        
        public void Redistribute(double tolerance)
        {
            if(this.Left != null) {
                this.Left.Redistribute(tolerance);
                if(this.Left.Max + tolerance > this.Min){
                    this.Values.AddRange(this.Left.GetRightValues());
                    this.Min = this.Left.Min;
                    this.Left = this.Left.Left;
                }
            }
            
            if(this.Right != null) {
                this.Right.Redistribute(tolerance);
                if(this.Right.Min - tolerance < this.Max){
                    this.Values.AddRange(this.Right.GetLeftValues());
                    this.Max = this.Right.Max;
                    this.Right = this.Right.Right;
                }
            }
        }
    }
}

double如果需要，您可以切换到另一种类型（我真希望 C# 有一个numeric通用约束）。

Answer 2

最直接的方法是设计自己的IEqualityComparer<double>.

    public class ToleranceEqualityComparer : IEqualityComparer<double>
    {
        public double Tolerance { get; set; } = 0.02;
        public bool Equals(double x, double y)
        {
            return x - Tolerance <= y && x + Tolerance > y;
        }

        //This is to force the use of Equals methods.
        public int GetHashCode(double obj) => 1;
    }

你应该像这样使用

 var dataByPrice = data.GroupBy(d => d.Price, new ToleranceEqualityComparer());