More performance Stringgrid sorting algorithm help

[3ddark 3]

The sort function is working. But when I sort for 100000 rows, it works very slowly.

What suggestions do you have for better performance. I'm only sorting for one column at a time. No multiple sorting

procedure TStringGrid.SortStringGrid(ACol: Integer);
var
  i, j : Integer;
  LTemp: TStringList;
  LSortType: TSortMode;
  LCompResult: Boolean;
begin
  Perform(WM_SETREDRAW, 0, 0);
  LTemp := TStringList.Create;
  try
    LSortType := smNone;
    for i := Self.FixedRows to Self.RowCount - 2 do
    begin
      for j:= i+1 to Self.RowCount-1 do
      begin
        //first sort or another column sort
        if (FSortType = smNone) or (FSortType = smDesc) or ((FSortType = smAsc) and (FSortCol <> ACol)) then
        begin
          if AnsiCompareText(Self.Cells[ACol, i], Self.Cells[ACol, j]) = GreaterThanValue then
          begin
            LTemp.Assign(Self.Rows[j]);
            Self.Rows[j].Assign(Self.Rows[i]);
            Self.Rows[i].Assign(LTemp);
          end;
          LSortType := smAsc;
        end
        else if (FSortType = smAsc) and (FSortCol = ACol) then  //sort same column asc to desc
        begin
          if AnsiCompareText(Self.Cells[ACol, i], Self.Cells[ACol, j]) = LessThanValue then
          begin
            LTemp.Assign(Self.Rows[i]);
            Self.Rows[i].Assign(Self.Rows[j]);
            Self.Rows[j].Assign(LTemp);
          end;
          LSortType := smDesc;
        end;
      end;
    end;
    FSortType := LSortType;
    FSortCol := ACol;
  finally
    LTemp.free;
    Perform(WM_SETREDRAW, 1, 0);
    Invalidate;
  end;
end;

[dummzeuch 1505]

That's Bubble Sort you are using, which is not renowned for speed but mostly for the funny name.

Maybe it would help to use something faster?

[Anders Melander 1783]

57 minutes ago, dummzeuch said:

That's Bubble Sort you are using, which is not renowned for speed but mostly for the funny name.

 

Funny name you say? How about he optimize it with Gnome sort instead:

procedure GnomeSort(List: TList<integer>);
begin
  var i := 0;
  while (i < List.Count-1) do
    if (i = 0) or (List[i] >= List[i-1]) then
      Inc(i)
    else
    begin
      var Swap := List[i];
      List[i] := List[i-1];
      List[i-1] := Swap;
      Dec(i);
    end;
end;

[Arnaud Bouchez 407]

1 hour ago, Anders Melander said:

 

Funny name you say? How about he optimize it with Gnome sort instead:

It is also known as "stupid sort".

Best algorithm name ever.

[Anders Melander 1783]

2 minutes ago, Arnaud Bouchez said:

It is also known as "stupid sort".

Best algorithm name ever.

Yes it's horrendously slow but if performance isn't important it's nice and short and easy to implement - if you can remember the algorithm. I've used it a few times in throw away production code just because I like its simplicity. Compare to how often people get quicksort wrong when they roll their own.

[FPiette 383]

3 hours ago, 3ddark said:

What suggestions do you have for better performance.

I suggest to first extract all strings used as key from the grid along with their index and move them in a single buffer (Avoid numerous memory allocation), keeping the pointers into an array (of pointers). Then use a fast algorithm to sort the array of pointers by dereferencing the pointers to access the strings for comparison. Moving only the pointers is the key to fast operation. Once the array is sorted, use the index part to move the grid rows.

 

This will be efficient for a large grid because strings are moved only once to create the array of pointers

[Vandrovnik 214]

6 hours ago, Anders Melander said:

 

Funny name you say? How about he optimize it with Gnome sort instead:

 

OK, and when it should work faster, we can always optimize it with starting at i:=1 and using tList<>.Exchange 🙂

[Anders Melander 1783]

