Что делает фактический компаратор TArray.Sort по умолчанию и когда вы его используете?

Question

В помощь Delphi XE2 для System.Generics.Collections.TArray.Sort, он говорит

Note: If the Comparer parameter is provided, it is used to compare elements; otherwise the default comparator for the array elements is used. 

я вырыл немного назад и обнаружил, что компаратор по умолчанию для TArray.Sort является _LookupVtableInfo от System.Generics.Defaults. Код для этого является

function _LookupVtableInfo(intf: TDefaultGenericInterface; info: PTypeInfo; size: Integer): Pointer; 
var 
    pinfo: PVtableInfo; 
begin 
    if info <> nil then 
    begin 
    pinfo := @VtableInfo[intf, info^.Kind]; 
    Result := pinfo^.Data; 
    if ifSelector in pinfo^.Flags then 
     Result := TTypeInfoSelector(Result)(info, size); 
    if ifVariableSize in pinfo^.Flags then 
     Result := MakeInstance(Result, size); 
    end 
    else 
    begin 
    case intf of 
     giComparer: Result := Comparer_Selector_Binary(info, size); 
     giEqualityComparer: Result := EqualityComparer_Selector_Binary(info, size); 
    else 
     System.Error(reRangeError); 
     Result := nil; 
    end; 
    end; 
end; 

Это называется

IComparer<T>(_LookupVtableInfo(giComparer, TypeInfo(T), SizeOf(T))) 

Я просмотрел эту совсем немного, и я на самом деле не все, что уверен, что знаю, что он делает. Он просто сравнивает бит в памяти друг с другом или что именно?

Вторая часть вопроса является более обобщенной из того, какие ситуации вы, скорее всего, захотите использовать компаратор по умолчанию, или маловероятно, что вы когда-нибудь захотите его использовать?

Answer 1

Сравнение по умолчанию обеспечивает реализацию для многих распространенных типов. В частности, она поддерживает следующие:

• Интегральные типы: Byte, Word, Integer т.д.
• перечисляемых типов.
• Плавающие типы точек.
• Строки.
• Наборы.
• Класс экземпляров.
• Процедурные переменные.
• Методы.
• Варианты.
• Статические массивы.
• Динамические массивы.
• Интерфейсы.
• Указатели.
• Записи.

Для многих из этих типов реализация по умолчанию - это именно то, что вы ожидаете. Например, для целых чисел, перечисляемых типов, типов с плавающей точкой, в реализации используются операторы <, > и =. Для string по умолчанию используются вызовы CompareStr.

Для других типов реализация по умолчанию, вероятно, менее полезна. Например, для записей сравнение представляет собой двоичное сравнение. Очень вероятно, что вы захотите предоставить свою собственную реализацию сравнения для записи. Одна вещь, которую нужно следить за записями, заключается в том, что сопоставитель по умолчанию будет сравнивать любые дополнения в вашей записи, и вы никогда не захотите этого делать. Поэтому он никогда не бывает полезен для выровненной записи с дополнением. И я также задал вопрос утилите для записей, содержащих ссылочные типы.

Для динамических массивов реализация по умолчанию сначала сравнивает длину, а затем, если длина равна, сравнивает двоичный контент массива. Таким образом, это может быть разумно для массивов простых типов значений. Но для многомерных динамических массивов или массивов ссылочных типов не так много.

Для экземпляров классов, методов, процедурных переменных интерфейсы по умолчанию сравнивают операнды как указатель (два указателя в случае методов) и выполняют сравнение адресов.

Когда вы хотите использовать компаратор по умолчанию? Ну, вы будете использовать его, когда это будет соответствовать вашим требованиям для сравнения. Поэтому это, безусловно, имеет смысл для простых типов значений. Помимо этого вам нужно будет принять решение в каждом конкретном случае.

Answer 2

Функция вы разместили там на самом деле не функция Comparision, а функция, которая возвращает функцию сравнения, на основе TypeInfo и SizeOf Т.

После этого глубже, мы видим в Generics.Defaults многие функции вида:

function Compare_ имя типа (Inst: Pointer; const Left, Right: Тип ): Integer;

, которые все имеют одинаковый корпус (но заметьте слева и справа имеют разные типы)

begin 
    if Left < Right then 
    Result := -1 
    else if Left > Right then 
    Result := 1 
    else 
    Result := 0; 
end; 

и, наконец, все осталось

