如何在 C# 中对连续 GUID 进行排序？

Question

如何在 C# 中对连续 GUID 进行排序？

9

顺序GUID是唯一的，但是会按照一定的顺序创建；这种顺序略微不同于使用标准.NET GUID比较器时所得到的顺序。

我正在寻找一个能够按照顺序GUID规则排序的C# GUID比较器。

== 更新 ==

我特别指的是由SQL Server中的NewSequentialId()创建的顺序GUID，尽管我现在意识到，当我写这个问题时，标准Win32 API调用UuidCreateSequential()使用的方案与SQL Server不同（我认为它们是相同的）。

== 更新2 ==

petelids 给出了下面的答案，例如使用List<System.Data.SqlGuid>.Sort()将按照以下顺序排列（使用具有每4位位置的1的初始GUID列表）...

01000000-0000-0000-0000-000000000000
10000000-0000-0000-0000-000000000000
00010000-0000-0000-0000-000000000000
00100000-0000-0000-0000-000000000000
00000100-0000-0000-0000-000000000000
00001000-0000-0000-0000-000000000000
00000001-0000-0000-0000-000000000000
00000010-0000-0000-0000-000000000000
00000000-0100-0000-0000-000000000000
00000000-1000-0000-0000-000000000000
00000000-0001-0000-0000-000000000000
00000000-0010-0000-0000-000000000000
00000000-0000-0100-0000-000000000000
00000000-0000-1000-0000-000000000000
00000000-0000-0001-0000-000000000000
00000000-0000-0010-0000-000000000000
00000000-0000-0000-0001-000000000000
00000000-0000-0000-0010-000000000000
00000000-0000-0000-0100-000000000000
00000000-0000-0000-1000-000000000000
00000000-0000-0000-0000-000000000001
00000000-0000-0000-0000-000000000010
00000000-0000-0000-0000-000000000100
00000000-0000-0000-0000-000000001000
00000000-0000-0000-0000-000000010000
00000000-0000-0000-0000-000000100000
00000000-0000-0000-0000-000001000000
00000000-0000-0000-0000-000010000000
00000000-0000-0000-0000-000100000000
00000000-0000-0000-0000-001000000000
00000000-0000-0000-0000-010000000000
00000000-0000-0000-0000-100000000000

与List<System.Guid>.Sort()返回的以下顺序相反

00000000-0000-0000-0000-000000000001
00000000-0000-0000-0000-000000000010
00000000-0000-0000-0000-000000000100
00000000-0000-0000-0000-000000001000
00000000-0000-0000-0000-000000010000
00000000-0000-0000-0000-000000100000
00000000-0000-0000-0000-000001000000
00000000-0000-0000-0000-000010000000
00000000-0000-0000-0000-000100000000
00000000-0000-0000-0000-001000000000
00000000-0000-0000-0000-010000000000
00000000-0000-0000-0000-100000000000
00000000-0000-0000-0001-000000000000
00000000-0000-0000-0010-000000000000
00000000-0000-0000-0100-000000000000
00000000-0000-0000-1000-000000000000
00000000-0000-0001-0000-000000000000
00000000-0000-0010-0000-000000000000
00000000-0000-0100-0000-000000000000
00000000-0000-1000-0000-000000000000
00000000-0001-0000-0000-000000000000
00000000-0010-0000-0000-000000000000
00000000-0100-0000-0000-000000000000
00000000-1000-0000-0000-000000000000
00000001-0000-0000-0000-000000000000
00000010-0000-0000-0000-000000000000
00000100-0000-0000-0000-000000000000
00001000-0000-0000-0000-000000000000
00010000-0000-0000-0000-000000000000
00100000-0000-0000-0000-000000000000
01000000-0000-0000-0000-000000000000
10000000-0000-0000-0000-000000000000

- redcalx

3

“稍微不寻常”是什么意思？如果不知道如何排序，我们怎么能提出任何建议呢？ - DavidG

3

没有更多的上下文，这个陈述是荒谬的。例如，如果您使用GUID作为ID，并按照这些GUID对项目进行排序，则可以更快地搜索。 - O. R. Mapper

1

@O.R.Mapper，看起来OP正在要求按照生成顺序对它们进行排序（“...顺序GUID是唯一的，但是按顺序创建...”）。 - Adriano Repetti

3

好的，我会尽力进行翻译。以下是需要翻译的内容：This question may be useful https://dev59.com/rm035IYBdhLWcg3wKsua - Captain Kenpachi

1

