It is currently Mon Dec 09, 2019 6:02 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 24 posts ]  Go to page Previous  1, 2
Author Message
 Post subject: Re: Custom sort for Linked Lists
PostPosted: Tue Jan 29, 2019 7:10 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Thu Mar 25, 2004 2:15 pm
Posts: 713
Location: Spain
Thank you very much :!: You saved my day. Really useful functions.

_________________
PB 5.7x, PureVision User.


Top
 Profile  
Reply with quote  
 Post subject: Re: Custom sort for Linked Lists
PostPosted: Tue Jan 29, 2019 7:54 am 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3715
Location: Berlin, Germany
Many thanks, Fred! :-)

zikitrake, I'm glad that the functions are useful for you.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Custom sort for Linked Lists
PostPosted: Thu Jan 31, 2019 7:10 am 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3715
Location: Berlin, Germany
New version 1.22, 2019-01-31

Changes
  • Simplified and improved the MergeSort routine, so that it's even faster now.
    As a consequence, the default value of sInsertionSortMaxSize was reduced from 50 to 35.
  • The procedure SetInsertionSortMaxSize() now returns the previous value of sInsertionSortMaxSize for convenience.
  • Some cosmetic changes.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Custom sort for Linked Lists
PostPosted: Thu Jan 31, 2019 9:08 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3543
Location: Netherlands
Did you consider using a (natural) bottom-up merge sort instead of top-down ?
Bottom-up is non-recursive.

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: Custom sort for Linked Lists
PostPosted: Thu Jan 31, 2019 11:20 am 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3715
Location: Berlin, Germany
wilbert wrote:
Did you consider using a (natural) bottom-up merge sort instead of top-down ?

Thanks for your suggestion!
Yes, I considered using a bottom-up merge sort. Comparing its speed with the speed of the existing version is on my ToDo list.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Custom sort for Linked Lists
PostPosted: Sat Mar 02, 2019 7:59 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3543
Location: Netherlands
Little John wrote:
Speed test

The following code demonstrates that the hybrid sorting algorithm is considerably faster than using self-written MergeSort alone. On my system, 35 is a good threshold value.

I got some strange results when I ran your speed test.
I found out it had to do with the copies of lists that you are using. Since they are located in different parts of memory, one list may be in a better place compared to another one.
When I changed your code so every test is done with the same list, the results were very different on my computer.
Code:
;-============  Structures  ============

Structure Person
  Idx.i
  Name.s
  Age.i
EndStructure


Procedure CreateRandomStructures (List x.Person(), n.i)
  Protected m$, a, i, r=Int(n/2)
 
  For i = 1 To r
    m$ = RandomString(Random(1000, 200))
    a = Random(80, 20)
   
    AddElement(x())
    x()\Idx = i*2 - 1
    x()\Name = m$
    x()\Age = a
   
    AddElement(x())
    x()\Idx = i*2
    x()\Name = m$
    x()\Age = a + 10
  Next
EndProcedure

Procedure.i ComparePersons (*pa.Integer, *pb.Integer, mode.i)
  ; -- custom comparison function of type 'ProtoCompare'
  ; in : *pa, *pb: pointers to pointers to structures to be compared
  ;      mode    : mode of comparison:
  ;                #PB_Sort_Ascending/#PB_Sort_Descending
  ; out: return value: #True/#False
  Protected.Person *a = *pa\i, *b = *pb\i     ; dereference the pointers passed as parameters
 
  If (mode & #PB_Sort_Descending)
    ProcedureReturn Bool(*a\Name < *b\Name)
  Else
    ProcedureReturn Bool(*a\Name > *b\Name)
  EndIf
EndProcedure


Define u0, u1, u2, u3, u4

NewList p0.Person()
CreateRandomStructures(p0(), n)

; --------------------------------------------------------------------------

threshold = 35

SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Idx), TypeOf(Person\Idx))
u0 = ElapsedMilliseconds()
SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Name), TypeOf(Person\Name))
u0 = ElapsedMilliseconds() - u0

SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Idx), TypeOf(Person\Idx))
CS::SetInsertionSortMaxSize(2 * threshold)
u1 = ElapsedMilliseconds()
CS::SortListAny(p0(), @ ComparePersons())
u1 = ElapsedMilliseconds() - u1

SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Idx), TypeOf(Person\Idx))
CS::SetInsertionSortMaxSize(threshold)
u2 = ElapsedMilliseconds()
CS::SortListAny(p0(), @ ComparePersons())
u2 = ElapsedMilliseconds() - u2

SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Idx), TypeOf(Person\Idx))
CS::SetInsertionSortMaxSize(0.5 * threshold)
u3 = ElapsedMilliseconds()
CS::SortListAny(p0(), @ ComparePersons())
u3 = ElapsedMilliseconds() - u3

SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Idx), TypeOf(Person\Idx))
CS::SetInsertionSortMaxSize(1)
u4 = ElapsedMilliseconds()
CS::SortListAny(p0(), @ ComparePersons())
u4 = ElapsedMilliseconds() - u4

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: Custom sort for Linked Lists
PostPosted: Sat Mar 02, 2019 10:27 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3715
Location: Berlin, Germany
Hi wilbert!

wilbert wrote:
I got some strange results when I ran your speed test.
I found out it had to do with the copies of lists that you are using. Since they are located in different parts of memory, one list may be in a better place compared to another one.

I wasn't aware of that problem. Thank you for your investigations!

Now I also did a speed test the way you proposed (with PB 5.70 x64 on Windows 10). Here is the complete executable code I used:
Code:
EnableExplicit

XIncludeFile "SortListCustom.pbi"

CompilerIf #PB_Compiler_Debugger
   MessageRequester("Error",
                    "Switch the Debugger off!",
                    #PB_MessageRequester_Error)
   End
CompilerEndIf


Procedure.s RandomString (length.i)
   Protected *char.Character, ret$=Space(length)
   
   *char = @ ret$
   While *char\c <> 0
      If Random(1) = 0
         *char\c = Random('Z', 'A')
      Else
         *char\c = Random('z', 'a')
      EndIf
      *char + SizeOf(Character)
   Wend
   
   ProcedureReturn ret$
EndProcedure


;-============  Structures  ============

Structure Person
  Idx.i
  Name.s
  Age.i
EndStructure


Procedure CreateRandomStructures (List x.Person(), n.i)
  Protected m$, a, i, r=Int(n/2)
 
  For i = 1 To r
    m$ = RandomString(Random(1000, 200))
    a = Random(80, 20)
   
    AddElement(x())
    x()\Idx = i*2 - 1
    x()\Name = m$
    x()\Age = a
   
    AddElement(x())
    x()\Idx = i*2
    x()\Name = m$
    x()\Age = a + 10
  Next
EndProcedure

Procedure.i ComparePersons (*pa.Integer, *pb.Integer, mode.i)
  ; -- custom comparison function of type 'ProtoCompare'
  ; in : *pa, *pb: pointers to pointers to structures to be compared
  ;      mode    : mode of comparison:
  ;                #PB_Sort_Ascending/#PB_Sort_Descending
  ; out: return value: #True/#False
  Protected.Person *a = *pa\i, *b = *pb\i     ; dereference the pointers passed as parameters
 
  If (mode & #PB_Sort_Descending)
    ProcedureReturn Bool(*a\Name < *b\Name)
  Else
    ProcedureReturn Bool(*a\Name > *b\Name)
  EndIf
EndProcedure


Define u0, u1, u2, u3, u4
Define msg$, threshold, n = 500000

NewList p0.Person()
CreateRandomStructures(p0(), n)

; --------------------------------------------------------------------------

threshold = 35

SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Idx), TypeOf(Person\Idx))
u0 = ElapsedMilliseconds()
SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Name), TypeOf(Person\Name))
u0 = ElapsedMilliseconds() - u0

SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Idx), TypeOf(Person\Idx))
CS::SetInsertionSortMaxSize(2 * threshold)
u1 = ElapsedMilliseconds()
CS::SortListAny(p0(), @ ComparePersons())
u1 = ElapsedMilliseconds() - u1

SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Idx), TypeOf(Person\Idx))
CS::SetInsertionSortMaxSize(threshold)
u2 = ElapsedMilliseconds()
CS::SortListAny(p0(), @ ComparePersons())
u2 = ElapsedMilliseconds() - u2

SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Idx), TypeOf(Person\Idx))
CS::SetInsertionSortMaxSize(0.5 * threshold)
u3 = ElapsedMilliseconds()
CS::SortListAny(p0(), @ ComparePersons())
u3 = ElapsedMilliseconds() - u3

