Any idea to randomize arrays quickly(er)??

[AdmiralAlkex]

Some of you may have seen ShiftER, my picture viewer.

I have lately been working on mitigating some of the slowdowns to get a better user experience, and it has gone really well, except for one issue:

Randomization of the playlist. 100 items are instant, 1k items are good enough, but 10k items takes a whooping 17 seconds on a Intel Q9550@3400 MHz!

Anyone have any idea how to make this faster?

#Include <String.au3>

Global $asTest[10000]
For $iX = 0 To UBound($asTest) -1
    $asTest[$iX] = $asTest[$iX] = _StringRepeat("IAmAString", Random(5, 15, 1))     ;To simulate path\filename
Next

$iTime = TimerInit()
_Randomize()
ConsoleWrite("_Randomize() took: " & Round(TimerDiff($iTime)) & " ms" & @CRLF)

Func _Randomize()
    $UB = UBound($asTest)
    Local $aRanPlayList[$UB]

    For $X = $UB -1 To 0 Step -1
        $Ran = Random(0, UBound($asTest) -1, 1)
        $aRanPlayList[$X] = $asTest[$Ran]
        _FastArrayDel($asTest, $Ran)
    Next
    $asTest = $aRanPlayList
EndFunc

Func _FastArrayDel(ByRef $Array, $Element)
    $UBTemp = UBound($Array)-1
    If $UBTemp = 0 Then Return
    $Array[$Element] = $Array[$UBTemp]
    ReDim $Array[$UBTemp]
EndFunc

[Yashied]

expandcollapse popup

#Include <String.au3>

Global $asTest[10000]
For $iX = 0 To UBound($asTest) - 1
    $asTest[$iX] = $asTest[$iX] = _StringRepeat("IAmAString", Random(5, 15, 1)) ;To simulate path\filename
Next

$iTime = TimerInit()
_Randomize()
ConsoleWrite("_Randomize() took: " & Round(TimerDiff($iTime)) & " ms" & @CRLF)

$iTime = TimerInit()
_ArraySortRandom($asTest)
ConsoleWrite("_Randomize() took: " & Round(TimerDiff($iTime)) & " ms" & @CRLF)

Func _Randomize()
    $UB = UBound($asTest)
    Local $aRanPlayList[$UB]

    For $X = $UB - 1 To 0 Step -1
        $Ran = Random(0, UBound($asTest) - 1, 1)
        $aRanPlayList[$X] = $asTest[$Ran]
        _FastArrayDel($asTest, $Ran)
    Next
    $asTest = $aRanPlayList
EndFunc   ;==>_Randomize

Func _FastArrayDel(ByRef $Array, $Element)
    $UBTemp = UBound($Array) - 1
    If $UBTemp = 0 Then Return
    $Array[$Element] = $Array[$UBTemp]
    ReDim $Array[$UBTemp]
EndFunc   ;==>_FastArrayDel

Func _ArraySortRandom(ByRef $aArray, $iMultiplier = 2)

    Local $A, $B, $Temp

    For $i = 1 To $iMultiplier * UBound($aArray)
        $A = Random(0, UBound($aArray) - 1, 1)
        $B = Random(0, UBound($aArray) - 1, 1)
        $Temp = $aArray[$A]
        $aArray[$A] = $aArray[$B]
        $aArray[$B] = $Temp
    Next
EndFunc   ;==>_ArraySortRandom

The matches benchmark for different values of $iMultiplier parameter.

1 ~ 13.49%

2 ~ 1.86% (Optimal)

3 ~ 0.23%

4 ~ 0.07%

5 ~ 0.01%

6 ~ 0.04%

7 ~ 0%

8 ~ 0%

9 ~ 0%

#Include <Array.au3>

Dim $Data[10000]

For $i = 0 To UBound($Data) - 1
    $Data[$i] = $i
Next

For $i = 1 To 9
    $Count = 0
    $Temp = $Data
    _ArraySortRandom($Temp, $i)
    For $j = 0 To UBound($Temp) - 1
        If $Temp[$j] = $Data[$j] Then
            $Count += 1
        EndIf
    Next
    ConsoleWrite('x' & $i & ' => ' & (100 * $Count / UBound($Data)) & '% matches' & @CR)
Next

Func _ArraySortRandom(ByRef $aArray, $iMultiplier = 2)

    Local $A, $B, $Temp

    For $i = 1 To $iMultiplier * UBound($aArray)
        $A = Random(0, UBound($aArray) - 1, 1)
        $B = Random(0, UBound($aArray) - 1, 1)
        $Temp = $aArray[$A]
        $aArray[$A] = $aArray[$B]
        $aArray[$B] = $Temp
    Next
