Jump to content
Sign in to follow this  
AdmiralAlkex

Any idea to randomize arrays quickly(er)??

Recommended Posts

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

Share this post


Link to post
Share on other sites
Yashied

#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.

:idea:

Edited by Yashied

Share this post


Link to post
Share on other sites
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])


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites
AdmiralAlkex

That looks awesome Yashied, thank you! :idea:

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 by AdmiralAlkex

Share this post


Link to post
Share on other sites
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 by smashly

Share this post


Link to post
Share on other sites
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 by Spiff59

Share this post


Link to post
Share on other sites
jchd

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


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites
Yashied
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 by Spiff59

Share this post


Link to post
Share on other sites
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.

:idea:

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

Edited by PsaltyDS

Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law

Share this post


Link to post
Share on other sites
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! :idea:

Edited by AdmiralAlkex

Share this post


Link to post
Share on other sites
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 by Malkey

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 by Spiff59

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.