OrderBy与非传递IComparer

Question

拿一个自定义IComparer,如果它们的差异小于给定的epsilon,则将两个双精度视为相等.

如果在OrderBy().ThenBy()子句中使用此IComparer会发生什么？

具体来说,我在考虑以下实现:

public class EpsilonComparer : IComparer<double>
{
    private readonly double epsilon;

    public EpsilonComparer(double epsilon)
    {
        this.epsilon = epsilon;
    }

    public int Compare(double d1, double d2)
    {
        if (Math.Abs(d1-d2)<=epsilon) return 0;

        return d1.CompareTo(d2);
    }
}

现在这个IComparer关系显然不具有传递性.(if a ~ b and b ~ c then a ~ c)

使用epsilon == 0.6:

• 比较(1,1.5)== 0
• 比较(1.5%,2)== 0
  还
• 比较(1,2)== -1

如果在OrderBy查询中使用此IComparer会发生什么,如下所示:

List<Item> itemlist;
itemList = itemlist.OrderBy(item=>item.X, new EpsilonComparer(0.352))
                   .ThenBy (item=>item.Y, new EpsilonComparer(1.743)).ToList();

排序的行为是否符合预期,首先按X排序列表,然后按Y排序,同时将大致相等的值视为完全相等？
在某些情况下它会爆炸吗？
或者整个类型是不明确的？

使用IComparer没有传递性的后果究竟是什么？

(我知道这很可能是c#语言的未定义行为.我仍然对答案非常感兴趣.)

是否有另一种方法来获得这种排序行为？
(除了舍入值之外,当两个关闭的双打时会引入伪像,一个被向上舍入而另一个向下)

_{此处提供了此问题中代码的在线信息:}

Answer 1

在这里查看我的代码片段。它只是用于第一级排序而不是优化。

OrderBy 和 ThenBy 使用通用算法。您需要使用像我这样的特殊算法重新实现 OrderBy 和 ThenBy 。那么它就可以作为OrderBy().ThenBy().

算法细节：

在 EpsilonComparer 下的排序序列（x1 x2 x3...）中，如果 x4>x1，则 x5>x1。如果 x4=x1，则 x3=x1，并且 x5>x1 或 x5=x1。

使用 epsilon(0.4)，输入以下数字：0.1, 0.6, 1, 1.1, 1.6, 2, 2, 2.6, 3, 3.1, 3.6, 4, 4.1, 4.6, 5, 5.1, 5.6, 6, 6.1, 6.6

结果：0.1 0.6 1 1.1 (1.6 2 2 ) 2.6 3 3.1 3.6 4 4.1 4.6 (5 5.1 ) 5.6 (6 6.1 ) 6.6

(a,b,c)表示这些数字相等，并且数字的顺序不固定。它们可以是 (a,b,c)、(c,a,b) 和任何其他顺序。

ab表示 a < b 并且顺序是固定的。

using System;
using System.Collections.Generic;
using System.Linq;

namespace Rextester
{
    class Program
    {
        public static void Main(string[] args)
        {
            new EpsilonSort(new EpsilonComparer(0.4), 0.1, 0.6, 1, 1.1, 1.6, 2, 2, 2.6, 3, 3.1, 3.6, 4, 4.1, 4.6, 5, 5.1, 5.6, 6, 6.1, 6.6).Sort();
        }
    }

    public class EpsilonSort
    {
        private readonly IComparer<double> m_comparer;
        private readonly double[] m_nums;
        public EpsilonSort(IComparer<double> comparer, params double[] nums)
        {
            this.m_comparer = comparer;
            this.m_nums = nums;
        }

        public void Sort()
        {
            Node root = new Node();
            root.Datas = new List<double>(this.m_nums);

            foreach (double i in (double[])this.m_nums.Clone())
            {
                this.ProcessNode(i, root);
            }

            this.OutputNodes(root);
        }

        private void OutputNodes(Node root)
        {
            if (root.Datas == null)
            {
                foreach (var i in root.Nodes)
                {
                    this.OutputNodes(i);
                }
            }
            else
            {
                if (root.Datas.Count == 1)
                {
                    Console.WriteLine(root.Datas[0]);
                }
                else
                {
                    Console.Write('(');
                    foreach (var i in root.Datas)
                    {
                        Console.Write(i);
                        Console.Write(' ');
                    }
                    Console.WriteLine(')');
                }
            }
        }

        private void ProcessNode(double value, Node one)
        {
            if (one.Datas == null)
            {
                foreach (var i in one.Nodes)
                {
                    this.ProcessNode(value, i);
                }
            }
            else
            {
                Node[] childrennodes = new Node[3];
                foreach (var i in one.Datas)
                {
                    int direction = this.m_comparer.Compare(i, value);
                    if (direction == 0)
                    {
                        this.AddData(ref childrennodes[1], i);
                    }
                    else
                    {
                        if (direction < 0)
                        {
                            this.AddData(ref childrennodes[0], i);
                        }
                        else
                        {
                            this.AddData(ref childrennodes[2], i);
                        }
                    }
                }
                childrennodes = childrennodes.Where(x => x != null).ToArray();
                if (childrennodes.Length >= 2)
                {
                    one.Datas = null;
                    one.Nodes = childrennodes;
                }
            }
        }

        private void AddData(ref Node node, double value)
        {
            node = node ?? new Node();
            node.Datas = node.Datas ?? new List<double>();
            node.Datas.Add(value);
        }

        private class Node
        {
            public Node[] Nodes;
            public List<double> Datas;
        }
    }

    public class EpsilonComparer : IComparer<double>
    {
        private readonly double epsilon;

        public EpsilonComparer(double epsilon)
        {
            this.epsilon = epsilon;
        }

        public int Compare(double d1, double d2)
        {
            if (Math.Abs(d1 - d2) <= epsilon) return 0;

            return d1.CompareTo(d2);
        }
    }
}