@AdrianoRepetti：我并不是在参考OP所寻找的内容，而是在回应CarbineCoder的评论，该评论声称GUIDs永远不应以任何方式排序。 - O. R. Mapper

显示剩余12条评论

3个回答

6

死灵法术：
答案涉及了如何，但未涉及为什么。
因此，只是为了记录，SQL-server按字节顺序进行排序，也就是说按照自定义的字节顺序：

private static readonly int[] x_rgiGuidOrder = new int[16] // 16 Bytes = 128 Bit 
        {10, 11, 12, 13, 14, 15, 8, 9, 6, 7, 4, 5, 0, 1, 2, 3};

换句话说，如果你把Guid想象成一个连续的UInt128数字，你需要将它分成16个基于256的块，并按照它们的排序顺序排列这些块，以产生与SQL兼容的UID。

如果不清楚，请看下面：

public class SqlGuid
    : System.IComparable
    , System.IComparable<SqlGuid>
    , System.Collections.Generic.IComparer<SqlGuid>
    , System.IEquatable<SqlGuid>
{
    private const int NUM_BYTES_IN_GUID = 16;

    // Comparison orders.
    private static readonly int[] m_byteOrder = new int[16] // 16 Bytes = 128 Bit 
    {10, 11, 12, 13, 14, 15, 8, 9, 6, 7, 4, 5, 0, 1, 2, 3};

    private byte[] m_bytes; // the SqlGuid is null if m_value is null


    public SqlGuid(byte[] guidBytes)
    {
        if (guidBytes == null || guidBytes.Length != NUM_BYTES_IN_GUID)
            throw new System.ArgumentException("Invalid array size");

        m_bytes = new byte[NUM_BYTES_IN_GUID];
        guidBytes.CopyTo(m_bytes, 0);
    }


    public SqlGuid(System.Guid g)
    {
        m_bytes = g.ToByteArray();
    }


    public byte[] ToByteArray()
    {
        byte[] ret = new byte[NUM_BYTES_IN_GUID];
        m_bytes.CopyTo(ret, 0);
        return ret;
    }

    int CompareTo(object obj)
    {
        if (obj == null)
            return 1; // https://msdn.microsoft.com/en-us/library/system.icomparable.compareto(v=vs.110).aspx

        System.Type t = obj.GetType();

        if (object.ReferenceEquals(t, typeof(System.DBNull)))
            return 1;

        if (object.ReferenceEquals(t, typeof(SqlGuid)))
        {
            SqlGuid ui = (SqlGuid)obj;
            return this.Compare(this, ui);
        } // End if (object.ReferenceEquals(t, typeof(UInt128)))

        return 1;
    } // End Function CompareTo(object obj)


    int System.IComparable.CompareTo(object obj)
    {
        return this.CompareTo(obj);
    }


    int CompareTo(SqlGuid other)
    {
        return this.Compare(this, other);
    }


    int System.IComparable<SqlGuid>.CompareTo(SqlGuid other)
    {
        return this.Compare(this, other);
    }


    enum EComparison : int
    {
        LT = -1, // itemA precedes itemB in the sort order.
        EQ = 0, // itemA occurs in the same position as itemB in the sort order.
        GT = 1 // itemA follows itemB in the sort order.
    }


    public int Compare(SqlGuid x, SqlGuid y)
    {
        byte byte1, byte2;

        //Swap to the correct order to be compared
        for (int i = 0; i < NUM_BYTES_IN_GUID; i++)
        {
            byte1 = x.m_bytes[m_byteOrder[i]];
            byte2 = y.m_bytes[m_byteOrder[i]];
            if (byte1 != byte2)
                return (byte1 < byte2) ?  (int) EComparison.LT : (int) EComparison.GT;
        } // Next i 

        return (int) EComparison.EQ;
    }


    int System.Collections.Generic.IComparer<SqlGuid>.Compare(SqlGuid x, SqlGuid y)
    {
        return this.Compare(x, y);
    }


    public bool Equals(SqlGuid other)
    {
        return Compare(this, other) == 0;
    }


    bool System.IEquatable<SqlGuid>.Equals(SqlGuid other)
    {
        return this.Equals(other);
    }


}

这意味着您可以通过以下方式而无需使用SqlGuid来实现：

public class TestClass 
{
    public static void Test()
    {
        System.Collections.Generic.List<System.Guid> ls = new System.Collections.Generic.List<System.Guid>();
        for(int i = 0; i < 100; ++i)
            ls.Add(System.Guid.NewGuid());

        ls.Sort(Compare);
    }


