Optimization of a sorting algorithm

[Olli]

I think Yuki shew the tip !
8 elements =
8 hashes in the map.
+8 tests.
List is sorted (without really having the referencies sorted, but the links are in the wanted order)

I would to add anything again, but I am very busy fo any weeks. Possible I will be back ! Very cool to compare speedness of algos.

Note that your request is very interesting in the sense it could applied in other domains (files system, ...)


Ref = REFerency to which the entry points.
Crt = CuRrent element of the entry list.
Hnd = boolean HaNDling status which starts when a referency has been detected, without the entry it points is done. And status which ends when a moved entry has no referency.
Alpha = points the current element when the handling starts
Beta = points the current element when the handling will ends

If it was a files system,
Ref is the address of the direct parent directory of the current file.
Crt is the current file tested.
Hnd translates the moves period of each directory from the file directory, to the root directory.
Alpha is the identifier of the file/directory which demands to search its parents directories to the root.
beta is the nearest directory, before reach the root.

This algo is very interesting. And I thank Yuki for the standard vocabulary !

(And sorry for my own very wild vocabulary...)

[Kurzer]

LOL - Irony of fate.

Now I have integrated the sorting algorithm V3 into my module and.... now I accidentally created a gadget list constellation that doesn't sort correctly. (where is the smiliey with the caneval stream?)

So everything from the beginning and start over. With multiple, iterative references the algorithm has problems.

[23:25:58] [Debug] Gadget 0: button nothing, RefGadget: , SortValue: 0
[23:25:58] [Debug] Gadget 1: button settings, RefGadget: , SortValue: 1000
[23:25:58] [Debug] Gadget 2: test button, RefGadget: button settings, SortValue: 1001
[23:25:58] [Debug] Gadget 3: editor, RefGadget: , SortValue: 2000
[23:25:58] [Debug] Gadget 4: test2 button, RefGadget: editor, SortValue: 2001
[23:25:58] [Debug] Gadget 5: button info, RefGadget: editor, SortValue: 2001
[23:25:58] [Debug] Gadget 6: button exit, RefGadget: , SortValue: 3000
[23:25:58] [Debug] Gadget 7: button show data, RefGadget: button clr data, SortValue: 5000 <-----------
[23:25:58] [Debug] Gadget 8: button show gad, RefGadget: button show data, SortValue: 5001
[23:25:58] [Debug] Gadget 9: button show ini, RefGadget: button show gad, SortValue: 5002
[23:25:58] [Debug] Gadget 10: button set data, RefGadget: button info, SortValue: 7000
[23:25:58] [Debug] Gadget 11: button clr data, RefGadget: button set data, SortValue: 7001 <-----------

[Olli]

Do not worry... I am there
Plus, Yuki certainly will check his code.
Plus, Wilbert has not said anything, until now. He strikes a bit like lightning. He is not close to 100 meters, to... make several impacts simultaneously!

Structure header

Code: Select all

Structure entry
 name.s ; <-- added
 value.i
 *ref
 refName.s ; <--- added
 done.i
EndStructure

; >>> Added 
Structure entries 
 Map *key(8192)
EndStructure
; Added ^^^

Structure entryList
 List e.entry()
  *m ; <--- added
EndStructure

Procedure entryListCreate()
 Protected *this.entryList = AllocateMemory(SizeOf(entryList) )
 InitializeStructure(*this, entryList)
 ProcedureReturn *this
EndProcedure

Procedure entryListResetTheDones(*this.entryList);<--adds
 With *this\e()
  ForEach(*this\e() )
   \Done = 0
  Next
 EndWith
EndProcedure

Procedure entryListCreateMap(*this.entryList); <--- adds
 Protected *that.entries
 With *this
  \m = AllocateMemory(SizeOf(entries) )
  InitializeStructure(\m, entries)
  *that = \m
  ForEach \e()
   *that\key(\name) = \e()
  Next
 EndWith
EndProcedure

Procedure entryListDestroyMap(*this.entryList); <--- adds
 ClearStructure(*this\m, entries)
 FreeMemory(*this\m)
 *this\m = 0
EndProcedure

Procedure entryListAdd(*this.entryList, name.s, value.i, refName.s) ; adds
 With *this
  \name = name
  \value = value
  \refName = refName
 EndWith
EndProcedure

