It was pointed out in the comments to my previous post that my simple generic sorting routine contains additional overhead compared to TArray Rtl code (Generic.Collections & Generic.Defaults units) because RTTI is used inside the loop. Yes, that is true. Let us improve the code by taking RTTI check away from the loop, while keeping the code simple (without using over-weighted and tricky IComparer interface).
Simple tasks should have simple solutions. Now when I look at it the solution seems quite obvious, still I spent some hours trying to find it – generics are weird for beginner. The last step that led to working code was to declare generic procedural type TCompare inside generic class TArray, without it the code would not compile:
unit GenericSort;
interface
type
TArray<T> = class
public type
TCompare = function(const L, R: T): Integer;
private
class procedure InternalSort(var A: array of T;
Compare: TCompare); static;
public
class procedure InsertionSort(var A: array of T); static;
end;
function CompareInt(const L, R: Integer): Integer;
implementation
uses SysUtils, TypInfo;
class procedure TArray.InternalSort(var A: array of T; Compare: TCompare);
var
I, J: Integer;
Item: T;
P: PTypeInfo;
begin
for I:= 1 + Low(A) to High(A) do begin
Item:= A[I];
J:= I - 1;
while (J >= Low(A)) and (Compare(A[J], Item) > 0) do begin
A[J + 1]:= A[J];
Dec(J);
end;
A[J + 1]:= Item;
end;
end;
function CompareInt(const L, R: Integer): Integer;
begin
if L < R then Result:= -1
else if L > R then Result:= 1
else Result:= 0;
end;
class procedure TArray.InsertionSort(var A: array of T);
var
P: PTypeInfo;
begin
P:= TypeInfo(T);
case P^.Kind of
tkInteger: InternalSort(A, @CompareInt);
tkUString: InternalSort(A, @CompareStr);
end;
end;
end.
Note that the function ‘CompareInt’ is declared in interface section. If you comment out interface declaration you get compile error
[DCC Error] GenericSort.pas(54): E2506 Method of parameterized type declared in interface section must not use local symbol ‘CompareInt’.
Nice to see some simple solution came out of this 🙂
Some small change and you can even get rid of your own CompareInt routine:
uses Math, Types; type TCompare<T> = function(const Left, Right: T): TValueRelationship; TCompareInt = function(const Left, Right: Integer): TValueRelationship; var P: PTypeInfo; const CompareInt: TCompareInt = CompareValue; begin P:= TypeInfo(T); case P^.Kind of tkInteger: InternalSort(Values, @CompareInt); tkUString: InternalSort(Values, @CompareStr); end; end;Unfortunatly you cannot pass the CompareValue routine directly because its overloaded and getting the address of the first one all the time. But putting it into the constant fixes that. Just comparing floating numbers could get messy with that because of the additional Epsilon parameter in the CompareValue routine.
IMHO you’re using an Insertion sort, which is far from efficient.
Generics (like regular old TList) uses the much faster QuickSort algorithm.
I’ve written some comparable functions (with much more methods, like serialization) for dynamic arrays. Working from Delphi 6 up to XE. You could find some hints about using such low-level RTTI access. There is even a way of comparing and/or hashing nested records and dynamic arrays. See http://synopse.info/forum/viewtopic.php?id=254
IMHO you’re using an Insertion sort, ..
Sure I am 🙂
I have contributed 5 simple sorting algorithms to Rosetta Code recently, and it made me think further about generics.
Nice article, I would suggest not calling it TArray though because that’s already used by SysUtils.TArray.
SysUtils.TArray<T> is not the same as TArray.
Actually I would consider making either a child class or a class helper of Collections.Generics.TArray.
I know it’s not the same thing, but it has the same name: SysUtils.TArray and GenericSort.Array. If you defined a new type for storing strings, would you call it a TStringList?
Actually TArray is defined in System, not SysUtils, my mistake.
Maybe I missed something, but as far as I can see all you have done here is reduce two sets of simple, easily understood code (one for sorting an array of Integer the other for sorting an array of String) to one set of code, slightly larger than either of the original 2, a set of code which is orders of magnitude more complex, took longer to create than the combined effort to create the original 2, but which ultimately does only the same thing, and without modification will only work for, the exact same types as those original 2 sets of code!
Thanks to that case on TypeKind, surely this “generic” is only good for Integers and Strings and extending this “generic” to support other types, generically, is non-trivial (thinking especially of TArray where the TypeKind info will only tell you that it is an object so you then have to do further classtype tests and implement class specific comparison routines internal to the GENERIC class, thus binding the “generic” to very specific classes and creating a “scope knot”, forcing that GENERIC to “use” all the units that contain any/all types that you may ever wish to sort.
vs
Copy/Paste simple, easily understood array sort routine, plok it in the unit that contains the type being sorted, modify the one small piece of code that compares the elements – job done and no scope knots.
Again, could someone please explain what REAL benefit generics actually delivers, beyond the ability to claim bragging rights and swagger around showing off the chest wig awarded for having deconvoluted unnecessarily labyrinthine implementation details to identify the limitations and problems imposed by generics on otherwise simple code, and successfully spending hours working around them to finally deliver something that works which could have been delivered in a fraction of the time without generics?
.. as far as I can see all you have done here is ..
What I have done here is a runtime implementation of the job that IMO should be done much more efficiently at compile time. We have not such a smart compiler right now, but generics is certainly an interesting concept to play with.