function BinaryCompare(const Left, Right: Pointer; Size: Integer): Integer; 
var 
    pl, pr: PByte; 
    len: Integer; 
begin 
    pl := Left; 
    pr := Right; 
    len := Size; 
    while len > 0 do 
    begin 
    Result := pl^ - pr^; 
    if Result <> 0 then 
     Exit; 
    Dec(len); 
    Inc(pl); 
    Inc(pr); 
    end; 
    Result := 0; 
end; 

Answer 3

Дэвид проделал большую работу текстуально описания того, как работают компараторы по умолчанию, но для некоторых из вас это может быть легче следовать, когда вы видите, как базовый код (и решить, действительно ли применяются сопоставления по умолчанию).

Я покрою только Compare_ стиль сравнений. Стиль Equals_ работает аналогичным образом.

Что происходит, что _LookupVtableInfo выбирает IComparer интерфейс для Compare_ сравнения стилей (и стиль IEqualityComparer для Equals_).

Под этих интерфейсами не обычные интерфейсы, но интерфейс обертки вокруг глобальных функций этой формы для Compare_ стиля:

function Compare_t<T>(Inst: Pointer; const Left, Right: T): Integer; 

и глобальных процедур этой формы для Equals_ стиля:

function Equals_t<T>(Inst: Pointer; const Left, Right: T): Integer; 
function GetHashCode_t<T>(Inst: Pointer; const Left, Right: T): Integer; 

результат Compare_ функции стиля просты, но немного отличаются от -1, 0, +1, что некоторые люди могут ожидать:

< 0 for Left < Right 
= 0 for Left = Right 
> 0 for Left > Right 

Для большинства случаев, реализация очень прост:

Я сгруппировал Compare_ функции стиля, как они делают это.

• Обычные типы (включая счетчики и Int64).
• Типы с плавающей запятой (Real) (включая Comp и валюту).
• Короткие струны (от Turbo Pascal/Delphi 1 день).
• Широкие строки (в стиле OLE).
• Методы.
• Указатели (включая классы, интерфейсы, ссылки на классы и процедуры).

(Обычные типы вне диапазона 1, 2, 4, 8 байтов и реальные типы вне диапазона 4, 8, 10 байт вызывают ошибку, поскольку они являются незаконными).

Первая группа просто вычитает слева от правых: подписан/беззнаковых целых чисел длины 1 или 2 байта

function Compare_I1(Inst: Pointer; const Left, Right: Shortint): Integer; 
function Compare_I2(Inst: Pointer; const Left, Right: Smallint): Integer; 
function Compare_U1(Inst: Pointer; const Left, Right: Byte): Integer; 
function Compare_U2(Inst: Pointer; const Left, Right: Word): Integer; 

    Result := Left - Right; 

Вторая группа делает сравнение:

function Compare_I4(Inst: Pointer; const Left, Right: Integer): Integer; 
function Compare_I8(Inst: Pointer; const Left, Right: Int64): Integer; 
function Compare_U4(Inst: Pointer; const Left, Right: LongWord): Integer; 
function Compare_U8(Inst: Pointer; const Left, Right: UInt64): Integer; 
function Compare_R4(Inst: Pointer; const Left, Right: Single): Integer; 
function Compare_R8(Inst: Pointer; const Left, Right: Double): Integer; 
function Compare_R10(Inst: Pointer; const Left, Right: Extended): Integer; 
function Compare_RI8(Inst: Pointer; const Left, Right: Comp): Integer; 
function Compare_RC8(Inst: Pointer; const Left, Right: Currency): Integer; 
function Compare_WString(Inst: PSimpleInstance; const Left, Right: WideString): Integer; 
function Compare_Pointer(Inst: PSimpleInstance; Left, Right: NativeUInt): Integer; 

type 
{$IFNDEF NEXTGEN} 
    TPS1 = string[1]; 
    TPS2 = string[2]; 
    TPS3 = string[3]; 
{$ELSE NEXTGEN} 
    OpenString = type string; 
    TPS1 = string; 
    TPS2 = string; 
    TPS3 = string; 
{$ENDIF !NEXTGEN} 

function Compare_PS1(Inst: PSimpleInstance; const Left, Right: TPS1): Integer; 
function Compare_PS2(Inst: PSimpleInstance; const Left, Right: TPS2): Integer; 
function Compare_PS3(Inst: PSimpleInstance; const Left, Right: TPS3): Integer; 
// OpenString allows for any String[n], see http://my.safaribooksonline.com/book/programming/borland-delphi/1565926595/5dot-language-reference/ch05-openstring 
function Compare_PSn(Inst: PSimpleInstance; const Left, Right: OpenString): Integer; 

    if Left < Right then 
    Result := -1 
    else if Left > Right then 
    Result := 1 
    else 
    Result := 0; 