Procedure entryListSortLinks(*this.entryList)
 Protected *that.entries ; <--- Added
 Protected hnd ; HaNDling status flag
 Protected alpha, beta ; pointers
 With *this\e()
  entryListResetTheDones(*this) ; <--- Added
  entryListCreateMap(*this) ; <--- Added
  *that = *this\m ; <--- Added
  FirstElement(*this\e() )
  Repeat
   If \ref
    If hnd = 0
     alpha = *this\e()
     hnd = 1
    EndIf
    beta = *this\e()
    \done = 1
    \ref = *that\key(\refName) ; <--- Added
    ChangeCurrentElement(*this\e(), \ref)
    If \done
     ChangeCurrentElement(*this\e(), beta)
     \done = 1
    Else
     MoveElement(*this\e(), #PB_List_Before, beta)
     \done = 1
     PreviousElement(*this\e() ) ; "Continue" statement cannot bypass "Until" test ! Forced to go back ! ! !
     Continue
    EndIf
   Else
    If hnd
     hnd = 0
     ChangeCurrentElement(*this\e(), alpha)
    EndIf
    \done = 1
   EndIf
  Until NextElement(*this\e() ) = 0
  entryListDestroyMap(*this) ; <--- Added
 EndWith
EndProcedure

[yuki]

Now I have integrated the sorting algorithm V3 into my module and.... now I accidentally created a gadget list constellation that doesn't sort correctly. (where is the smiliey with the caneval stream?)

So everything from the beginning and start over. With multiple, iterative references the algorithm has problems.

I've prepared V4 and V5 sorts that can be used as simple, drop-in replacements for V3 (no structure changes/DAG complexity):

Code: Select all

Procedure SortList_V5()
  Static NewMap seenOrderMap.i(2048)
  Static Dim *pendingEntries.MyStruct(0)
  
  Protected *currentEntry.MyStruct
  Protected pendingCount, parentOrder, x, xLim
  Protected entryCount = ListSize(StructList())
  
  ; Reset known orders from a prior sort operation
  ClearMap(seenOrderMap())
  ; Resize pending array to accommodate entries. Could make this more dynamic and/or a factor
  ; of the entry count to reduce reallocs.
  If ArraySize(*pendingEntries()) < entryCount
    ReDim *pendingEntries(entryCount)
  EndIf
  
  ; Iterate over elements in order to assign those without a parent/ref a sort order which
  ; clearly represents their being on effectively the first layer of our tree.
  ; All other elements will be stored in a pending array in order to be later grouped under
  ; known elements.
  ForEach StructList()
    If StructList()\RefEntry = ""
      StructList()\Sort = 1
      seenOrderMap(StructList()\Entry) = 1
    Else
      *pendingEntries(pendingCount) = StructList()
      pendingCount + 1
    EndIf
  Next
  
  ; Continue scanning elements so long as we've some which haven't been associated with a
  ; proper sort order.
  While pendingCount
    ; Store number of elements to iterate over before resetting pending count.
    xLim = pendingCount - 1
    pendingCount = 0
    For x = 0 To xLim
      *currentEntry = *pendingEntries(x)
      parentOrder = seenOrderMap(*currentEntry\RefEntry)
      If parentOrder
        ; Element has at last been assigned an order.
        *currentEntry\Sort = parentOrder + 1
        seenOrderMap(*currentEntry\Entry) = parentOrder + 1
      Else
        ; Element must go back to the pending pool.
        *pendingEntries(pendingCount) = *currentEntry
        pendingCount + 1
      EndIf
    Next
    ; In cases where the pending count is non-zero and hasn't changed, we've certainly a
    ; cycle present. Trigger a debugger error and bail if not debugging.
    If pendingCount = xLim + 1
      DebuggerError("Your hierarchy has held cycles!")
      Break
    EndIf
  Wend
  
  SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\Sort), TypeOf(MyStruct\Sort))
EndProcedure

Procedure SortList_V4()
  Protected numAssignedInCurrentPass
  Protected *parent.MyStruct
  Static NewMap *handledOrderMap.MyStruct(4096)
  
  ClearMap(*handledOrderMap())
  
  ; Find all elements on the first layer of tree (without parent/ref) and store them in
  ; our known-order map while assigning depth (\Sort) 1.
  ; All other elements will be assigned depth (\Sort) 0.
  ForEach StructList()
    If StructList()\RefEntry = ""
      StructList()\Sort = 1
      *handledOrderMap(StructList()\Entry) = StructList()
    Else
      StructList()\Sort = 0
    EndIf
  Next
  
  ; Repeatedly scan the list searching for elements yet-to-be assigned a non-zero depth (\Sort)
  ; value, while assigning such once if we've handled their parent/ref.
  ; The scanning process stops whenever we are no longer able to assign a single depth value
  ; in a single pass. This should only happen when complete OR running into cycles.
  Repeat
    numAssignedInCurrentPass = 0
    ForEach StructList()
      If Not StructList()\Sort
        *parent = *handledOrderMap(StructList()\RefEntry)
        If *parent
          StructList()\Sort = *parent\Sort + 1
          *handledOrderMap(StructList()\Entry) = StructList()
          numAssignedInCurrentPass + 1
        EndIf
      EndIf
    Next
  Until Not numAssignedInCurrentPass
  
  SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\Sort), TypeOf(MyStruct\Sort))
EndProcedure

The Global StructMap.MyStruct() is no longer needed, so initialisation can become slightly cheaper if you don't require that for other purposes.

Hierarchy seems OK:

Code: Select all

═══════════════════════ V4/V5 ═══════════════════════
|  #  |       Name       |        Ref        | Sort |
|-----|------------------|-------------------|------|
|   0 | button nothing   |                   |    1 |
|   1 | button settings  |                   |    1 |
|   2 | editor           |                   |    1 |
|   3 | button exit      |                   |    1 |
|   4 | test button      | button settings   |    2 |
|   5 | test2 button     | editor            |    2 |
|   6 | button info      | editor            |    2 |
|   7 | button set data  | button info       |    3 |
|   8 | button clr data  | button set data   |    4 |
|   9 | button show data | button clr data   |    5 |
|  10 | button show gad  | button show data  |    6 |
|  11 | button show ini  | button show gad   |    7 |

═══════════════════════  DAG  ═══════════════════════
    button exit
    editor
        button info
            button set data
                button clr data
                    button show data
                        button show gad
                            button show ini
        test2 button
    button settings
        test button
    button nothing

Timing (1000 items test) (PB 6.02 LTS, Windows 11 x64, 5800X, No Optimiser):

Code: Select all

| Method | ASM Debug | ASM Release | C Debug | C Release |
|--------|-----------|-------------|---------|-----------|
|   V1   |   16052μs |      2505μs |  6541μs |    2514μs |
|   V2   |    6486μs |      1106μs |  2959μs |    1093μs |
|   V3   |     320μs |       190μs |   237μs |     189μs |
|   V4   |     360μs |       138μs |   233μs |     131μs |
|   V5   |     262μs |       129μs |   197μs |     127μs |
|  LDAG  |     182μs |        34μs |    95μs |      35μs |
|  ADAG  |     160μs |         5μs |    56μs |       5μs |