SortStructuredList(p0(), #PB_Sort_Ascending, OffsetOf(Person\Idx), TypeOf(Person\Idx))
CS::SetInsertionSortMaxSize(1)
u4 = ElapsedMilliseconds()
CS::SortListAny(p0(), @ ComparePersons())
u4 = ElapsedMilliseconds() - u4

; --------------------------------------------------------------------------

msg$ + "-- Sorting structures" + #LF$ +
       "u0 = " + StrD(u0/1000,3) + " Sec. (built-in MergeSort)" + #LF$ +
       "u1 = " + StrD(u1/1000,3) + " Sec."   + #LF$ +
       "u2 = " + StrD(u2/1000,3) + " Sec. <" + #LF$ +
       "u3 = " + StrD(u3/1000,3) + " Sec."   + #LF$ +
       "u4 = " + StrD(u4/1000,3) + " Sec. (self-written MergeSort alone)"

MessageRequester("Duration", msg$)


wilbert wrote:
When I changed your code so every test is done with the same list, the results were very different on my computer.

Here are the results on my system with both methods.
Results of my original test wrote:
-- Sorting structures
u0 = 0.396 Sec. (built-in MergeSort)
u1 = 1.214 Sec.
u2 = 1.177 Sec. <
u3 = 1.197 Sec.
u4 = 2.679 Sec. (self-written MergeSort alone)

Results of your test wrote:
-- Sorting structures
u0 = 0.424 Sec. (built-in MergeSort)
u1 = 1.221 Sec.
u2 = 1.198 Sec. <
u3 = 1.234 Sec.
u4 = 2.742 Sec. (self-written MergeSort alone)

The results are pretty similar. Especially using the proposed threshold (u2) is with both methods faster than using a bigger threshold (u1) or a smaller one (u3).

What are the results that you get on macOS with both my original and your new method?

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Custom sort for Linked Lists
PostPosted: Sun Mar 03, 2019 6:55 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3543
Location: Netherlands
Your original code.
Quote:
-- Sorting strings
t0 = 0.667 Sec. (built-in MergeSort)
t1 = 2.530 Sec.
t2 = 2.249 Sec. <
t3 = 1.612 Sec.
t4 = 1.829 Sec. (self-written MergeSort alone)

-- Sorting structures
u0 = 3.444 Sec. (built-in MergeSort)
u1 = 1.913 Sec.
u2 = 1.844 Sec. <
u3 = 1.807 Sec.
u4 = 2.197 Sec. (self-written MergeSort alone)


The changed version
Quote:
-- Sorting structures
u0 = 0.383 Sec. (built-in MergeSort)
u1 = 1.105 Sec.
u2 = 1.050 Sec. <
u3 = 1.034 Sec.
u4 = 1.255 Sec. (self-written MergeSort alone)


A PB linked list is a chain of small parts of allocated memory.
What I suspect is that when using different lists, for some lists, the assigned memory is more fragmented compared to other lists.
If you have to jump around in memory to do comparisons, this might make a significant difference.
That's the only explanation I can think of :?

The string sorting benchmark might also suffer from this but I wouldn't know how to restore that list to its original presorted order in that case.

Edit:
After some more thinking ...
Modern versions of MacOS can use memory compression.
So another possibility could be that all the duplicated lists of the original version take up so much memory that the OS decides to compress the memory.

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: Custom sort for Linked Lists
PostPosted: Sun Mar 03, 2019 1:08 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3715
Location: Berlin, Germany
wilbert wrote:
Your original code.
Quote:
[...]

-- Sorting structures
u0 = 3.444 Sec. (built-in MergeSort)
u1 = 1.913 Sec.
u2 = 1.844 Sec. <
u3 = 1.807 Sec.
u4 = 2.197 Sec. (self-written MergeSort alone)

This is really strange. It looks as if the built-in routine were the slowest one. :D
In contrast, the results of your changed version make sense.

I have run my original speed test rather often (but only on Windows), and always got consistent results. So I think the main cause of the strange results that you encountered might be the different memory handling of Windows and MacOS.

I've changed now my original benchmark code, also for sorting the string lists. (I'm storing the order of the elements in a list of pointers, and use the pointers for rearranging the elements of the string list before each new speed test.)

Thanks again for finding this issue and reporting it!

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 24 posts ]  Go to page Previous  1, 2

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye