AdmiralAlkex Posted April 21, 2010 Share Posted April 21, 2010 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 .Some of my scripts: ShiftER, Codec-Control, Resolution switcher for HTC ShiftSome of my UDFs: SDL UDF, SetDefaultDllDirectories, Converting GDI+ Bitmap/Image to SDL Surface Link to comment Share on other sites More sharing options...
Yashied Posted April 21, 2010 Share Posted April 21, 2010 (edited) 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 ;==>_ArraySortRandomThe 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 ;==>_ArraySortRandomEDIT:Even at $iMultiplier = 9 this is more than 60 times faster. Edited April 21, 2010 by Yashied My UDFs: iKey | FTP Uploader | Battery Checker | Boot Manager | Font Viewer | UDF Keyword Manager | Run Dialog Replacement | USBProtect | 3D Axis | Calculator | Sleep | iSwitcher | TM | NetHelper | File Types Manager | Control Viewer | SynFolders | DLL Helper Animated Tray Icons UDF Library | Hotkeys UDF Library | Hotkeys Input Control UDF Library | Caret Shape UDF Library | Context Help UDF Library | Most Recently Used List UDF Library | Icons UDF Library | FTP UDF Library | Script Communications UDF Library | Color Chooser UDF Library | Color Picker Control UDF Library | IPHelper (Vista/7) UDF Library | WinAPI Extended UDF Library | WinAPIVhd UDF Library | Icon Chooser UDF Library | Copy UDF Library | Restart UDF Library | Event Log UDF Library | NotifyBox UDF Library | Pop-up Windows UDF Library | TVExplorer UDF Library | GuiHotKey UDF Library | GuiSysLink UDF Library | Package UDF Library | Skin UDF Library | AITray UDF Library | RDC UDF Library Appropriate path | Button text color | Gaussian random numbers | Header's styles (Vista/7) | ICON resource enumeration | Menu & INI | Tabbed string size | Tab's skin | Pop-up circular menu | Progress Bar without animation (Vista/7) | Registry export | Registry path jumping | Unique hardware ID | Windows alignment More... Link to comment Share on other sites More sharing options...
jchd Posted April 21, 2010 Share Posted April 21, 2010 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 hereRegExp tutorial: enough to get startedPCRE 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) Link to comment Share on other sites More sharing options...
AdmiralAlkex Posted April 21, 2010 Author Share Posted April 21, 2010 (edited) 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 .Some of my scripts: ShiftER, Codec-Control, Resolution switcher for HTC ShiftSome of my UDFs: SDL UDF, SetDefaultDllDirectories, Converting GDI+ Bitmap/Image to SDL Surface Link to comment Share on other sites More sharing options...
Yashied Posted April 21, 2010 Share Posted April 21, 2010 (edited) Use indirection...In this case will be overlaps.EDIT:Bit late. Edited April 21, 2010 by Yashied My UDFs: iKey | FTP Uploader | Battery Checker | Boot Manager | Font Viewer | UDF Keyword Manager | Run Dialog Replacement | USBProtect | 3D Axis | Calculator | Sleep | iSwitcher | TM | NetHelper | File Types Manager | Control Viewer | SynFolders | DLL Helper Animated Tray Icons UDF Library | Hotkeys UDF Library | Hotkeys Input Control UDF Library | Caret Shape UDF Library | Context Help UDF Library | Most Recently Used List UDF Library | Icons UDF Library | FTP UDF Library | Script Communications UDF Library | Color Chooser UDF Library | Color Picker Control UDF Library | IPHelper (Vista/7) UDF Library | WinAPI Extended UDF Library | WinAPIVhd UDF Library | Icon Chooser UDF Library | Copy UDF Library | Restart UDF Library | Event Log UDF Library | NotifyBox UDF Library | Pop-up Windows UDF Library | TVExplorer UDF Library | GuiHotKey UDF Library | GuiSysLink UDF Library | Package UDF Library | Skin UDF Library | AITray UDF Library | RDC UDF Library Appropriate path | Button text color | Gaussian random numbers | Header's styles (Vista/7) | ICON resource enumeration | Menu & INI | Tabbed string size | Tab's skin | Pop-up circular menu | Progress Bar without animation (Vista/7) | Registry export | Registry path jumping | Unique hardware ID | Windows alignment More... Link to comment Share on other sites More sharing options...
smashly Posted April 21, 2010 Share Posted April 21, 2010 (edited) 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 EndFuncEdit: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 Link to comment Share on other sites More sharing options...
Spiff59 Posted April 21, 2010 Share Posted April 21, 2010 (edited) 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 Link to comment Share on other sites More sharing options...
jchd Posted April 21, 2010 Share Posted April 21, 2010 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 hereRegExp tutorial: enough to get startedPCRE 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) Link to comment Share on other sites More sharing options...
Yashied Posted April 21, 2010 Share Posted April 21, 2010 @Spiff59 Perfect! My UDFs: iKey | FTP Uploader | Battery Checker | Boot Manager | Font Viewer | UDF Keyword Manager | Run Dialog Replacement | USBProtect | 3D Axis | Calculator | Sleep | iSwitcher | TM | NetHelper | File Types Manager | Control Viewer | SynFolders | DLL Helper Animated Tray Icons UDF Library | Hotkeys UDF Library | Hotkeys Input Control UDF Library | Caret Shape UDF Library | Context Help UDF Library | Most Recently Used List UDF Library | Icons UDF Library | FTP UDF Library | Script Communications UDF Library | Color Chooser UDF Library | Color Picker Control UDF Library | IPHelper (Vista/7) UDF Library | WinAPI Extended UDF Library | WinAPIVhd UDF Library | Icon Chooser UDF Library | Copy UDF Library | Restart UDF Library | Event Log UDF Library | NotifyBox UDF Library | Pop-up Windows UDF Library | TVExplorer UDF Library | GuiHotKey UDF Library | GuiSysLink UDF Library | Package UDF Library | Skin UDF Library | AITray UDF Library | RDC UDF Library Appropriate path | Button text color | Gaussian random numbers | Header's styles (Vista/7) | ICON resource enumeration | Menu & INI | Tabbed string size | Tab's skin | Pop-up circular menu | Progress Bar without animation (Vista/7) | Registry export | Registry path jumping | Unique hardware ID | Windows alignment More... Link to comment Share on other sites More sharing options...
Spiff59 Posted April 21, 2010 Share Posted April 21, 2010 (edited) @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 Link to comment Share on other sites More sharing options...
PsaltyDS Posted April 21, 2010 Share Posted April 21, 2010 (edited) 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 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 Link to comment Share on other sites More sharing options...
AdmiralAlkex Posted April 22, 2010 Author Share Posted April 22, 2010 (edited) 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 .Some of my scripts: ShiftER, Codec-Control, Resolution switcher for HTC ShiftSome of my UDFs: SDL UDF, SetDefaultDllDirectories, Converting GDI+ Bitmap/Image to SDL Surface Link to comment Share on other sites More sharing options...
Malkey Posted April 22, 2010 Share Posted April 22, 2010 (edited) 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 Link to comment Share on other sites More sharing options...
Tvern Posted April 22, 2010 Share Posted April 22, 2010 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. Link to comment Share on other sites More sharing options...
Spiff59 Posted April 22, 2010 Share Posted April 22, 2010 (edited) 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 Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now