排序整数对

Question

我有一个包含约 100k 个整数对的列表，如下所示：

0, 12
0, 14
0, 1
0, 8
0, 2
0, 4
0, 3
1, 5
1, 11
1, 8
1, 2
2, 7
2, 9
2, 4
2, 5
2, 13
3, 12
3, 10
3, 4
3, 6
...

我需要像这样对它们进行排序

0, 1
0, 2
0, 3
0, 4
0, 8
0, 12
0, 14
1, 2
1, 5
1, 8
1, 11
2, 4
2, 5
2, 7
2, 9
2, 13
3, 4
3, 6
...

目前我在做：

myList.Sort(comparer);

当比较器定义为：

class EdgeIntersectComparer : IComparer<EdgeIntersect>
{
   public int Compare(EdgeIntersect l1, EdgeIntersect l2)
   {
       if (l1.V1 < l2.V1)
          return -1;
       if (l1.V1 > l2.V1)
          return 1;

       if (l1.V2 < l2.V2)
          return -1;
       if (l1.V2 > l2.V2)
          return 1;

       return 0;
   }
}

我可以做些什么来提高执行速度？有没有更聪明的方法来解决这个问题？

谢谢。

编辑：

已测试 myList.OrderBy(e => e.V1).ThenBy(e => e.V2) 速度较慢。

Answer 1

您在已删除的 post 中评论说 V1 已经排序。

In addition by V1 the list is already sorted.

我使用 V1 已经订购的数据进行了测试，但 V2 使用随机数初始化。我发现这比你的方法更快：

myList = myList.GroupBy(x => x.V1).SelectMany(x => x.OrderBy(y => y.V2)).ToList();

如果 V1 已经排序，此仅有效。

Answer 2

作为一个可能的选择，您可以尝试使用数组而不是列表。（这取决于您的上下文）。如果你不能：

假设：

 public class Pair
{
    public int First { get; private set; }
    public int Second { get; private set; }
    public Pair(int first, int second)
    {
        this.First = first;
        this.Second = second;
    }
}

List 是如何按第一项排序的，也许是这样的？不确定这是否会更快：

    public static List<Pair> FullOrderedList(List<Pair> SemiOrderedList)
    {
        List<Pair> FList = new List<Pair>();
        List<Pair> demi = new List<Pair>();
        int MaxNumber = SemiOrderedList.Count;
        int compared = 0;
        for (int i = 0; i < MaxNumber; i++)
        {
            int first = SemiOrderedList[i].First;
            if (compared == first)
            {
                demi.Add(SemiOrderedList[i]);
            }
            else
            {
                compared++;
                FList.AddRange(demi.OrderBy(x => x.Second));
                demi.Clear();
            }
        }
        return FList;
    }

Answer 3

通过优化您的比较器可以获得小幅速度提升：

if (l1.V1 == l2.V1)
{
   if (l1.V2 > l2.V2) return 1;
   else return -1;
}
else if (l1.V1 < l2.V1)
          return -1;
else return 1;

最多检查 2 个语句，而不是你的 4 个。

排序整数对

Sorting pair of integers

.net

c#

sorting

graphics

quicksort