使用非传递性IComparer的OrderBy

10

使用自定义的IComparer,如果两个double类型的数字之间的差小于给定的epsilon,则将它们视为相等。

如果将这个IComparer用在OrderBy().ThenBy()子句中会发生什么?

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

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的关系显然不是传递的。(如果a ~ b 且 b ~ c,则a ~ c

当epsilon== 0.6时:

  • Compare(1, 1.5) == 0
  • Compare(1.5, 2) == 0
    但是
  • Compare(1, 2 ) == -1

如果将此IComparer用于OrderBy查询,会发生什么情况:

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会有什么后果?

还有其他方法可以获得这种排序行为吗?(除了四舍五入值,这会在两个接近的双精度数中引入人为误差)

此问题的在线代码示例可在此处找到:


1
可能是C# IComparer<T>标准用法问题的重复。 - kevingessner
1
尝试使用Items { 0.3, 1.5 }, { 0.6, 4.5 }, { 0.9, 3 },看看你会得到什么。 - ohmusama
1
@kevingessner 我看到了那个问题,但我不认为这是一个重复的问题。我特别想知道使用非传递性 IComparer 的后果是什么。 - HugoRune
1
@ohmusama 输出为(0.3, 1.5) (0.6, 4.5) (0.9, 3),这是我所期望的,但这并不能说明一般情况。 (代码可在此处在线测试:http://rextester.com/ZKGV94991) - HugoRune
2
后果是针对可能相同的数据,排序顺序是不确定的。此外,非传递比较器有可能在某些使用中导致无限循环。 - Joe
显示剩余3条评论
2个回答

2
问题在于第一级排序(按 X 排序)可能已经导致不同的顺序。想象一下,所有项目都在彼此的 epsilon 范围内。然后,所有排序顺序都符合您的比较器,因为它总是返回 0。排序算法可以翻转硬币并仍然提供“正确”的答案。没有用。

如果第一级是任意排序的,则无法指望第二级排序起作用。

当然,所有这些讨论都是无意义的,因为您正在违反排序 API 的前提条件。即使它偶尔能够工作,您也不能确定它会在 a) 所有数据上 b) 在所有未来的 .NET 版本上工作。

那么你如何实现你的目标呢?你的问题只是定义不清,因为有很多解决方案可行。我知道你想要实现什么,但是根据你当前的问题定义,这是不可能的。

我建议这样做:按 X 对所有项目进行排序(不使用 epsilon)。然后,从左到右遍历排序后的项目,并将项目合并成最多一个 epsilon 宽度的组。这给你了一组项目,其中 X 值最多相差 epsilon。

然后,您可以使用组号作为第一级排序。它只是一个简单的整数,因此在其上进行排序不会有麻烦。对于 Y 字段,您可以使用没有 epsilon 的普通比较器(或重复相同的技巧)。


我认为你的遍历不正确。以 epsilon 0.4 的方式说出 "1, 1.4, 1.6"。根据你的算法,结果是 "(1,1.4), 1.6",这表明了两个数字顺序:"1, 1.4, 1.6" 和 "1.4, 1, 1.6"。显然第二个是错误的。唯一的顺序是 "1, 1.4, 1.6"。 - Vince
@Vince,为什么“1.4, 1, 1.6”可能是根据这个算法得出的结果顺序?您可以按X值对单个组内的项目进行排序,以定义顺序并消除任何歧义。 - usr
分组是一个抽象的概念。例如,通常对数字“2,1”进行排序,那么它就有了唯一的顺序“1,2”。现在问题有一个特殊要求(epsilon)。使用epsilon 3对数字“1,2,3”进行排序,那么任何顺序(1,2,3或3,2,1)都可以。没有分组的概念。 - Vince
@Vince,我介绍了这个概念,并且现在它已经存在了。首先你说这个算法是错的,因为它产生了错误排序的输出结果。然后我修复了它,你又说任何顺序都可以。我不明白有什么问题。你可以按照任何方式来做,这只是一个不重要的细节。你能给我展示一个具体的输入,这个算法不能正确排序吗?我已经处理了你提供的所有输入。 - usr
1
"first(1),second(1)" 带有 epsilon(0),它有两个顺序 "first(1),second(1)" 和 "second(1),first(1)"。在删除前缀(frist 和 second)后,它具有唯一的顺序 "1,1"(实际上有两个顺序)。现在,"1,2,3" 带有 epsilon(1)。数字没有高低之分,排序只是一个方向(从小到大或从大到小)。根据您的算法,它将变成 "(1,2),3",看起来 2 比 3 更接近 1。这太不公平了。 - Vince

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)和任何其他顺序。

a b 表示 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);
        }
    }
}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接