Как отсортировать последовательные идентификаторы GUID в C#?

Question

Как отсортировать последовательные идентификаторы GUID в C#?

Последовательные GUID уникальны, но создаются с заказом; этот порядок немного необычен и отличается от порядка, достигнутого при использовании стандартного компаратора.NET Guid.

Я ищу компаратор C# Guid, который будет сортировать по правилам последовательных идентификаторов GUID.

== ОБНОВЛЕНИЕ ==

Я конкретно имею в виду последовательные идентификаторы GUID, созданные NewSequentialId() в SQL Server, хотя теперь я понимаю, что стандартный вызов Win32 API UuidCreateSequential() использует другую схему для SQL Server (я предположил, что они были такими же, когда я писал вопрос),

== ОБНОВЛЕНИЕ 2 ==

petelids дает ответ ниже, используя, например, List.Sort (), следующую последовательность (используя начальный список GUID с 1 в каждом 4-битном местоположении)...

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.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

9

c# guid newsequentialid

Источник

user15703 16 апр '15 в 12:13

3 ответа

Решение

Necromancing:
Ответ охватывает как, но не почему.
Итак, просто для записи, SQL-сервер сортирует их по байтам по порядку, то есть в произвольном порядке:

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 не нужно пересчитывать байтовый массив каждый раз, когда происходит сравнение.

6

Источник

user155077 14 мар '18 в 14:04

Отступление: см. Рэймонда Чена Сколько существует способов сортировки GUID?

Резюме:

И Java обрабатывает каждый GUID как пару 64-битных целых чисел со знаком в формате с обратным порядком байтов, см. Другой способ сортировки GUID: Java . В двух столбцах (биты 0 и 64) порядок сортировки 89ABCDEF01234567. В остальных столбцах порядок сортировки — 0123456789ABCDEF.

1

Источник

user422877 11 фев '22 в 12:12

Другие вопросы по тегам c# guid newsequentialid

user3791802 16 апр '15 в 12:49 2015-04-16 12:49 · Accepted Answer · 2015-04-16 12:49

Существует разница между способом, которым Sql-сервер и.NET руководствуются.

В.NET Framework есть структура, которая называется SqlGuid это должно вести себя так же, как руководства в Sql Server.

Рассмотрим следующий пример, адаптированный здесь:

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-сссс-DDDD-2eeeeeeeeeee
2aaaaaaa-BBBB-сссс-DDDD-1eeeeeeeeeee
1aaaaaaa-BBBB-сссс-DDDD-3eeeeeeeeeee
Сортированные направляющие
1aaaaaaa-BBBB-сссс-DDDD-3eeeeeeeeeee
2aaaaaaa-BBBB-сссс-DDDD-1eeeeeeeeeee
3aaaaaaa-BBBB-сссс-DDDD-2eeeeeeeeeee
- Сортировка SqlGuids--
2aaaaaaa-BBBB-сссс-DDDD-1eeeeeeeeeee
3aaaaaaa-BBBB-сссс-DDDD-2eeeeeeeeeee
1aaaaaaa-BBBB-сссс-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-сссс-DDDD-1eeeeeeeeeee
3aaaaaaa-BBBB-сссс-DDDD-2eeeeeeeeeee
1aaaaaaa-BBBB-сссс-DDDD-3eeeeeeeeeee