6 minutes ago, Vandrovnik said:

we can always optimize it with starting at i:=1

That won't work. You need to start at zero.

 

10 minutes ago, Vandrovnik said:

tList<>.Exchange

That's cheating. Then you might as well just optimize it to use TList.Sort

[Vandrovnik 214]

19 minutes ago, Anders Melander said:

That won't work. You need to start at zero.

I cannot see why? In first step, "if (i=0) ..." will execute "inc(i)", so we have i=1 and continue with next iteration...

while (i < List.Count-1) do
    if (i = 0) or (List[i] >= List[i-1]) then
      Inc(i)
    else

[Anders Melander 1783]

Well now that I've had my fun here's a serious suggestion:

type
  TGridCracker = class(TCustomGrid);
  
procedure SortGrid(Grid: TCustomGrid; ACol: integer; Ascending: boolean);  
begin
  var Rows := TList<integer>.Create;
  Rows.Capacity := Grid.RowCount - Grid.FixedRows;
  
  // Populate list with row indices
  for var i := Grid.FixedRows to Grid.RowCount-1 do
    Rows.Add(i);

  // Sort the row indices
  Rows.Sort(TComparer<integer>.Construct(
    function(const A, B: integer): integer
    begin
      Result := AnsiCompareText(Grid.Cells[ACol, A], Grid.Cells[ACol, B]);
      if (not Ascending) then
        Result := -Result;
    end));
  
  // Move the rows in-place to their new position
  Grid.BeginUpdate;
  try
  
    var ToIndex := Grid.FixedRows;
    for var FromIndex in Rows do
      if (FromIndex <> ToIndex) then
        TGridCracker(Grid).MoveRow(FromIndex, ToIndex);
  
  finally
    Grid.EndUpdate;
  end;
end;

I've not used TStringGrid in decades but I think it might be fast enough if you can get it to compile (I haven't tried).

 

I'm assuming that the protected MoveRow method does what we need (i.e. move a whole row in the grid). It might not though.

A minor optimization would be to use a TArray<integer> instead of a TList<integer> but the improvement would be minimal.

[Anders Melander 1783]

12 minutes ago, Vandrovnik said:

I cannot see why? In first step, "if (i=0) ..." will execute "inc(i)", so we have i=1 and continue with next iteration...

If you start with i := 1 then the 0 and 1 elements will always be swapped.

If you then also change the test for (i = 0) to (i = 1) then the 0 and 1 elements will never be swapped.

 

Try to run it in your head with just three elements in reverse sort order.

iteration  elements
    0      3  2  1    i=0: inc
           ^

    1      3  2  1    swap and dec
              ^

    2      2  3  1    i=0: inc
           ^

    3      2  3  1    ok: inc
              ^

    4      2  3  1    swap and dec
                 ^

    5      2  1  3    swap and dec
              ^

    6      1  2  3    i=0: inc
           ^

    7      1  2  3    ok: inc
              ^

    8      1  2  3    ok: inc
                 ^

    9      1  2  3    done
                    ^ 

 

[Vandrovnik 214]

Test is not changed, just at the beginning instead of i:=0 I would use i:=1;

When I start with i:=1 with Data 3, 2, 1, it is as in your example, just first iteration is already done:

 

iteration  elements
    0      3  2  1    swap and dec
              ^

    1      2  3  1    i=0: inc
           ^

    ...

If Data is 1, 2, 3, it is:
 

iteration  elements
    0      1  2  3    inc, because List[1] >= List[0]
              ^

    1      1  2  3    inc, because List[2] >= List[1]
                 ^

    

 

 

[Anders Melander 1783]

1 hour ago, Vandrovnik said:

Test is not changed, just at the beginning instead of i:=0 I would use i:=1;

When I start with i:=1 with Data 3, 2, 1, it is as in your example, just first iteration is already done:

Yes. You are right.

[Vincent Parrett 750]

Everyone focusing on the sorting algorithm, no one comments on the folly of loading a 100K rows into a TStringGrid 😉 

 

[Anders Melander 1783]

