Jump to content
3ddark

More performance Stringgrid sorting algorithm help

Recommended Posts

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;

Share this post


Link to post

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?

  • Thanks 2

Share this post


Link to post
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;

:classic_wink:

  • Thanks 1
  • Confused 1

Share this post


Link to post
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.

  • Like 1

Share this post


Link to post
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.

  • Like 1
  • Thanks 1

Share this post


Link to post
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

  • Thanks 1

Share this post


Link to post
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 🙂

Share this post


Link to post
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 :classic_smile:

Share this post


Link to post
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

Share this post


Link to post

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.

  • Thanks 1

Share this post


Link to post
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
                    ^ 

 

Share this post


Link to post

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]
                 ^

    

 

 

  • Like 1

Share this post


Link to post
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.

Share this post


Link to post
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.

Share this post


Link to post

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.

Share this post


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

 


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

 

😢

Share this post


Link to post
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.

Share this post


Link to post
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.

  • Like 1

Share this post


Link to post
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 by aehimself
  • Like 1

Share this post


Link to post
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.

Share this post


Link to post

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.

 

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×