V4 is equal or better in debug-mode with the C-backend, and only a little slower in ASM-backend with debugger, while coming in ahead when the debugger is off.

V5 is fastest (aside DAG) regardless debugger on/off state here.

DAG comes out far ahead here (esp. debugger off), but isn't exactly a drop-in replacement for the sorting methods.

(And sorry for my own very wild vocabulary...)

If I don't apologise for my monotonous technical ramblings (I did it too much and got stuck talking this way ), then I don't think you should apologise for your approach either

(IMO, not knowing/caring for the vocab can be more useful, since it leads to real innovation)

Edit 1: formatted time measurements into table to take up less space and simplify reading.
Edit 2: added V5 which beats prior approaches regardless of debugger on/off state. formatted sort outputs into table.
Edit 3: added DAG timings. (LDAG/ADAG = copy DAG to flat list/array) (N.B. you can instead skip copy and render straight from DAG walking)
Edit 4: clarify text. (last edit!)

[Olli]

I taped the code from my smartphone : if there is no bug, there could be a V5 to be sure there is innovation, but I am not sure : we should be on the same algo, as prime number miner, there are not lots of algos.

template example (should be like that) :

Code: Select all

*z.entryList = entryListCreate()
entryListAdd(*z, "Ok button", 3000, "Esc button")
; ...
entryListSortLinks(*z)

ForEach *z\e()
 Debug *z\name + Chr(9) + *z\ref
Next

@kurzer

Instead of using "value" integer, you should use "value" bits.
And, now I understand why Wilbert talks about indexed maps : because the names, you need them to sort the hierarchy, on one kind, and because the names are also used as a map to reduce the memory allocating, and reduce the treatment time, depending of which link type is treating.

[Kurzer]

Yuki and Olli,

thank you very much for your immense cooperation and the effort you have made.

I'll have to wait until tomorrow to take a closer look at everything. In any case, it's really great that you (Yuki) have implemented your V4 and V5 solutions as a procedure that can be directly integrated into the test framework. Great.

I will also convert my testframework here to PrintN() outputs to be able to do the measurements without the debugger.

Then tomorrow I will look at the V4 and V5 solutions in detail. I want to understand the solutions, not just copy them. This is also my personal requirement.

Thank you both for your efforts. I will report, how it goes on with my module and whether I possibly entangle myself again in curious sorting results. LOL

Edit:
I have now rebuilt the test framework and have also rearranged the init() procedure to use the same gadgets and references model where my V3 algorithm failed within the "WinHandler module".

Yuki, but in doing so I noticed that your V4 does the sorting fine, but V5 displays a "DebuggerError("Your hierarchy has held cycles!")" which, in my opinion, is not present.

Here again my testframewiork, maybe I missed something in the hurry.... I'm about to leave my office now, it's already way too late to be at work

I will do everything else tomorrow.
See you... and thanks again!

(the code is corrected in the meantime, see Edit2 below).

Code: Select all

EnableExplicit

Structure MyStruct
	Entry.s
	RefEntry.s
	Sort.i
EndStructure

Global NewList StructList.MyStruct()
Global NewMap StructMap.MyStruct()
Define i, StartTime, Duration

OpenConsole()
ConsoleTitle ("Sorting")
EnableGraphicalConsole(1)

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

; Procedure for high resolution time measurement, thanks go to Axolotl
; https://www.purebasic.fr/english/viewtopic.php?p=589086#p589086
Procedure.i ElapsedMicroseconds()
	Static frequency.q
	Protected count.q
	
	If frequency = 0 
		If QueryPerformanceFrequency_(@frequency)
			; frequency / 10000      ; .. divide frequency by 10000 for tenths of a millisecond 
			; frequency / 1000   		 ;:: in milli seconds 
			; frequency / 1000   		 ;:: in micro seconds 
			frequency / 1000000      ;:: in micro seconds 
		EndIf 
	EndIf
	
	If QueryPerformanceCounter_(@count)
		ProcedureReturn count / frequency 
	Else
		ProcedureReturn 0
	EndIf 
EndProcedure 

