8

顺序 GUID 是唯一的，但是是按顺序创建的；该顺序有点不寻常，并且与使用标准 .NET Guid 比较器时获得的顺序不同。

我正在寻找一个 C# Guid 比较器，它将按顺序 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
4

3 回答 3

13

Sql server 和 .NET 对 guid 进行排序的方式有所不同。

在 .NET 框架中有一个称为 struct 的结构，其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);
}

这将产生输出：

--未排序
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee
的Guids---排序的Guids-- --
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

于 2015-04-16T12:49:21.077 回答
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 不需要在每次进行比较时都重新计算字节数组。

于 2018-03-14T14:04:15.100 回答
1

离题：请参阅 Raymond Chen 的How many ways are there to sort GUIDs？

总结为：

算法 字节数组 细绳
记忆体 00 11 22 33 44 55 66 77 88 99 AA BB CC DD EE FF {33221100-5544-7766-8899-AABBCCDDEEFF}
System.Guid / 字符串 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}
平台::指南 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。

于 2022-02-11T12:12:40.097 回答