What about a PLC sort algorithm ?

Sioan · Jan 10, 2014

I have a RADIXSORT implementation for S7 !
(not quite finished ... maybe tomorrow)

I would like to see some alternative ... program examples!

Sioan · Jan 13, 2014

QUICKSORT worst case : "n²" (source : WIKIPEDIA)
RADIXSORT worst case : "kn" (source : WIKIPEDIA)

... what do you think is the best sort algorithm for integer, double integer, reals for PLC ?
My personal opinion is : RadixSort (best "worst case" time).

f.E:
QUICKSORT 10,000² for 10,000 DINT (REAL).
RADIXSORT 10,000*32 for 10,000 DINT (REAL).

Over 32 elements to sort -> radixsort better than quicksort !(My personal opinion!) Is it correct?
?
(I also believe that for real-time applications, one has to take the worst case scenario as given)

daba · Jan 13, 2014

You can see the various algorithms animated here..

If you play around with it, you will see that the "best" algirithm depends on the "initial conditions".. e.g. random, nearly-sorted, etc.

Sioan · Jan 13, 2014

daba said:
You can see the various algorithms animated here..

If you play around with it, you will see that the "best" algirithm depends on the "initial conditions".. e.g. random, nearly-sorted, etc.

RADIXSORT isn't there !