; The sorting procedures
Procedure Sortlist_V1()
	Protected i, j, SearchStart = 0, SearchEnd = ListSize(StructList()) - 1, *Entry
	Protected.s RefEntry
	
	For i = SearchStart To SearchEnd - 1
		SelectElement(StructList(), i)
		If StructList()\RefEntry <> ""
			*Entry = @StructList()
			RefEntry = StructList()\RefEntry
			For j = i + 1 To SearchEnd
				SelectElement(StructList(), j)
				If StructList()\Entry = RefEntry
					If StructList()\RefEntry <> ""
						i - 1
					EndIf
					MoveElement(StructList(), #PB_List_Before, *Entry)
					Break
				EndIf
			Next
		EndIf
	Next	
EndProcedure
Procedure Sortlist_V2()
	Protected i, j, SkipEntries, SearchStart = 0, SearchEnd = ListSize(StructList()) - 1, *Entry
	Protected.s RefEntry
	
	For i = SearchStart To SearchEnd - 1
		SelectElement(StructList(), i)
		If StructList()\RefEntry <> ""
			*Entry = @StructList()
			RefEntry = StructList()\RefEntry
			For j = i + 1 To SearchEnd
				SelectElement(StructList(), j)
				If StructList()\Entry = RefEntry
					If StructList()\RefEntry <> ""
						i - 1
						SkipEntries + 1
					Else	
						i + SkipEntries
						SkipEntries = 1
					EndIf
					MoveElement(StructList(), #PB_List_Before, *Entry)
					Break
				EndIf
			Next
		EndIf
	Next
EndProcedure
Procedure SortList_V3()
	Protected Sortvalue = 0	
	#Blocksize = 1000
	; We work through the list from beginning to end using the following logic:
	
	; 1) We sort the list in ascending order by RefEntry, so that all entries without RefEntry are at the beginning
	; 2) We go through the list once from beginning to end to get the sorted element names
	;    These represent the keys of the identical map. In this loop, only the entries of the map are processed.
	;    a) If the map entry does *not* reference any other entry and field sort = 0: 
	;       - The map entry gets in the field Sort = Sortvalue
	;       - Sortvalue = Sortvalue + #Blocksize (1000)
	;    b) If the map entry *does* reference any other entry:
	;       - If the referenced entry in the map has no Sortvalue yet:
	;         - The referenced map entry gets in the field Sort = Sortvalue
	;         - Sortvalue = Sortvalue + #Blocksize (1000)
	;         - After this:
	;           - If the map entry referencing the other element does not yet have a Sortvalue:
	;             - The map entry gets in the field Sort = Sortvalue
	;             - Sortvalue = Sortvalue + #Blocksize (1000)
	;       c) If the referenced(!) entry in the map already has a sortvalue:
	;            - The entry that references it gets the Sortvalue + 1 from the referenced entry 
	;            - Sortvalue = Sortvalue + #Blocksize (1000)
	; 3) We sort the list in ascending order by the field sort
	
	; 1)
	SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\RefEntry), TypeOf(MyStruct\RefEntry))
	
	With StructList()
		; 2)
		ForEach StructList()
			; 2b)
			If \RefEntry <> ""
				If StructMap(\RefEntry)\Sort = 0
					StructMap(\RefEntry)\Sort = Sortvalue
					Sortvalue + #Blocksize
					If StructMap(\Entry)\Sort = 0
						StructMap(\Entry)\Sort = Sortvalue
						Sortvalue + #Blocksize
					EndIf
					; 2c)
				Else
					StructMap(\Entry)\Sort = StructMap(\RefEntry)\Sort + 1
					Sortvalue + #Blocksize
				EndIf
				; 2a)	
			ElseIf StructMap(\Entry)\Sort = 0
				StructMap(\Entry)\Sort = Sortvalue
				Sortvalue + #Blocksize
			EndIf
		Next
		
		ForEach StructList()
			\Sort = StructMap(\Entry)\Sort
		Next	
	EndWith
	
	; 3)
	SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\Sort), TypeOf(MyStruct\Sort))
	
EndProcedure
Procedure SortList_V4()
	Protected numAssignedInCurrentPass
	Protected *parent.MyStruct
	Static NewMap *handledOrderMap.MyStruct(4096)
	
	ClearMap(*handledOrderMap())
	
	; Find all elements on the first layer of tree (without parent/ref) and store them in
	; our known-order map while assigning depth (\Sort) 1.
	; All other elements will be assigned depth (\Sort) 0.
	ForEach StructList()
		If StructList()\RefEntry = ""
			StructList()\Sort = 1
			*handledOrderMap(StructList()\Entry) = StructList()
		Else
			StructList()\Sort = 0
		EndIf
	Next
	
	; Repeatedly scan the list searching for elements yet-to-be assigned a non-zero depth (\Sort)
	; value, while assigning such once if we've handled their parent/ref.
	; The scanning process stops whenever we are no longer able to assign a single depth value
	; in a single pass. This should only happen when complete OR running into cycles.
	Repeat
		numAssignedInCurrentPass = 0
		ForEach StructList()
			If Not StructList()\Sort
				*parent = *handledOrderMap(StructList()\RefEntry)
				If *parent
					StructList()\Sort = *parent\Sort + 1
					*handledOrderMap(StructList()\Entry) = StructList()
					numAssignedInCurrentPass + 1
				EndIf
			EndIf
		Next
	Until Not numAssignedInCurrentPass
	
	SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\Sort), TypeOf(MyStruct\Sort))
EndProcedure
Procedure SortList_V5()
	Static NewMap seenOrderMap.i(2048)
	Static Dim *pendingEntries.MyStruct(0)
	
	Protected *currentEntry.MyStruct
	Protected pendingCount, parentOrder, x, xLim
	Protected entryCount = ListSize(StructList())
	
	; Reset known orders from a prior sort operation
	ClearMap(seenOrderMap())
	; Resize pending array to accommodate entries. Could make this more dynamic and/or a factor
	; of the entry count to reduce reallocs.
	If ArraySize(*pendingEntries()) < entryCount
		ReDim *pendingEntries(entryCount)
	EndIf
	
	; Iterate over elements in order to assign those without a parent/ref a sort order which
	; clearly represents their being on effectively the first layer of our tree.
	; All other elements will be stored in a pending array in order to be later grouped under
	; known elements.
	ForEach StructList()
		If StructList()\RefEntry = ""
			StructList()\Sort = 1
			seenOrderMap(StructList()\Entry) = 1
		Else
			*pendingEntries(pendingCount) = StructList()
			pendingCount + 1
		EndIf
	Next
	
	; Continue scanning elements so long as we've some which haven't been associated with a
	; proper sort order.
	While pendingCount
		; Store number of elements to iterate over before resetting pending count.
		xLim = pendingCount - 1
		pendingCount = 0
		For x = 0 To xLim
			*currentEntry = *pendingEntries(x)
			parentOrder = seenOrderMap(*currentEntry\RefEntry)
			If parentOrder
				; Element has at last been assigned an order.
				*currentEntry\Sort = parentOrder + 1
				seenOrderMap(*currentEntry\Entry) = parentOrder + 1
			Else
				; Element must go back to the pending pool.
				*pendingEntries(pendingCount) = *currentEntry
				pendingCount + 1
			EndIf
		Next
		; In cases where the pending count is non-zero and hasn't changed, we've certainly a
		; cycle present. Trigger a debugger error and bail if not debugging.
		If pendingCount = xLim + 1
			DebuggerError("Your hierarchy has held cycles!")
			Break
		EndIf
	Wend
	
	SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\Sort), TypeOf(MyStruct\Sort))
EndProcedure

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

; Initializing the list and map
Procedure Init()
	Protected  i
	ClearList(StructList())
	ClearMap(StructMap())
	
	; We create a list of n entries to get enough runtime for a time measurement.
	For i = 1 To 1 Step 1
		AddElement(StructList()) : StructList()\Entry = "button nothing_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "test button_" + Str(i) : StructList()\RefEntry = "button settings_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "test2 button_" + Str(i) : StructList()\RefEntry = "editor_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "button settings_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "editor_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "button info_" + Str(i) : StructList()\RefEntry = "editor_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "button set data_" + Str(i) : StructList()\RefEntry = "button info_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "button clr data_" + Str(i) : StructList()\RefEntry = "button set data_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "button show data_" + Str(i) : StructList()\RefEntry = "button clr data_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "button show gad_" + Str(i) : StructList()\RefEntry = "button show data_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "button show ini_" + Str(i) : StructList()\RefEntry = "button show gad_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "button exit_" + Str(i)
	Next i
	
	; Now we create a map with the same content as the list
	ForEach StructList()
		StructMap(StructList()\Entry)\Entry =StructList()\Entry
		StructMap(StructList()\Entry)\RefEntry =StructList()\RefEntry
	Next
	
	; All steps up to here can be realized in my use case by the code area responsible for registering a gadget in my module.
	; Therefore this code part must not be included in the time measurement.
EndProcedure

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

Procedure PrintList(Title.s = "", MaxEntries.i = 32)
	Protected.i i	
	
	PrintN(Title)
	PrintN(".═════+════════════════════════+════════════════════════+══════════.")
	PrintN("|  #  |          Name          |           Ref          |   Sort   |")
	PrintN("|-----|------------------------|------------------------|----------|")
	
	ForEach StructList()
		If i < MaxEntries
			PrintN("|" + RSet(Str(i) + " ", 5) + "| " + LSet(StructList()\Entry, 23) + "| " + LSet(StructList()\RefEntry, 23) + "| " + LSet(Str(StructList()\Sort), 9) + "|")
			i + 1
		EndIf
	Next
EndProcedure

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

; START

Init()

PrintList("UNSORTED LIST")
PrintN("")

If 1=1
	Init()
	StartTime = ElapsedMicroseconds()
	SortList_V1()
	Duration = ElapsedMicroseconds() - StartTime
	PrintN(""): PrintN("")
	PrintList("V1 Algorithm: " + Str(Duration) + " microseconds.")	
EndIf

If 1=1
	Init()
	StartTime = ElapsedMicroseconds()
	SortList_V2()
	Duration = ElapsedMicroseconds() - StartTime
	PrintN(""): PrintN("")
	PrintList("V2 Algorithm: " + Str(Duration) + " microseconds.")	
EndIf

If 1=1
	Init()
	StartTime = ElapsedMicroseconds()
	SortList_V3()
	Duration = ElapsedMicroseconds() - StartTime
	PrintN(""): PrintN("")
	PrintList("V3 Algorithm: " + Str(Duration) + " microseconds.")	
EndIf

If 1=1
	Init()
	StartTime = ElapsedMicroseconds()
	SortList_V4()
	Duration = ElapsedMicroseconds() - StartTime
	PrintN(""): PrintN("")
	PrintList("V4 Algorithm: " + Str(Duration) + " microseconds.")	
EndIf

If 1=1
	Init()
	StartTime = ElapsedMicroseconds()
	SortList_V5()
	Duration = ElapsedMicroseconds() - StartTime
	PrintN(""): PrintN("")
	PrintList("V5 Algorithm: " + Str(Duration) + " microseconds.")	
EndIf

PrintN("")
Print("Press any key to exit")
Input()

Code: Select all

UNSORTED LIST
.═════+════════════════════════+════════════════════════+══════════.
|  #  |          Name          |           Ref          |   Sort   |
|-----|------------------------|------------------------|----------|
|   0 | button nothing_1       |                        | 0        |
|   1 | test button_1          | button settings_1      | 0        |
|   2 | test2 button_1         | editor_1               | 0        |
|   3 | button settings_1      |                        | 0        |
|   4 | editor_1               |                        | 0        |
|   5 | button info_1          | editor_1               | 0        |
|   6 | button set data_1      | button info_1          | 0        |
|   7 | button clr data_1      | button set data_1      | 0        |
|   8 | button show data_1     | button clr data_1      | 0        |
|   9 | button show gad_1      | button show data_1     | 0        |
|  10 | button show ini_1      | button show gad_1      | 0        |
|  11 | button exit_1          |                        | 0        |



V1 Algorithm: 6 microseconds.
.═════+════════════════════════+════════════════════════+══════════.
|  #  |          Name          |           Ref          |   Sort   |
|-----|------------------------|------------------------|----------|
|   0 | button nothing_1       |                        | 0        |
|   1 | button settings_1      |                        | 0        |
|   2 | test button_1          | button settings_1      | 0        |
|   3 | editor_1               |                        | 0        |
|   4 | test2 button_1         | editor_1               | 0        |
|   5 | button info_1          | editor_1               | 0        |
|   6 | button set data_1      | button info_1          | 0        |
|   7 | button clr data_1      | button set data_1      | 0        |
|   8 | button show data_1     | button clr data_1      | 0        |
|   9 | button show gad_1      | button show data_1     | 0        |
|  10 | button show ini_1      | button show gad_1      | 0        |
|  11 | button exit_1          |                        | 0        |


