c# - 如何通过具有容差因子的数值对对象进行 GroupBy？

Question

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

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

我试图在考虑公差因素的同时对最低数字进行分组。 例如，在公差 = 0.02 的情况下，我的预期结果应该是:

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

我怎样才能在为大型数据集实现良好性能的同时做到这一点？ LINQ 是这种情况下的方法吗？

Answer 1

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

这是我作为扩展方法的实现(所以你可以链接它，尽管像普通的 Group 方法一样，它会在结果 时完全迭代 source code>IEnumerable 被迭代)。

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 泛型约束)。