17 minutes ago, Vincent Parrett said:

the folly of loading a 100K rows into a TStringGrid

or any grid for that matter. Well I thought that was a given and that the excessive row count was just to exacerbate the poor performance for benchmark purposes.

[BruceTTTT 7]

I had my own heap sort algorithm that worked well and allowed for nested row sorts, and controlling sort based on integers, strings, and dates. It worked very well and was much faster than a bubble sort.

 

For fun, I rewrote this using TStringLists, exporting the column data (that's sorted) to the stringlist, using its sort routine with the anonymous function parameter to select the type of data, then moving the original rows around based on the results of the TStringList sort. To my surprise, this was faster than the heap sort. Not by much, but noticeable with thousands of rows. I now use it as my native grid sort.

[aehimself 396]

On 9/20/2020 at 9:33 PM, Anders Melander said:

 

begin
  var Rows := TList<integer>.Create;

 

😢

[Anders Melander 1783]

23 hours ago, aehimself said:

😢

Why so sad? Because of the leak?

[aehimself 396]

4 minutes ago, Anders Melander said:

Why so sad? Because of the leak?

Leaks are easy to be fixed, no. I just personally dislike inline variable declarations.

 

If the Delphi language is moving closer to C#, they could have implemented something useful like Linq or the "?" operator when assigning values to variables (String myVar = inCondition ? "" : otherClass.SringProperty; forgot the name, sorry) in my opinion; that's all.

[Anders Melander 1783]

45 minutes ago, aehimself said:

I just personally dislike inline variable declarations.

Fair enough.

I've come to use them a lot. Often I have to remind myself to use a new feature after it's introduced but this one feels so natural that I'm not thinking about it all. If anything I have to remind myself not to use it too much.

 

47 minutes ago, aehimself said:

the "?" operator

The ternary operator. Didn't like it when my main language was C++ and I still don't like it. For me it somehow breaks the flow when I'm reading code.

[aehimself 396]

9 minutes ago, Anders Melander said:

The ternary operator.

Yes, yes, yes, that is the name. I use it a lot, and I keep forgetting it's name. I should seriously consider inking it on my wrist.

Not only the question mark, though.

That wouldn't help much.

9 minutes ago, Anders Melander said:

For me it somehow breaks the flow when I'm reading code.

That's the beauty of it, no? For me, inline variable declarations are making the code harder to read, for you it's ternary operators. I have a colleague who always writes if (expression == false) instead of if (!expression) because he admitted he misses the exclamation mark about 80% of the times.

 

All in all - even if you don't use many of them - it's good to have a bigger toolset to choose from when you are coding. We just have our preferences.

 

Edit: never thought about it, but do inline variables work like in C#? For example

if (condition)
{
 String myStr = "";
}
myStr = "Hello world";

will not compile, as inline variables are local to the current block. Does it behave the same way in Delphi?

 

Edited September 27, 2020 by aehimself

[Anders Melander 1783]

56 minutes ago, aehimself said:

Does it behave the same way in Delphi?

Yes.

Without that I wouldn't use them.

[FPiette 383]

10 hours ago, aehimself said:

I just personally dislike inline variable declarations.

It is sometimes very useful when you have to port code from another language which makes use of that feature. It is not always easy to replace several variables in a single function having same name but totally independent.

[Lars Fosdal 1792]

I like inline declarations with their scope limitations.
I particularly like the inline declaration of loop variables with type inference.

I do not like the leaks inline declared variables can cause with captures.  
https://quality.embarcadero.com/browse/RSP-29564

[Rollo62 536]

I like inline vars, but don't see much importance for my right now.
Thats why I don't use them (and also for backwards compatibility reasons) until they are really stable and tested 150%.

 

Same I like ternary operators, but in Delphi we only have the lame "IfThen( ..."  replacments.
I would like to see them in the language too, which will help a lot to shorten some specific code.
Its a higher importance to me, but still not a killer feature.

 

There are more important things to do, like closing current issues, before opening new, un-needed issues.