EndFunc   ;==>_ArraySortRandom

EDIT:

Even at $iMultiplier = 9 this is more than 60 times faster.

Edited April 21, 2010 by Yashied

[jchd]

Use indirection:

Local $t = TimerInit()
Local $ran[100000]
Local $n = UBound($ran) - 1
For $i = 0 To $n
    $ran[$i] = Random(0, $n)
Next
ConsoleWrite("Generating " & $n + 1 & " indexes took " & TimerDiff($t) & " ms" & @LF)

Then access your playlist thru $ran: play($playlist[$ran[$i]]) instead of play($playlist[$i])

[AdmiralAlkex]

That looks awesome Yashied, thank you!

Edit: I'm not so sure about jchd's code though...

Edit2: Yeah I can't have duplicates (I just want the order "changed") so I'll probably go with Yashied's code.

Edited April 21, 2010 by AdmiralAlkex

[Yashied]

Use indirection...

In this case will be overlaps.

EDIT:

Bit late.

Edited April 21, 2010 by Yashied

[smashly]

Hi, using my pc and the code below I get "_Randomize() took: 75 ms" "_Randomize() took: 57 ms" (removed silly If compare)

(My PC i7 920 @ 4Ghz)

#Include <Array.au3>

Global $asTest[10000]

For $iX = 0 To UBound($asTest) -1
    $asTest[$iX] = $iX & ": IAmAString"     ;To simulate path\filename
Next

$iTime = TimerInit()
_Randomize()
ConsoleWrite("_Randomize() took: " & Round(TimerDiff($iTime)) & " ms" & @CRLF)

_ArrayDisplay($asTest)

Func _Randomize()
    $UB = UBound($asTest)
    For $X = 0 To $UB -1
        $Ran1 = Random(0, $UB -1, 1)
        $Ran2 = Random(0, $UB -1, 1)
        _ArraySwap($asTest[$Ran1], $asTest[$Ran2])
    Next
EndFunc

Edit:

And put the loop in a loop of 5 for more random result I get "_Randomize() took: 374 ms" "_Randomize() took: 279 ms" (removed silly If compare)

#Include <Array.au3>

Global $asTest[10000]

For $iX = 0 To UBound($asTest) -1
    $asTest[$iX] = $iX & ": IAmAString"     ;To simulate path\filename
Next

$iTime = TimerInit()
_Randomize()
ConsoleWrite("_Randomize() took: " & Round(TimerDiff($iTime)) & " ms" & @CRLF)

_ArrayDisplay($asTest)

Func _Randomize()
    $UB = UBound($asTest)
    For $i = 1 To 5
        For $X = 0 To $UB -1
            $Ran1 = Random(0, $UB -1, 1)
            $Ran2 = Random(0, $UB -1, 1)
            _ArraySwap($asTest[$Ran1], $asTest[$Ran2])
        Next
    Next
EndFunc

Cheers

Edited April 21, 2010 by smashly

[Spiff59]

This scrambles the original array, I suppose copying to a second array would be worthwhile if you need to retain the original list.

Am I nuts or does this do it pretty fast?

#Include <Array.au3>
#Include <String.au3>

Global $asTest[1000] = [999]
For $iX = 1 To UBound($asTest) - 1
    $asTest[$iX] = "Entry#" & $iX
Next

$iTime = TimerInit()
_Randomize2()
ConsoleWrite("_Randomize() took: " & Round(TimerDiff($iTime)) & " ms" & @CRLF)
_ArrayDisplay($asTest)

;===============================================================================
Func _Randomize2()
    For $i= $asTest[0] to 1 Step -1
        $new = Random(1, $i + 1, 1)
        $tmp = $asTest[$i]
        $asTest[$i] = $asTest[$new]
        $asTest[$new] = $tmp
    Next
EndFunc

typo

edit2: thats sloppily thrown together, the "include string.au3" isn't needed, nor the ubound() statement, probably a const for array-size would be involved if this was being graded

Edited April 21, 2010 by Spiff59

[jchd]

Sorry, I didn't realize you exclude dups, I was assuming that it would matter for a playlist.

[Yashied]

@Spiff59

Perfect!

[Spiff59]

@Spiff59

Perfect!

Thank you, Sir <blush>

Since I'd gotten my sloppy entry into the race lol

Here a prettier version:

#Include <Array.au3>
Global $iArraySize = 999, $asTest[$iArraySize + 1] = [$iArraySize]
For $iX = 1 To $iArraySize
    $asTest[$iX] = "Entry#" & $iX
Next

$iTime = TimerInit()
_Randomize2()
ConsoleWrite("_Randomize() took: " & Round(TimerDiff($iTime)) & " ms" & @CRLF)
_ArrayDisplay($asTest)