    public static int Compare(System.Guid x, System.Guid y)
    {
        const int NUM_BYTES_IN_GUID = 16;
        byte byte1, byte2;

        byte[] xBytes = new byte[NUM_BYTES_IN_GUID];
        byte[] yBytes = new byte[NUM_BYTES_IN_GUID];

        x.ToByteArray().CopyTo(xBytes, 0);
        y.ToByteArray().CopyTo(yBytes, 0);

        int[] byteOrder = new int[16] // 16 Bytes = 128 Bit 
            {10, 11, 12, 13, 14, 15, 8, 9, 6, 7, 4, 5, 0, 1, 2, 3};


        //Swap to the correct order to be compared
        for (int i = 0; i < NUM_BYTES_IN_GUID; i++)
        {
            byte1 = xBytes[byteOrder[i]];
            byte2 = yBytes[byteOrder[i]];
            if (byte1 != byte2)
                return (byte1 < byte2) ? -1 : 1;
        } // Next i 

        return 0;
    }

}

尽管使用SqlGuid会更加高效，因为SqlGuid不需要在每次比较时重新计算字节数组。

- Stefan Steiger

1

顺带一提：请参考雷蒙德·陈的有多少种方法可以排序GUID？

总结如下：

算法	字节数组	字符串
memcmp	00 11 22 33 44 55 66 77 88 99 AA BB CC DD EE FF	{33221100-5544-7766-8899-AABBCCDDEEFF}
System.Guid / string	33 22 11 00 55 44 77 66 88 99 AA BB CC DD EE FF	{00112233-4455-6677-8899-AABBCCDDEEFF}
SqlGuid	CC DD EE FF AA BB 88 99 66 77 00 11 22 33 44 55	{FFEEDDCC-BBAA-9988-6677-001122334455}
Platform::Guid	33 22 11 00 77 66 55 44 BB AA 99 88 FF EE DD CC	{00112233-6677-4455-BBAA-9988FFEEDDCC}

而Java将每个GUID视为一对带符号的64位整数，采用大端格式排序，参见另一种排序GUID的方法：Java。在两列（位0和64）中，排序顺序是89ABCDEF01234567。在其他列中，排序顺序是0123456789ABCDEF。

- Yahoo Serious

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- petelids · Accepted Answer

Sql Server和.NET对Guid排序的方式有所不同。

.NET框架中有一个名为SqlGuid的结构体，应当与Sql Server中的guid行为相同。

考虑以下例子，来自这里：

List<Guid> a = new List<Guid>();
a.Add(new Guid("3AAAAAAA-BBBB-CCCC-DDDD-2EEEEEEEEEEE"));
a.Add(new Guid("2AAAAAAA-BBBB-CCCC-DDDD-1EEEEEEEEEEE"));
a.Add(new Guid("1AAAAAAA-BBBB-CCCC-DDDD-3EEEEEEEEEEE"));
Console.WriteLine("--Unsorted Guids--");
foreach (Guid g in a)
{
    Console.WriteLine("{0}", g);
}
a.Sort();
Console.WriteLine("--Sorted Guids--");
foreach (Guid g in a)
{
    Console.WriteLine("{0}", g);
}

List<SqlGuid> b = new List<SqlGuid>();
b.Add(new SqlGuid("3AAAAAAA-BBBB-CCCC-DDDD-2EEEEEEEEEEE"));
b.Add(new SqlGuid("2AAAAAAA-BBBB-CCCC-DDDD-1EEEEEEEEEEE"));
b.Add(new SqlGuid("1AAAAAAA-BBBB-CCCC-DDDD-3EEEEEEEEEEE"));
b.Sort();
Console.WriteLine("--Sorted SqlGuids--");
foreach (SqlGuid sg in b)
{
    Console.WriteLine("{0}", sg);
}

这会产生以下输出：

--未排序的Guid--
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee
--排序的Guid--
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
--排序的SqlGuids--
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee

SqlGuid类有一个以Guid为参数的构造函数，两者之间的转换也可以通过强制类型转换进行，所以它们之间的转换应该很容易。例如，在上面的代码中添加以下内容：

List<SqlGuid> c = a.Select(g => new SqlGuid(g)).ToList();
c.Sort();
Console.WriteLine("--Sorted SqlGuids 2--");
foreach (SqlGuid sg2 in c)
{
    Console.WriteLine("{0}", sg2);
}

添加输出：

--已排序的 SqlGuids 2--
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee