Topic: how to shuffle a set of list ?

[highflyingbird]

the length of list is longer,my code runs faster.

On my computer, 20000 items , 10 times test:

HFB:shuffle takes: 1.932 Seconds .
Average performance: 0.1932 Seconds/time.

ShuffleList2 takes: 173.458 Seconds.
Average performance: 17.3458 Seconds/time.

The difference is very huge.

My Big O notation is O(n),maybe the others is O(n^2).

[RAIN CODE]

You guys are really good. I have still a lot to learn when it come to List.
All the lisps here are shorter than mine. No doubts about it.

I was thinking since my game's lisps are written all in module (subroutines)
Next time I post the game here, maybe someone here could re-write some of the module which I think there are
alot of rooms for improvement. If it shorter I am sure it will run faster.

There are alot of suggestions here dunno which to use  . All looks so good
Thanks again.

[highflyingbird]

Just a little bit of changed,to simulate the lotto:

Code - Auto/Visual Lisp: [Select]

1. (defun HFB:GetLottery (MaxNumber Count / i lst array temp Index lastIndex Lottery)
2.   (setq i MaxNumber)
3.   (repeat MaxNumber
4.     (setq lst (cons i lst))
5.     (setq i (1- i))
6.   )
7.  
8.   (setq LastIndex (1- MaxNumber))
9.   (setq Array (vlax-safearray-fill (vlax-make-safearray vlax-vblong (cons 0 LastIndex)) lst))
10.  
11.   (setq i 0)
12.   (repeat Count
13.     (setq Index (LM:RandomRange i LastIndex))
14.     (setq temp (vlax-safearray-get-element array Index))
15.     (vlax-safearray-put-element array Index (vlax-safearray-get-element array i))
16.     (vlax-safearray-put-element array i temp)
17.     (setq Lottery (cons temp Lottery))
18.     (setq i (1+ i))
19.   )
20.   (reverse Lottery)
21. )

In China, "double chromosphere":

(cons (LM:randomRange 1 16) (hfb:getlottery 32 6))

(12 17 27 28 32 8 7)

Did you guessed this group numbers? Break your leg!

[irneb]

HFB: You're correct! Whenever you use nth on long lists, it's always faster to use an array instead. That's where arrays are better to use than linked-lists (indexing is a simple multiplication instead of an iteration).

[ElpanovEvgeniy]

to solve the problem, really need a full randomization or enough each time to have a different order?

I see the opportunity to multiply to simplify the solution...

[irneb]

Just one thing HFB: Yours would only work if the list contains all the same types. And you'd need to modify the code in order to have a list of different types. Or you could change your function to something like this (hope you don't mind  ):

Code - Auto/Visual Lisp: [Select]

1. (defun HFB:shuffleTyp  (lst DataType / count array i lastIndex RandNum tmp)
2.   (setq count (length lst))
3.   (setq Array (MakeSafeArray (mapcar 'vlax-make-variant lst) DataType)) ;->maybe other type
4.   (setq i 0)
5.   (setq LastIndex (1- count))
6.   (repeat LastIndex
7.     (setq RandNum (LM:randomrange i LastIndex))
8.     (setq tmp (vlax-safearray-get-element array RandNum))
9.     (vlax-safearray-put-element array RandNum (vlax-safearray-get-element array i))
10.     (vlax-safearray-put-element array i tmp)
11.     (setq i (1+ i)))
12.   (vlax-safearray->list array))

Or to have it work exactly as the list-based versions

Code - Auto/Visual Lisp: [Select]

1. (defun HFB:shuffleVar  (lst / count array i lastIndex RandNum tmp)
2.   (setq count (length lst))
3.   (setq Array (MakeSafeArray (mapcar 'vlax-make-variant lst) vlax-vbVariant)) ;->maybe other type
4.   (setq i 0)
5.   (setq LastIndex (1- count))
6.   (repeat LastIndex
7.     (setq RandNum (LM:randomrange i LastIndex))
8.     (setq tmp (vlax-safearray-get-element array RandNum))
9.     (vlax-safearray-put-element array RandNum (vlax-safearray-get-element array i))
10.     (vlax-safearray-put-element array i tmp)
11.     (setq i (1+ i)))
12.   (mapcar 'vlax-variant-value (vlax-safearray->list array)))

An alternative list-based method ... using 6 Packs, then "dealing" each item from the list randomly into one of each pack, and then stacking the packs into one again

Code - Auto/Visual Lisp: [Select]

1. (defun ShuffleList6  (lst / pac0 pac1 pac2 pac3 pac4 pac5 v)
2.   (foreach item  lst
3.     (setq v (read (strcat "pac" (itoa (rem (fix (* (Random nil) 6)) 6)))))
4.     (set v (cons item (eval v))))
5.   (append pac0 pac1 pac2 pac3 pac4 pac5))

It's not all that bad compared to the array method for long lists (tested on 20000 integers)

Code: [Select]

Benchmarking ..... done for 8 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(HFB:SHUFFLE LST)                                8      1998      1998     54.15
(HFB:SHUFFLETYP LST vlax-vbLong)                 8      2029      2029     53.33
(HFB:SHUFFLEVAR LST)                             8      2200      2200     49.18
(SHUFFLELIST6 LST)                               4      1278      2556     42.33
(SHUFFLELIST LST)                                1     13525    108200      1.00
--------------------------------------------------------------------------------
And comparing list of 50 items:

Code: [Select]

Benchmarking ............ done for 2048 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(SHUFFLELIST2 LST)                            2048      1263      1263     21.14
(HFB:SHUFFLE LST)                             2048      1436      1436     18.60
(SHUFFLELIST LST)                             2048      1497      1497     17.84
(HFB:SHUFFLETYP LST vlax-vbLong)              2048      1497      1497     17.84
(HFB:SHUFFLEVAR LST)                          2048      1606      1606     16.63
(SHUFFLELIST6 LST)                            2048      1903      1903     14.03
(SHUFFLELIST5 LST)                            1024      1404      2808      9.51
(LM:SHUFFLE LST)                              1024      1436      2872      9.30
(SHUFFLELIST4 LST)                             512      1013      4052      6.59
(SHUFFLELIST3 LST)                             512      1107      4428      6.03
(PH:SHUFFLE1 LST)                              512      1512      6048      4.42
(SHUFFLE LST)                                  128      1669     26704      1.00
--------------------------------------------------------------------------------
Overall, it seems yours is the fastest for a wide range of list lengths. Even the mod to use variants is still faster.