function Compare_Method(Inst: PSimpleInstance; const Left, Right: TMethodPointer): Integer; 
var 
    LMethod, RMethod: TMethod; 
begin 
    LMethod := TMethod(Left); 
    RMethod := TMethod(Right); 
    if LMethod < RMethod then 
    Result := -1 
    else if LMethod > RMethod then 
    Result := 1 
    else 
    Result := 0; 
end; 

Теперь мы получаем интересное бит: не столь простые результаты.

Строки, используемые CompareStr. Если вы хотите что-то другое, вы можете использовать TOrdinalIStringComparer

function Compare_LString(Inst: PSimpleInstance; const Left, Right: AnsiString): Integer; 
function Compare_UString(Inst: PSimpleInstance; const Left, Right: UnicodeString): Integer; 

    Result := CompareStr(Left, Right); 

BinaryCompare используется для:

• двоичных данных, в том числе неизвестных, Char/WChar, Set, Array, Record. Исключение, если двоичные данные имеют размер 1, 2 или 4 байта в x86 и x64 и 8 байтов в x64, он будет сравниваться как целые числа.
• динамические изображения (будьте осторожны, когда они многомерны!).
• варианты в крайнем случае (см ниже)

Для записей, которые можно сравнить, то имеет смысл выполнять перегрузку операторов, и имеет компаратор использовать эти операторы.

Двоичные данные 1, 2, 4 или 8 байт представляет собой исключение, которое будет давать странные результаты на прямой порядок байтов машин (Intel x86 и x64, а также би-Endian Arm в режиме прямой порядок байтов):

function Comparer_Selector_Binary(info: PTypeInfo; size: Integer): Pointer; 
begin 
    case size of 
    // NOTE: Little-endianness may cause counterintuitive results, 
    // but the results will at least be consistent. 
    1: Result := @Comparer_Instance_U1; 
    2: Result := @Comparer_Instance_U2; 
    4: Result := @Comparer_Instance_U4; 
    {$IFDEF CPUX64} 
    // 64-bit will pass const args in registers 
    8: Result := @Comparer_Instance_U8; 
    {$ENDIF} 
    else 
    Result := MakeInstance(@Comparer_Vtable_Binary, size); 
    end; 
end; 

остальное двоичном:

function Compare_Binary(Inst: PSimpleInstance; const Left, Right): Integer; 
begin 
    Result := BinaryCompare(@Left, @Right, Inst^.Size); 
end; 

function Compare_DynArray(Inst: PSimpleInstance; Left, Right: Pointer): NativeInt; 
var 
    len, lenDiff: NativeInt; 
begin 
    len := DynLen(Left); 
    lenDiff := len - DynLen(Right); 
    if lenDiff < 0 then 
    Inc(len, lenDiff); 
    Result := BinaryCompare(Left, Right, Inst^.Size * len); 
    if Result = 0 then 
    Result := lenDiff; 
end; 

Как обычно, Variants в лиге свои собственные. Сначала проверяется VarCompareValue. Если это не удается, то проверяется Compare_UString. Если это не удается, то проверяется BinaryCompare. Если это не удастся: тяжелая удача.

function Compare_Variant(Inst: PSimpleInstance; Left, Right: Pointer): Integer; 
var 
    l, r: Variant; 
    lAsString, rAsString: string; 
begin 
    Result := 0; // Avoid warning. 
    l := PVariant(Left)^; 
    r := PVariant(Right)^; 
    try 
    case VarCompareValue(l, r) of 
     vrEqual:  Exit(0); 
     vrLessThan:  Exit(-1); 
     vrGreaterThan: Exit(1); 
     vrNotEqual: 
     begin 
     if VarIsEmpty(L) or VarIsNull(L) then 
      Exit(1) 
     else 
      Exit(-1); 
     end; 
    end; 
    except // if comparison failed with exception, compare as string. 
    try 
     lAsString := PVariant(Left)^; 
     rAsString := PVariant(Right)^; 
     Result := Compare_UString(nil, lAsString, rAsString); 
    except // if comparison fails again, compare bytes. 
     Result := BinaryCompare(Left, Right, SizeOf(Variant)); 
    end; 
    end; 
end;