TListBox and sorting

[Morten Brendefu]

I did an experiment regarding sorting of 256.000 random "names" using TListBox component.
A friend of mine say that TListBox is faster than my code at sorting, so I wanted to test this out of curiosity.

Method of testing.
When I have created 256 thousand random textstrings, each 6 characters, I add these into a listbox that is invisible, hence no updating whilst adding.
Then I Press a button in order to do only one thing:
TListBox.Sorted:=TRUE
It takes about 5 seconds, and the control is returned to my form.
Does this mean that 256000 purely random strings have been sorted in that time?
My friend claim so.

Now for the big thing.
If it is sorted, why when I press another button in order to view the TListBox does this operation halt the computer for almost 3 minutes before the component shows the data?
I would think that this is because it is actually sorting the data now.

My routines that is a derivate of a binary approach is not by far fast, but it does the job of hiding the TListBox, copying the unsorted data from a TListBox into an Array, Then sorting this data through an index, deleting the data in the TListBox, adding all the data from my now sorted array, making TListBox visible, and all data can be viewed in the correct order instantly as the TListBox.visible:=TRUE.
The complete work takes almost one minute less than TListBox alone.

does anybody have any ideas as to why TListBox is so slow showing the data if it indeed has got the data sorted?

Best regards,
Morten Brendefur.

[pritaeas]

Am not sure what version of Delphi you have, and whether or not you have the source code. You could step through the TCustomListBox.SetSorted method, to see what actually happens. You may have to set some breakpoints, due to sending of messages.

For normal sorting speed-up on a visible listbox, you can set the Items.BeginUpdate, then Sort, then the Items.EndUpdate. Technically, it should not really differ from your visible technique in terms of speed. Can't say I've ever waited that long for a component to update it's contents.

[Morten Brendefu]

I thought I could show you all my code for parts of this :-)

First I create 256000 random names with this procedure:

procedure TForm1.MakeMaxClick(Sender: TObject);
  VAR
    x :INTEGER;
    y :BYTE;
    z :CHAR;
    sr:abc6;
begin
  Randomize;
  ListBox1.Visible:=FALSE;
  ListBox1.Items.BeginUpdate;
  FOR x:=1 TO Maxarray DO BEGIN
    sr:='';
    FOR y:=1 to 6 DO BEGIN
      z:=CHAR(Random(26)+65);
      sr:=sr+z;
    END;
    ListBox1.Items.Add(sr);
  END;
  ListBox1.Items.EndUpdate;
  ListBox1.Visible:=TRUE;
end;

The code need 14 seconds on my computer in order to finish generating all the random words.
It then instantly show ALL data and I can start scrolling down this unsorted list.

Next step is:

procedure TForm1.Button5Click(Sender: TObject);
begin
  ListBox1.Visible := false;
  ListBox1.Items.BeginUpdate;
  ListBox1.Sorted :=True;
  ListBox1.Items.EndUpdate;
  ListBox1.Visible := True;
  ShowMessage('Finished');
end;

It displays the message "Finished" after approx 11 seconds but still the listbox is not visible.
After a total of 4 minutes(after clicking ok) the listbox is displayed.

My own code for sorting:

PROCEDURE QrebuildIndex;
  VAR
    wTop,wMiddle,wBottom,wPosition : INTEGER;
    bModifier    : BYTE;
    bNeedSearches: ARRAY[1..24] OF INTEGER; // 16 comparisons will find any and all data no matter where in an index of 65536 items. Morten Brendefur 2011.

  PROCEDURE BuildNeedSearches(antall:BYTE); // Builds index of numbers where we have to extend searches by one extra run.
    VAR
      x:BYTE;
    BEGIN
      FOR x:=1 TO antall DO BEGIN
        bNeedSearches[x]:=1;
        bNeedSearches[x]:=(bNeedSearches[x] SHL x);
      END;
      bModifier:=1;
    END;

  PROCEDURE FindPointOfInsert;
    VAR                       
      x:BYTE;

    PROCEDURE Doublecheck; // Some values of top and bottom variables lead to a result that is misplaced by one in a few cases.
      BEGIN
        IF sAbc6[wIndex[wMiddle]] < sAbc6[wPosition] THEN INC(wMiddle); // By doublechecking we exterminate this cause of error.
      END;

    BEGIN
      IF wBottom=bNeedSearches[bModifier] THEN INC(bModifier); // Denne fungerer bare dersom vi bygger hele indexen fra start.
      FOR x:=1 TO bModifier DO BEGIN
        wMiddle:=wTop+((wBottom-wTop) DIV 2);
        IF sAbc6[wIndex[wMiddle]] > sAbc6[wPosition] // Working towards an index all the time.
        THEN wBottom:=wMiddle
        ELSE wTop   :=wMiddle;
      END;
        // With 17 comparisons we can find any place in an index of 65536 values.
        // This compared with common sequential search of which may need up to 65536 comparisons in order to be 100% accurate.
        // This was Ultrafast on the old Commodore 64. It is Unbeaten in speed. The implementation of use is 'simple'.
        // This implementation of Binary Sorting Routine is Made by Morten Brendefur.
        // The use of bModifier is my own implementation that increases speed slightly.
      Doublecheck; // Results might be off by one. This fixes this issue.
    END;

  PROCEDURE InsertDataInIndex;
    VAR
      x,y : INTEGER;
    BEGIN
      IF wPosition>wMiddle THEN BEGIN
        y:=wIndex[wPosition];
        FOR x:=wPosition DOWNTO wMiddle+1 DO BEGIN
          wIndex[x]:=wIndex[x-1];
        END;
        wIndex[wMiddle]:=y;
      END;
      INC(wPosition);
    END;

  BEGIN
    BuildNeedSearches(16); // An implementation that might save some time on exhaustive searches.
    wPosition:=2;
    REPEAT
//      wTop:=1;
//      wBottom:=wPosition-1;
      wtop:=0;
      wBottom:=wPosition;
      FindPointOfInsert; // It is possible to save some CPU cycles by putting the procedures code directly here
      InsertDataInIndex; // I prefer to use procedures in a way to logically explain where and what is happening.
    UNTIL wPosition>TotalNumberOfDataToBeSorted;
  END;

In a total of 2 minutes and 11 seconds I am able to make an index of 256000 records, sort everything, and show my sorted data in one listbox and also show the index I created in another listbox.
.
.
Delphi 9
spend twice as long time in order to display the sorted data in only one listbox.
I left my comments in the source. They may make the code easier to understand.

I still wonder though. Is my sorting routine faster than ListBox or is there some other explanation for why the listbox is not visible for 4 minutes when I use the built in sort function/property.

If people are interrested in my routine of sorting, then please copy and experiment.
(I could add that I am working on another method in order to speed up my sorting by at least 180 times, still only using Delphi without inline assembler
I'll release that code here at a later stage when it has been fully tested.)

Best regards,
Morten Brendefur.

[Wolfgan]

Try this. I have not tested the speed. Just as an option.

procedure TForm1.Button1Click(Sender: TObject);
var List: TStringList;
begin
  List:=TStringList.Create;
    try
      List.Assign(ListBox1.Items);
      List.CustomSort(TStringsSort);
      ListBox1.Items.Assign(List);
    finally
      List.Free;
    end;
end;
function TStringsSort(List: TStringList; Index1, Index2: Integer): Integer;
begin
  Result:=-CompareStr(List[Index1],List[Index2]);
end

[TrustyTony]

I proved the first pieces of code in Lazarus environment for comparison. I made the Buttons to show the finishing times after execution of the function finished.

[TrustyTony]

For benchmark against Python see Python forum : http://www.daniweb.com/software-development/python/code/358672

[TrustyTony]

... And continuing with Jython running in JVM