Menu
In QuickSort, a lot of time is spent on the swap temp:=var[i]; var[i]:=var[j]; var[j]:=temp. When the vars are integer I time 140 msec for a large random array. When the vars are string, the time is 750 msec. It appears to me that much of the difference is caused by the need to update the reference counts in all three assignments.
But is this necessary? After all, the reference counts for var[i] and var[j] will be the same before and after these three assignments. Would the following code corrupt things? (not that it solves a speed problem, but out of interest):
// P : Pstring;
move(values[i],P,sizeOf(Pstring));
move(values[j],values[i],sizeOf(Pstring));
move(P,values[i],sizeOf(Pstring));
There is no temp variable. Only the two pointers to the strings are interchanged. And if this is oké, is there a Delphi function to swap 2 pointers?
636
In this program, we need to swap two strings without using a third variable. Swapping two strings usually take a temporary third variable. One of the approach to accomplish this is to concatenate given two strings into first string.
Let us see the correct ways for swapping strings: If you are using character pointer for strings (not arrays) then change str1 and str2 to point each other’s data. i.e., swap pointers. In a function, if we want to change a pointer (and obviously we want changes to be reflected outside the function) then we need to pass a pointer to the pointer.
Swapping two strings usually take a temporary third variable. One of the approach to accomplish this is to concatenate given two strings into first string. Extract string 2 using substring (0, length (string1) - (string2)) i.e. in our case it will be substring (0, (11-4)).
1 Define two strings that need to be swapped. 2 Concatenate both the strings and store it in first string. 3 Extract the string from indexes 0 to length (string1) - (string2) using substring function and store it in string 2. 4 Extract the string from index length (string2) till end using substring function and store it in string 1.
What you are proposing is a well known and valid optimisation. Rather than calling the Move function it is better to perform direct assignments using casts to avoid reference counting code being generated.
var
temp: Pointer;
....
temp := Pointer(var[i]);
Pointer(var[i]) := Pointer(var[j]);
Pointer(var[j]) := temp;
In order for this to work you need to be confident that no exceptions will be raised during the swap process. Simple assignments of valid memory will not lead to exceptions, so this concern can be readily dismissed.
68
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