V2 Algorithm: 4 microseconds.
.═════+════════════════════════+════════════════════════+══════════.
|  #  |          Name          |           Ref          |   Sort   |
|-----|------------------------|------------------------|----------|
|   0 | button nothing_1       |                        | 0        |
|   1 | button settings_1      |                        | 0        |
|   2 | test button_1          | button settings_1      | 0        |
|   3 | editor_1               |                        | 0        |
|   4 | test2 button_1         | editor_1               | 0        |
|   5 | button info_1          | editor_1               | 0        |
|   6 | button set data_1      | button info_1          | 0        |
|   7 | button clr data_1      | button set data_1      | 0        |
|   8 | button show data_1     | button clr data_1      | 0        |
|   9 | button show gad_1      | button show data_1     | 0        |
|  10 | button show ini_1      | button show gad_1      | 0        |
|  11 | button exit_1          |                        | 0        |


V3 Algorithm: 7 microseconds.
.═════+════════════════════════+════════════════════════+══════════.
|  #  |          Name          |           Ref          |   Sort   |
|-----|------------------------|------------------------|----------|
|   0 | button nothing_1       |                        | 0        |
|   1 | button settings_1      |                        | 1000     |
|   2 | test button_1          | button settings_1      | 1001     |
|   3 | editor_1               |                        | 2000     |
|   4 | test2 button_1         | editor_1               | 2001     |
|   5 | button info_1          | editor_1               | 2001     |
|   6 | button exit_1          |                        | 3000     |
|   7 | button show data_1     | button clr data_1      | 5000     |
|   8 | button show gad_1      | button show data_1     | 5001     |
|   9 | button show ini_1      | button show gad_1      | 5002     |
|  10 | button set data_1      | button info_1          | 7000     |
|  11 | button clr data_1      | button set data_1      | 7001     |


V4 Algorithm: 140 microseconds.
.═════+════════════════════════+════════════════════════+══════════.
|  #  |          Name          |           Ref          |   Sort   |
|-----|------------------------|------------------------|----------|
|   0 | button nothing_1       |                        | 1        |
|   1 | button settings_1      |                        | 1        |
|   2 | editor_1               |                        | 1        |
|   3 | button exit_1          |                        | 1        |
|   4 | test button_1          | button settings_1      | 2        |
|   5 | test2 button_1         | editor_1               | 2        |
|   6 | button info_1          | editor_1               | 2        |
|   7 | button set data_1      | button info_1          | 3        |
|   8 | button clr data_1      | button set data_1      | 4        |
|   9 | button show data_1     | button clr data_1      | 5        |
|  10 | button show gad_1      | button show data_1     | 6        |
|  11 | button show ini_1      | button show gad_1      | 7        |


V5 Algorithm: 12 microseconds.
.═════+════════════════════════+════════════════════════+══════════.
|  #  |          Name          |           Ref          |   Sort   |
|-----|------------------------|------------------------|----------|
|   0 | button nothing_1       |                        | 1        |
|   1 | button settings_1      |                        | 1        |
|   2 | editor_1               |                        | 1        |
|   3 | button exit_1          |                        | 1        |
|   4 | test button_1          | button settings_1      | 2        |
|   5 | test2 button_1         | editor_1               | 2        |
|   6 | button info_1          | editor_1               | 2        |
|   7 | button set data_1      | button info_1          | 3        |
|   8 | button clr data_1      | button set data_1      | 4        |
|   9 | button show data_1     | button clr data_1      | 5        |
|  10 | button show gad_1      | button show data_1     | 6        |
|  11 | button show ini_1      | button show gad_1      | 7        |

Press any key to exit

Edit2:
I have now fixed my error that I mentioned here.
All sorting algorithms now work properly.

Yuki, I will adapt your last V5 version to my needs and then I can finally continue with the programming of the module. - Unfortunately I didn't get around to it the last days.

[Olli]

As I was not on computer, Yuki has done 99% of the work.

[Kurzer]

Found the Problem.... but I am watching my code at the phone.

In my example the ref Button "button setting_x" must be named "button settings_x". I forgot the "s". will fix it tomorrow and check the code.

wohaaa, I'll kill my german autocorrection.... typed every Word three Times.

[Olli]

This story of 's' letter is a problem, in France, U.K. and USA.

one object : étiquette
sticker
any object : étiquettes
stickers

I often made bugs from this 's' letter...

So, to prevent me from making a bug, I change the whole word :
example : "settings" becomes "configuration" or "config"

Everything remains singular.

[yuki]

Yuki, but in doing so I noticed that your V4 does the sorting fine, but V5 displays a "DebuggerError("Your hierarchy has held cycles!")" which, in my opinion, is not present.

Found the Problem.... but I am watching my code at the phone.

In my example the ref Button "button setting_x" must be named "button settings_x". I forgot the "s". will fix it tomorrow and check the code.

Ah yes, V5 catches ill-defined trees (which the other sort-based approaches ignore) but the message logged can be unhelpful.

"Your hierarchy has held cycles!"
should probably be just:
"Your hierarchy has held cycles or missing links!"

To aid debugging and spare headaches, you can change the debug-error code in V5 from:

Code: Select all

    ; In cases where the pending count is non-zero and hasn't changed, we've certainly a
    ; cycle present. Trigger a debugger error and bail if not debugging.
    If pendingCount = xLim + 1
      DebuggerError("Your hierarchy has held cycles!")
      Break
    EndIf

Into something like this:

Code: Select all

    ; In cases where the pending count is non-zero and hasn't changed, we've certainly a
    ; cycle present. Trigger a detailed debugger error and bail if not debugging.
    If pendingCount = xLim + 1
      CompilerIf #PB_Compiler_Debugger
        Protected invalidChainEntry.s = *pendingEntries(0)\RefEntry
        Protected invalidChain.s      = *pendingEntries(0)\Entry
        ; Clear the seen order map as we'll now use it to track seen invalid chain items.
        ClearMap(seenOrderMap())
        seenOrderMap(invalidChain) = #True
        ; Continue through the chain until we find either a missing or cyclic item.
        While invalidChainEntry
          invalidChain + " -> " + invalidChainEntry
          
          ; If we've seen the next node already, we've definitely a cycle.
          If seenOrderMap(invalidChainEntry)
            DebuggerError("Your hierarchy has referenced entries cyclically: " + invalidChain)
            Break
          EndIf
          seenOrderMap(invalidChainEntry) = #True
          
          ; Try and search for the next chain entry.
          ForEach StructList()
            If StructList()\Entry = invalidChainEntry
              invalidChainEntry = StructList()\RefEntry
              Goto continueNextEntry
            EndIf
          Next
          
          ; Failed to find next entry and continue on.
          DebuggerError("Your hierarchy has referenced a nonexistent entry: " + invalidChain)
          Break
          
          continueNextEntry:
        Wend
      CompilerEndIf
      Break
    EndIf

It's a lot more code but it shouldn't really hurt performance in the general case as it only takes place on error. It produces pretty helpful messages to narrow down the cause of hierarchy invalidity with a clear path, for example:

Code: Select all

; Case 0: Nonexistent Link
; ═══════════════════════════════════════════════════════
; Logs error: "Your hierarchy has referenced a nonexistent entry: x -> y -> Q"

AddElement(StructList())
StructList()\Entry = "x"
StructList()\RefEntry = "y"

AddElement(StructList())
StructList()\Entry = "y"
StructList()\RefEntry = "Q"


; Case 1: Cyclic Link
; ═══════════════════════════════════════════════════════
; Logs error: "Your hierarchy has referenced entries cyclically: x -> y -> z -> x"

AddElement(StructList())
StructList()\Entry = "x"
StructList()\RefEntry = "y"

AddElement(StructList())
StructList()\Entry = "y"
StructList()\RefEntry = "z"

AddElement(StructList())
StructList()\Entry = "z"
StructList()\RefEntry = "x"

Always happy to help! (and apologies if there are mistakes/weirdness! I'm just heading to sleep )

[Kurzer]

Yuki, I have now fixed my error that I mentioned here.
All sorting algorithms now work properly.

This thread has brought a great development. Great, I will now adopt your V5 in modified form in my module. Thanks a lot for lending me your experience and "brain power" I hope I can return the favor sometime.

Ciao, Kurzer

[Kurzer]

Oh damn, it gave me no peace.

I like such optimization tasks... and so I wanted to make it even more compact and with even less additional variables, lists or maps.

Tonight I created the sorting algorithm V6 and I can't really believe that this little procedure sorts correctly. I tested it manually with 24 entries. The sorting was correct for all entries.

I haven't tested the procedure in my module yet, I'll do that tomorrow, because it's already really late tonight.

V6 detects faulty references and returns a corresponding return value. Closed cycles are not detected separately, but simply skipped.

The list is run through only once, as in V3. The sorting is done at the corresponding entries in the map and later the sorting values are copied from the map to the list.

V6 is faster than all other versions up to approx. 600 entries. Since this is a list of gadgets of a window, I would claim that this high number of entries will never be reached in reality. Therefore - and also because the procedure is so simple - it is optimal for my purpose.

But without this terrific competition here, this evolutionary development would probably not have come about so quickly.
This is the stuff that drives me.

24 eintries:

Code: Select all

V3 Algorithm: 11 microseconds.
V5 Algorithm: 13 microseconds.
V5 extended : 11 microseconds.
V6 Algorithm: 6 microseconds.

120 entries:

Code: Select all

V3 Algorithm: 49 microseconds.
V5 Algorithm: 65 microseconds.
V5 extended: 53 microseconds.
V6 Algorithm: 25 microseconds.

600 entries:

Code: Select all

V3 Algorithm: 288 microseconds.
V5 Algorithm: 196 microseconds.
V5 extended: 190 microseconds.
V6 Algorithm: 138 microseconds.

1200 entries:

Code: Select all

V3 Algorithm: 900 microseconds.
V5 Algorithm: 546 microseconds.
V5 extended: 343 microseconds.
V6 Algorithm: 455 microseconds.

Code: Select all

Procedure.i SortList_V6()
	Protected.i *RefEntry.MyStruct, iSort = 999999, iReturnValue
	
	With StructList()
		ForEach StructList()
			If \RefEntry <> ""
				*RefEntry = FindMapElement(StructMap(), \RefEntry)
				If *RefEntry = 0
					; Invalid reference entry detected
					iReturnValue = -1
					Break
				EndIf
				If *RefEntry\Sort = 0
					StructMap(\Entry)\Sort = iSort
					iSort - 1
				Else
					StructMap(\Entry)\Sort = *RefEntry\Sort + 1
				EndIf
 			EndIf
		Next
	EndWith
	
	ForEach StructList()
		StructList()\Sort = StructMap(StructList()\Entry)\Sort
	Next		
	
	SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\Sort), TypeOf(MyStruct\Sort))
	ProcedureReturn iReturnValue
	
EndProcedure

[wilbert]

V6 is faster than all other versions up to approx. 600 entries.