;===============================================================================
Func _Randomize2()
    For $i= $iArraySize to 1 Step -1
        $new = Random(1, $i + 1, 1)
        $tmp = $asTest[$i]
        $asTest[$i] = $asTest[$new]
        $asTest[$new] = $tmp
    Next
EndFunc

Edited April 21, 2010 by Spiff59

[PsaltyDS]

The original took about 38800msec on my Q8300 2.5GHz.

This takes only about 2500ms:

#include <String.au3>
#include <Array.au3> ; Only for _ArrayDisplay()

Global $asTest[10000]
For $iX = 0 To UBound($asTest) - 1
    $asTest[$iX] = $iX & ": " & _StringRepeat("IAmAString", Random(5, 15, 1)) ;To simulate path\filename
Next

_ArrayDisplay($asTest, "$asTest, Before")
$iTime = TimerInit()
$aRET = _ArrayRandom($asTest)
ConsoleWrite("_Randomize() took: " & Round(TimerDiff($iTime)) & " ms" & @CRLF)
_ArrayDisplay($aRET, "$aRET, After")

Func _ArrayRandom(ByRef $aInput)
    Local $iSize = UBound($aInput), $iLimit = $iSize
    Local $aOutput[$iSize]

    Local $sFlags = ""
    For $n = 1 To $iSize
        $sFlags &= "1" ; Set a "1" flag for every element
    Next

    For $n = 0 To $iSize - 1
        $iRND = Random(1, $iLimit, 1)
        If $iRND = 0 Then $iRND = 1
        $iLoc = StringInStr($sFlags, "1", 2, $iRND)
        $aOutput[$n] = $aInput[$iLoc - 1]
        $sFlags = StringReplace($sFlags, $iLoc, "0") ; Clear the flag to "0" for the randomly selected element
        $iLimit -= 1
    Next

    Return $aOutput
EndFunc   ;==>_ArrayRandom

Just created a string of 1's and treated them like binary flag bits representing the unused elements.

Edit: I love the reverse-bubble-sort idea from Yashied!

Edited April 21, 2010 by PsaltyDS

[AdmiralAlkex]

I did some testing and Spiff's method seem fastest. It is a bit weird with very few items (like 10) but since ShiftER doesn't necessarily start at the beginning of the array, it shouldn't matter.

When I include this I will have exhausted my ToDo list (except for a few minor things) so I will probably upload the new code later today.

Big thanks to all of you!

Edited April 22, 2010 by AdmiralAlkex

[Malkey]

For $i= $iArraySize to 1 Step -1
 $new = Random(1, $i + 1, 1)
 $tmp = $asTest[$i]
 $asTest[$i] = $asTest[$new]
 $asTest[$new] = $tmp

For a heads up, user be aware.

A problem with Spiff59 's script is - if on the first loop, the generated random number is the maximum number then this error occurs:-

Array variable has incorrect number of subscripts or subscript dimension range exceeded.

$asTest[$i] = $asTest[$new]

$asTest[$i] = ^ ERROR

Reducing the array size to 2 significantly increases the chance of this error occurring.

Possibly, the probability of an error is 1 in (array size + 1).

Edit: Try

For $i = $iArraySize To 2 Step -1
        $new = Random(1, $i, 1)

Edited April 22, 2010 by Malkey

[Tvern]

I created This a while ago based on Yashieds method in another post. It's pretty much the same as spiff's method used in an UDF.

[Spiff59]

For a heads up, user be aware.

A problem with Spiff59 's script is - if on the first loop, the generated random number is the maximum number then this error occurs:-

I wonder if a BugTracker would be appropriate?

One wouldn't think that Random(1,1,1) should return a 0.

Edit: Ah, I see... If min=max then 0 is returned.

Random (999,999,1) also returns a zero.

That doesn't seem like correct behavior to me.

If you've requested an integer between 999 and 999, then 999 should be returned.

Edit2: Nevermind, I see that bug reports have been created on this issue more than once. In some versions of AutoIt it was corrected, and then later for some reason it reverted back to its present state. The current ruling is that one should write code to work-around this issue rather than have the function behave logically. That being the case, I guess the helpfile needs an update to make users aware of the quirkiness of the Random() function. I'll jot it down as a "known issue" with AutoIt, and let someone else (who doesn't scan the BugTracker history) open the next ticket.

Edit3: PS - Thanks, Malkey. Your mod to limit the lowest value in the loop to 2 avoids the min=max problem with Random(). Not making the final (potential) swap of elements 2 and 1 would not have a great effect on the randomness of the output (as one or both of those elements may have already been swapped multiple times).

Edited April 22, 2010 by Spiff59