( it's another kind of sorting ... without comparison)

Thank you !°
But nevertheless , personally I think that "the great" IBM wouldn't exist today , without RADIXSORT (if you know what I mean )

daba · Jan 13, 2014

Radix Sort is not there, probably because the process of Radix Sorting requires the numbers to be stored in Decimal Notation (ref. Wikipedia).

I can't see how that sorting algorithm can be efficient in a PLC where data is stored in Binary notation. Converting the binary data into Binary-Coded-Decimal for Radix Sorting would surely take the sting out of it...

But I'll let you prove it to me, your math is probably far better than mine

L D[AR2P#0.0] · Jan 13, 2014

Binary is just another radix....

Usireland · Jan 14, 2014

I tested a few different sorting algorithms on the new Compact Logix platform and I discovered that the algorithm makes a difference but not in the way you might think.

When people talk in terms of O (n and n^2 etc) the assumption is made that a compare instruction and a move instruction take the same amount of time. I cannot comment on PC implementations but in AB there is a significent difference in the amount of time used between a MOV and a Compare instruction (LES/GRT etc). As a result certin algorithms which are "Slower" in terms of O time are actually faster in real time (comparing the worst case scenario of both). An algorithm that uses a lot of MOV commands like say heap sort, even though it has a smaller O value, actually takes longer than Selection Sort, because Selection sort uses exactly N move instructions and a lot of Compare instructions, where as Heap sort uses a lot more MOV instructions and fewer Compare instructions.

Also without question, selection sort is a lot easier to understand looking at the code that Heap/Merge/Quick sort (I´ve never seen an implementation of Radix but I imagine it would be similar) and typically in a PLC you are not going to be doing a lot of Big Data, so the difference between the best and worst algorithm with a list of 32 elements is generally speaking neglagable.

Now when it comes to 32billion elements then thats a whole different ball game.

And of course we haven´t even begun to discuss the amount of space used in the process.

Sioan · Jan 14, 2014

Usireland said:
...
the algorithm makes a difference but not in the way you might think.
...

I think (to myself: )You must have clairvoyant abilities !
RADIXSORT do not COMPARE something ... you have just n*32 MOV-es every time , every n-array !!!(for REALS)

Sioan · Jan 14, 2014

2 Parts!°

Code:

DATA_BLOCK "SORT DB"
TITLE =
VERSION : 0.1
  STRUCT 	
   A : ARRAY  [0 .. 17 ] OF REAL  := 0.000000e+000;	
  END_STRUCT ;	
BEGIN
   A[0] := 0.000000e+000; 
   A[1] := 0.000000e+000; 
   A[2] := 0.000000e+000; 
   A[3] := 0.000000e+000; 
   A[4] := 0.000000e+000; 
   A[5] := 0.000000e+000; 
   A[6] := 0.000000e+000; 
   A[7] := 0.000000e+000; 
   A[8] := 0.000000e+000; 
   A[9] := 0.000000e+000; 
   A[10] := 0.000000e+000; 
   A[11] := 0.000000e+000; 
   A[12] := 0.000000e+000; 
   A[13] := 0.000000e+000; 
   A[14] := 0.000000e+000; 
   A[15] := 0.000000e+000; 
   A[16] := 0.000000e+000; 
   A[17] := 0.000000e+000; 
END_DATA_BLOCK


DATA_BLOCK "HELP DB"
TITLE =
VERSION : 0.1
  STRUCT 	
   A : ARRAY  [0 .. 17 ] OF REAL  := 0.000000e+000;	
  END_STRUCT ;	
BEGIN
   A[0] := 0.000000e+000; 
   A[1] := 0.000000e+000; 
   A[2] := 0.000000e+000; 
   A[3] := 0.000000e+000; 
   A[4] := 0.000000e+000; 
   A[5] := 0.000000e+000; 
   A[6] := 0.000000e+000; 
   A[7] := 0.000000e+000; 
   A[8] := 0.000000e+000; 
   A[9] := 0.000000e+000; 
   A[10] := 0.000000e+000; 
   A[11] := 0.000000e+000; 
   A[12] := 0.000000e+000; 
   A[13] := 0.000000e+000; 
   A[14] := 0.000000e+000; 
   A[15] := 0.000000e+000; 
   A[16] := 0.000000e+000; 
   A[17] := 0.000000e+000; 
END_DATA_BLOCK


FUNCTION_BLOCK "SORT FB"
TITLE =
VERSION : 0.1
VAR_INPUT
  START : BOOL ;	
  DB_Sort : BLOCK_DB ;	
  DB_Help : BLOCK_DB ;	
  LOOPTIME : INT ;	
END_VAR
VAR_OUTPUT
  BUSY : BOOL ;	//Not ready
END_VAR
VAR
  START_FM : BOOL ;	
  SELECTIONBIT : BOOL ;	
  DBNO_Sort : WORD ;	
  DBNO_Help : WORD ;	
  BITSET : DWORD ;	
  STEP : DWORD ;	
  BIT_Sort : DWORD ;	
  BIT_Help : DWORD ;	
  LOOPCOUNTER : INT ;	
END_VAR
VAR_TEMP
  DBNO_tempS : WORD ;	
  DBNO_tempH : WORD ;	
  ADDRESS_Sort : DWORD ;	
  DWNr_Sort : DWORD ;	
  DWNr_Help : DWORD ;	
  M : DWORD ;	
END_VAR
BEGIN
NETWORK
TITLE =
      A     #START; 
      FP    #START_FM; 
      JCN   END; 
      OPN   #DB_Help; 
      L     DBNO; 
      T     #DBNO_Help; 
      OPN   #DB_Sort; 
      L     DBNO; 
      T     #DBNO_Sort; 
      L     DBLG; //BYTE Anzahl des DB
      L     L#4; //DWORD Anzahl des DB
      /D    ; 
      +     L#-1; //(zählt von 0 an)
      L     L#32; //DWORD = 32 BIT
      *D    ; 
      T     #BITSET; 
      CLR   ; 
      =     #SELECTIONBIT; 
      L     L#0; 
      T     #STEP; 
      T     #LOOPCOUNTER; //.
      SET   ; 
      =     #BUSY; 
END:  NOP   0; 
NETWORK
TITLE =
      A     #BUSY; 
      JC    GO; 
      BE    ; 
GO:   NOP   0; 
NETWORK
TITLE =
      L     #LOOPCOUNTER; //.
      L     0; //.
      >I    ; //.   
      JC    s4; //.
NETWORK
TITLE =
      L     #STEP; //SCHRITTNUMMER
      L     L#4; //MOD 4 (ROUTINE_WIDERHOLFAKTOR)
      MOD   ; //ZYKLIZITÄT NÜTZEN
      L     L#0; //TYP 0
      <>D   ; 
      JC    s1; 
      L     #STEP; 
      L     L#16; 
      /D    ; 
      T     #M; 
      L     L#0; 
      ==D   ; 
      L     L#24; 
      JC    B1; 
      L     #M; 
      L     L#1; 
      ==D   ; 
      L     L#16; 
      JC    B1; 
      L     #M; 
      L     L#2; 
      ==D   ; 
      L     L#8; 
      JC    B1; 
      L     #M; 
      L     L#3; 
      ==D   ; 
      L     L#0; 
B1:   T     #ADDRESS_Sort; 
      L     #STEP; 
      L     L#16; 
      MOD   ; //Teilen auf  Periode von 0-31 (= bits in 1 dword)   
      L     L#2; 
      /D    ; //Nochmals Teilen auf Periode von 0-7 (= bits in 1 byte)
      T     #BIT_Sort; 
      L     #ADDRESS_Sort; 
      +D    ; 
      T     #ADDRESS_Sort; 
      L     L#0; 
      T     #DWNr_Sort; 
      T     #DWNr_Help; 
      L     #DBNO_Sort; 
      T     #DBNO_tempS; 
      L     #DBNO_Help; 
      T     #DBNO_tempH; 
NETWORK
TITLE =
s1:   NOP   0; 
      L     #STEP; 
      L     L#4; 
      MOD   ; 
      L     L#1; 
      <>D   ; 
      JC    s2; 
      L     #STEP; 
      L     L#16; 
      /D    ; 
      T     #M; 
      L     L#0; 
      ==D   ; 
      L     #BITSET; 
      +     L#24; 
      JC    B2; 
      L     #M; 
      L     L#1; 
      ==D   ; 
      L     #BITSET; 
      +     L#16; 
      JC    B2; 
      L     #M; 
      L     L#2; 
      ==D   ; 
      L     #BITSET; 
      +     L#8; 
      JC    B2; 
      L     #M; 
      L     L#3; 
      ==D   ; 
      L     #BITSET; 
B2:   L     #BIT_Sort; 
      +D    ; 
      T     #ADDRESS_Sort; 
      L     #BITSET; 
      T     #DWNr_Sort; 
      T     #DWNr_Help; 
      L     #DBNO_Sort; 
      T     #DBNO_tempS; 
      L     #DBNO_Help; 
      T     #DBNO_tempH; 
NETWORK
TITLE =
s2:   NOP   0; 
      L     #STEP; 
      L     L#4; 
      MOD   ; 
      L     L#2; 
      <>D   ; 
      JC    s3; 
      L     #STEP; 
      L     L#16; 
      /D    ; 
      T     #M; 
      L     L#0; 
      ==D   ; 
      L     L#24; 
      JC    B3; 
      L     #M; 
      L     L#1; 
      ==D   ; 
      L     L#16; 
      JC    B3; 
      L     #M; 
      L     L#2; 
      ==D   ; 
      L     L#8; 
      JC    B3; 
      L     #M; 
      L     L#3; 
      ==D   ; 
      L     L#0; 
B3:   T     #ADDRESS_Sort; 
      L     #STEP; 
      L     L#16; 
      MOD   ; 
      L     L#2; 
      /D    ; 
      T     #BIT_Help; 
      L     #ADDRESS_Sort; 
      +D    ; 
      T     #ADDRESS_Sort; 
      L     L#0; 
      T     #DWNr_Sort; 
      T     #DWNr_Help; 
      L     #DBNO_Sort; 
      T     #DBNO_tempH; 
      L     #DBNO_Help; 
      T     #DBNO_tempS; 
NETWORK
TITLE =
s3:   NOP   0; 
      L     #STEP; 
      L     L#4; 
      MOD   ; 
      L     L#3; 
      <>D   ; 
      JC    s4; 
      L     #STEP; 
      L     L#16; 
      /D    ; 
      T     #M; 
      L     L#0; 
      ==D   ; 
      L     #BITSET; 
      +     L#24; 
      JC    B4; 
      L     #M; 
      L     L#1; 
      ==D   ; 
      L     #BITSET; 
      +     L#16; 
      JC    B4; 
      L     #M; 
      L     L#2; 
      ==D   ; 
      L     #BITSET; 
      +     L#8; 
      JC    B4; 
      L     #M; 
      L     L#3; 
      ==D   ; 
      L     #BITSET; 
B4:   L     #BIT_Help; 
      +D    ; 
      T     #ADDRESS_Sort; 
      L     #BITSET; 
      T     #DWNr_Sort; 
      T     #DWNr_Help; 
      L     #DBNO_Sort; 
      T     #DBNO_tempH; 
      L     #DBNO_Help; 
      T     #DBNO_tempS; 
NETWORK
TITLE =
s4:   NOP   0; 
      AN    #SELECTIONBIT; 
      JC    oo0; 
NETWORK
TITLE =
      A     #SELECTIONBIT; 
      JC    oo1; 
NETWORK
TITLE =
oo0:  NOP   0; 
o3:   L     #DWNr_Sort; 
      L     #BITSET; //{0->(m-1)}[m]
      >D    ; 
      JC    o1; 
      OPN   DB [#DBNO_tempS]; 
      A     DBX [#ADDRESS_Sort]; 
      JC    o2; 
      L     DBD [#DWNr_Sort]; 
      OPN   DB [#DBNO_tempH]; 
      T     DBD [#DWNr_Help]; 
      L     #DWNr_Help; 
      +     L#32; 
      T     #DWNr_Help; 
o2:   NOP   0; 
      L     #ADDRESS_Sort; 
      +     L#32; 
      T     #ADDRESS_Sort; 
      L     #DWNr_Sort; 
      +     L#32; 
      T     #DWNr_Sort; 
      L     #LOOPCOUNTER; //.
      +     1; //.
      T     #LOOPCOUNTER; //.
      L     #LOOPTIME; //.
      MOD   ; //.   
      L     0; //.
      ==I   ; //.   
      JC    FIN; //.
      JU    o3; 
o1:   L     0; 
      T     #LOOPCOUNTER; 
      SET   ; 
      =     #SELECTIONBIT; 
      L     #STEP; 
      +     L#1; 
      T     #STEP; 
      BE    ; 
NETWORK
TITLE =
oo1:  NOP   0; 
o6:   L     #DWNr_Sort; 
      L     L#0; 
      <D    ; 
      JC    o4; 
      OPN   DB [#DBNO_tempS]; 
      AN    DBX [#ADDRESS_Sort]; 
      JC    o5; 
      L     DBD [#DWNr_Sort]; 
      OPN   DB [#DBNO_tempH]; 
      T     DBD [#DWNr_Help]; 
      L     #DWNr_Help; 
      +     L#-32; 
      T     #DWNr_Help; 
o5:   NOP   0; 
      L     #ADDRESS_Sort; 
      +     L#-32; 
      T     #ADDRESS_Sort; 
      L     #DWNr_Sort; 
      +     L#-32; 
      T     #DWNr_Sort; 
      L     #LOOPCOUNTER; //.
      +     1; //.
      T     #LOOPCOUNTER; //.
      L     #LOOPTIME; //.
      MOD   ; //.   
      L     0; //.
      ==I   ; //.   
      JC    FIN; //.
      JU    o6; 
o4:   L     0; 
      T     #LOOPCOUNTER; 
      CLR   ; 
      =     #SELECTIONBIT; 
      L     #STEP; 
      +     L#1; 
      T     #STEP; 
      L     L#64; 
      <D    ; 
      JC    FIN; 
      CLR   ; 
      =     #BUSY; 
FIN:  BE    ; 
END_FUNCTION_BLOCK


DATA_BLOCK "FB1 DB"
TITLE =
VERSION : 0.0
"SORT FB"
BEGIN
   START := FALSE; 
   DB_Sort := DB 1; 
   DB_Help := DB 1; 
   LOOPTIME := 0; 
   BUSY := FALSE; 
   START_FM := FALSE; 
   SELECTIONBIT := FALSE; 
   DBNO_Sort := W#16#0; 
   DBNO_Help := W#16#0; 
   BITSET := DW#16#0; 
   STEP := DW#16#0; 
   BIT_Sort := DW#16#0; 
   BIT_Help := DW#16#0; 
   LOOPCOUNTER := 0; 
END_DATA_BLOCK

Sioan · Jan 14, 2014

Code:

ORGANIZATION_BLOCK OB 1
TITLE = "Main Program Sweep (Cycle)"
VERSION : 0.1
VAR_TEMP
  OB1_EV_CLASS : BYTE ;	//Bits 0-3 = 1 (Coming event), Bits 4-7 = 1 (Event class 1)
  OB1_SCAN_1 : BYTE ;	//1 (Cold restart scan 1 of OB 1), 3 (Scan 2-n of OB 1)
  OB1_PRIORITY : BYTE ;	//Priority of OB Execution
  OB1_OB_NUMBR : BYTE ;	//1 (Organization block 1, OB1)
  OB1_RESERVED_1 : BYTE ;	//Reserved for system
  OB1_RESERVED_2 : BYTE ;	//Reserved for system
  OB1_PREV_CYCLE : INT ;	//Cycle time of previous OB1 scan (milliseconds)
  OB1_MIN_CYCLE : INT ;	//Minimum cycle time of OB1 (milliseconds)
  OB1_MAX_CYCLE : INT ;	//Maximum cycle time of OB1 (milliseconds)
  OB1_DATE_TIME : DATE_AND_TIME ;	//Date and time OB1 started
END_VAR
BEGIN
NETWORK
TITLE =
//TEST Netzwerk !
      A     [COLOR="Red"][B]I      0.7[/B][/COLOR]; 
      FP    M    100.0; 
      JCN   w; 
      OPN   "SORT DB"; 
      L     1.047484e+001; 
      T     DBD    0; 
      L     -2.147223e+003; 
      T     DBD    4; 
      L     -1.474840e+001; 
      T     DBD    8; 
      L     7.483600e+005; 
      T     DBD   12; 
      L     1.474830e+002; 
      T     DBD   16; 
      L     5.200000e+003; 
      T     DBD   20; 
      L     1.470000e+000; 
      T     DBD   24; 
      L     -1.470000e+004; 
      T     DBD   28; 
      L     1.470000e+003; 
      T     DBD   32; 
      L     1.214510e+007; 
      T     DBD   36; 
      L     6.612400e-001; 
      T     DBD   40; 
      L     2.501000e+004; 
      T     DBD   44; 
      L     -1.590010e+003; 
      T     DBD   48; 
      L     7.000000e+003; 
      T     DBD   52; 
      L     1.123000e+000; 
      T     DBD   56; 
      L     5.600100e+002; 
      T     DBD   60; 
      L     1.000000e-004; 
      T     DBD   64; 
      L     1.211101e+004; 
      T     DBD   68; 
w:    NOP   0; 
NETWORK
TITLE =
      CALL "SORT FB" , "FB1 DB" (
           START                    := [COLOR="red"][B]I      0.0[/B][/COLOR],
           DB_Sort                  := "SORT DB",
           DB_Help                  := "HELP DB",
           LOOPTIME                 := 32767,
           BUSY                     := [COLOR="Blue"][B]M      4.0[/B][/COLOR]);
END_ORGANIZATION_BLOCK

Not quite ready ... but even so everyone with S7 can test/simulate it ! Just play with it and observe "SORT DB".

Sioan · Jan 15, 2014

This not finished implementation is only a non-optimal experiment, yet!

LOOK HERE

... !!!

(... needs a rollback , too !)

Sioan · Jan 16, 2014

Ready to use , now ! ...powerfailure safe +etc. [no copyright]
Change the array size , the looptime ...test/play with it!

L D[AR2P#0.0] · Jan 16, 2014

Negative numbers not sorted correctly.

Sioan · Jan 16, 2014

That's realy simple to implement ! If you need it i'll make it ...!

Peter Nachtwey · Jan 16, 2014

I rarely need to sort in a PLC. I usually avoid doing things like that because they can take a varying about of time in a real time system. Sometimes data doesn't need to be sorted all at once and can sorted one item per scan over a period of scans and then a bit set to indicate the sort is done. This avoids the big time hit that would occur if you tried to sort the data all at once. I also like sort in place type of algorithms. I also prefer sort algorithms that minimize the worst case time. I like to know there is an upper bound on how long a sort will take.

Sorting isn't something that should be done in a PLC unless there are only about 10 items. If there are more then a PC should do it.

What about a PLC sort algorithm ?

Sioan

Member

Sioan

Member

daba

Lifetime Supporting Member

Sioan

Member

daba

Lifetime Supporting Member

L D[AR2P#0.0]

Lifetime Supporting Member

Usireland

Member

Sioan

Member

Sioan

Member

Sioan

Member

Sioan

Member

Sioan

Member

L D[AR2P#0.0]

Lifetime Supporting Member

Sioan

Member

Peter Nachtwey

Member

Similar Topics