The V5 version uses a map with 2048 slots/buckets.
The V6 version seems to use a map with the default of 512 slots.
When you have 1200 entries, this is a significant difference.
For a fair comparison, you should choose the same amount of slots for all versions.

[yuki]

V6 sees pretty significant gains by reusing the global map as-is instead of clearing with each invocation. By modifying V4 with similar reuse, it becomes approximately equal to V6 (93 vs 94 microseconds @ 1000 elements):

Code: Select all

Procedure SortList_V4_UsingGlobalMap()
  Protected numAssignedInCurrentPass
  Protected *parent.MyStruct
  
  ; Find all elements on the first layer of tree (without parent/ref) and store them in
  ; our known-order map while assigning depth (\Sort) 1.
  ; All other elements will be assigned depth (\Sort) 0.
  ForEach StructList()
    If StructList()\RefEntry = ""
      StructList()\Sort = 1
      StructMap(StructList()\Entry)\Sort = 1
    Else
      StructList()\Sort = 0
    EndIf
  Next
  
  ; Repeatedly scan the list searching for elements yet-to-be assigned a non-zero depth (\Sort)
  ; value, while assigning such once if we've handled their parent/ref.
  ; The scanning process stops whenever we are no longer able to assign a single depth value
  ; in a single pass. This should only happen when complete OR running into cycles.
  Repeat
    numAssignedInCurrentPass = 0
    ForEach StructList()
      If Not StructList()\Sort
        *parent = FindMapElement(StructMap(), StructList()\RefEntry)
        If Not *parent
          DebuggerWarning("Found reference to undefined entry: " + StructList()\RefEntry)
          ProcedureReturn -1
        EndIf
        If *parent\Sort
          StructList()\Sort = *parent\Sort + 1
          StructMap(StructList()\Entry)\Sort = StructList()\Sort
          numAssignedInCurrentPass + 1
        EndIf
      EndIf
    Next
  Until Not numAssignedInCurrentPass
  
  SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\Sort), TypeOf(MyStruct\Sort))
EndProcedure

Relying on the dirtied map for sort logic has the downside that whenever elements change, you have to properly invalidate the map. Affecting only the changed element might be coincidentally safe in some cases, but you'd really have to walk relations to be sure, which is relatively costly with the existing structure. This is good if your list is fixed after creation, but otherwise may cost more in the long run.

The DAG approach inherently avoids invalidation concerns, while V5 and (unmodified) V4 avoid it by ensuring they work on zeroed maps.

V6 still beats modified V4 (by quite a bit when it comes to deep trees), due to V6's fixed iteration count, but this also means chains longer than 2-elements have no sorting guarantees. In these cases, it relies on iteration order, so it's fine as long as the user hasn't registered controls out-of-order, e.g.:

Code: Select all

; Oops 1.
; ══════════════════════════════════════════════════════════════════════

AddElement(StructList()) : StructList()\Entry = "L4" : StructList()\RefEntry = "L3"
AddElement(StructList()) : StructList()\Entry = "L2" : StructList()\RefEntry = "L1"
AddElement(StructList()) : StructList()\Entry = "L3" : StructList()\RefEntry = "L2"
AddElement(StructList()) : StructList()\Entry = "L1"

; .═════+════════════════════════+════════════════════════+══════════.
; |  #  |          Name          |           Ref          |   Sort   |
; |-----|------------------------|------------------------|----------|
; |   0 | L1                     |                        | 0        |
; |   1 | L2                     | L1                     | 999998   |
; |   2 | L4                     | L3                     | 999999   |
; |   3 | L3                     | L2                     | 999999   |


; Oops 2.
; ══════════════════════════════════════════════════════════════════════

AddElement(StructList()) : StructList()\Entry = "L1"
AddElement(StructList()) : StructList()\Entry = "L2" : StructList()\RefEntry = "L1"
AddElement(StructList()) : StructList()\Entry = "L4" : StructList()\RefEntry = "L3"
AddElement(StructList()) : StructList()\Entry = "L3" : StructList()\RefEntry = "L2"

; .═════+════════════════════════+════════════════════════+══════════.
; |  #  |          Name          |           Ref          |   Sort   |
; |-----|------------------------|------------------------|----------|
; |   0 | L1                     |                        | 0        |
; |   1 | L4                     | L3                     | 999998   |
; |   2 | L2                     | L1                     | 999999   |
; |   3 | L3                     | L2                     | 1000000  |

; OK 1 (out-of-order OK in some cases).
; ══════════════════════════════════════════════════════════════════════

AddElement(StructList()) : StructList()\Entry = "L4" : StructList()\RefEntry = "L3"
AddElement(StructList()) : StructList()\Entry = "L1"
AddElement(StructList()) : StructList()\Entry = "L3" : StructList()\RefEntry = "L2"
AddElement(StructList()) : StructList()\Entry = "L2" : StructList()\RefEntry = "L1"

; .═════+════════════════════════+════════════════════════+══════════.
; |  #  |          Name          |           Ref          |   Sort   |
; |-----|------------------------|------------------------|----------|
; |   0 | L1                     |                        | 0        |
; |   1 | L2                     | L1                     | 999997   |
; |   2 | L3                     | L2                     | 999998   |
; |   3 | L4                     | L3                     | 999999   |

(Sidenote: I've had good luck with Windows Defender and PB recently, but it actually got mad with the test here as "Trojan:Win32/Wacatac.H!ml " )

[Kurzer]

[...] ...but this also means chains longer than 2-elements have no sorting guarantees. In these cases, it relies on iteration order, so it's fine as long as the user hasn't registered controls out-of-order

You are absolutely right. Unfortunately, I have to declare the V6 invalid in its current form.
I already suspected that this short, compact solution could be almost too good to be true

Therefore your updated V4 (using global map) should be the favorite so far.