Faster Loop
Blitz3D Forums/Blitz3D Programming/Faster Loop
| ||
| Hello I use this to loop through a type variable to place a specific one into another type variable. For very large lists, 4 million and higher, it can take 15 minutes for more. Is there a faster method? WHILE CT>0 For AB.CH=Each CH:BC=BC+1 If BC=BTR Then OB.CH=New CH:OB\BT=AB\BT:Text 20,20,CT:Delete AB.CH:CT=CT-1:Flip:Cls:Exit Next Wend HALT The loop Actually takes longer now for some reason with large bodies of data over 4 million in size. Debug is off and only the Chrome browser is running in the background. Running this section of the code now takes 45 minutes to complete. |
| ||
| I'm pretty sure a lot of coders use some sort of zoning system, in other words update only objects that are upto a certain distance from the player at that time. |
| ||
| If you are flipping inside the for loop with 4 million entries it will be limited by the vertical sync...ie about 60 frames per second which means that for loop will run at 1 iteration per 16ms approx....take the text and flip outside of the for loop. Edit...oops...i didnt see the exit command....running all your if statement commands on one line makes for unreadable code. |
| ||
| 4 million iterations should take a second. Yoyr slowdown is somewhere else. |
| ||
| The program still moves sluggishly. It's definitely the for loop. Now I remember that it was used for timing and so looping through 4 million items when looping just 1500 times was approximately a second, equals 2794 seconds, approximately 46 minutes . There may be no faster method inside a loop. |
| ||
| I'm with Matty on this one. There has to be something else happening. just 1500 times was approximately a second For ease of calculation I will assume a very leisurely 1.5GHz processor. That means one million CPU cycles to process each type instance. |
| ||
| Yes but the code exits the FOR loop and reenters it if CT > 0 which it will be for 4 millions times. I probably need to use another method for this, just thought there was another way or a shortcut. |
| ||
| From what I understand from your code you delete only one type and add it to the end of your list. The CT value must be equal to 1 before the loop, and if it take a while to compute, the BTR value must be huge. My suggestion is that instead of BC=BC+1, you can count how many types you have in your list one time, then calculate the FLOORED number of time you need to increment that value to reach BTR, and then do the BC=BC+1 stuff from that value. You can probably use the Mod command with success here. Maybe it's not clear, but unless you post a complete example it's hard to go further. |
| ||
| Can you please send some more code? And can you descripe, what is purpose of the algo? What is BTR? Does it change? I redesigned your code for better reading and there are two questions: Type CH Field BT% End Type While CT>0 For AB.CH=Each CH BC=BC+1 If BC=BTR Then OB.CH=New CH OB\BT=AB\BT Text 20,20,CT Delete AB.CH CT=CT 1 ;Why this "1" behind the CT? Flip Cls Exit EndIf Next Wend Halt ;What is HALT? Is it a kind of sorting algo? For me it look like you always try to continue at the point, where you leaved the loop at the previous time. So why not stay in the loop? your problem is the FLIP command. It comes to often. How many list elements will fit to the conditions? Already 3600 will need one minute! Only for testing purposes: Please do a test without FLIP and TEXT and check the time needed in total, similar to this: Type CH Field BT% End Type Global Check=Millisecs() While CT>0 For AB.CH=Each CH BC=BC+1 If BC=BTR Then OB.CH=New CH OB\BT=AB\BT Delete AB Exit EndIf Next Wend print "TIME=" + ( Millisecs()- Check ) WaitKey() |
| ||
| I think the Text command causes the slowdown, too. And you should use Flip 0 instead of Flip only. You could update the text once a second to fix this, a quick example: It takes at least 5.3 seconds here to iterate 100 Million times. |
| ||
| @dna: Just of of curiosity, are you running in windowed mode or fullscreen?. I noticed a while back that Blitz seems to lag in windowed mode. |
| ||
| I'm running the program in a windowed mode. Global GWID=600,GHEI=600,TY,LIP:Graphics3D GWID,GHEI,16,2 |
| ||
| I updated the posted code. It was missing a minus sign in the expression. It should have read . . . If BC=BTR Then OB.CH=New CH:OB\BT=AB\BT:Text 20,20,CT:Delete AB.CH:CT=CT-1:Flip:Cls:Exit . . . With a CT=CT-1 before the flip. It's in my source that way but fell out during the transfer. It runs the same |
| ||
| Why put CT=CT-1 instead of CT=0 ? If CT is superior to 1 before the loop it will mess everything. |
| ||
| did you try the test i descriped in my first post? Can you send more code. We cannot do experiments without knowing the complete type and how it is filled. And we know to less about the conditions that leads to the EXIT. Without knowing how big CT and BTR are, and how they are changing... it is difficult Here is a simulation to check the speed difference betweenn with or without FLIP Type CH Field BT% End Type For i%=0 To 100 OB.CH=New CH OB\BT=123 Next Global GWID=600,GHEI=600,TY,LIP Graphics3D GWID,GHEI,16,2 CT=100 Global Check=MilliSecs() While CT>0 BTR=BTR+1 For AB.CH=Each CH BC=BC+1 If BC=BTR Then OB.CH=New CH OB\BT=AB\BT Delete AB.CH CT=CT-1 Text 20,20,CT Flip 0 Cls Exit EndIf Next Wend Print "TIME=" + ( MilliSecs()- Check ) WaitKey() With a simple FLIP it needs 1660msec, with "FLIP 0" 17msec. When removing CLS and TEXT too, it needs 1msec. |
| ||
| It takes at least 5.3 seconds here to iterate 100 Million times. I ran you code, it takes 19.3 secs on my older machine but that is much faster than 40 minutes. I'll try the flip 0 code next |
| ||
Here is the additional code that you requested.seedrnd millisecs() While EE<4000000 W=Rand(1,100):AB.CH=New CH:AB\BT=W:EE=EE+1 Wend CT=4000000 FH2=WriteFile(FLO$+"SFO2.TXT"):If FH2=0 Then End While CT>0 BTR=Rand(1,CT):BC=0 For AB.CH=Each CH:BC=BC+1 If BC=BTR Then WriteByte(FH2,AB\BT):Delete AB.CH:CT=CT-1:Exit Next Wend CloseFile(FH2) Print"DONE" The algorithm pulls a byte out of the type element at random |
| ||
| You set up a list of size N, in this case 4000000. Then you step through the list, deleting one element each time. On average the length of the list is N/2 at this step. At each step you select a random element, which on average will be in the middle of the size N/2 list. That is a total of about N * (N/2)/2 things to do. So a list of initial size 1000 will do about 250000 things. Your 4000000 example will do 4000000 * 1000000 things. |
| ||
| That's probably the issue then. It will always be slow due to the large loops. But I wrote this piece and thought that it should speed up as the type list begins to shrink. I thought that would make it improve over time. I may have to do it with another method or abandon the idea. |
| ||
| And what's the purpose of this algorithm? What will you achieve? Perhaps there is another way. |
| ||
| You better use a type array instead of a type list. So you can access each member of the list (on a certain position) directly: this code is already faster than your code, but still not the optimum: Type CH Field BT% End Type max%=40000;00 Dim Source.CH(max) SeedRnd MilliSecs() For i%=0 To max W=Rand(1,100) Source(i)=New CH Source(i)\BT=W Next CT=max FH2=WriteFile(FLO$+"SFO2.TXT") If FH2=0 Then End Global Check=MilliSecs() While CT>0 ;If ( MilliSecs()- Check )>15000 End BTR=Rand(1,max) If Source(BTR)<>Null ;Print btr +" " + ct WriteByte(FH2,Source(BTR)\BT) Delete Source(BTR) CT=CT-1 EndIf Wend CloseFile(FH2) Print "TIME=" + ( MilliSecs()- Check ) WaitKey() Tested with 40000 elements your last code needs 9300msec, this piece of code 99msec. Perhaps other forum members can help? The code above runs fast (136msec) upto 65000 elements. With 66000 elements the times rises dramatically to >15000msec. What happens? In BlitzMax (also free) this job can be done with 1,000,000 elements within 19sec: |
| ||
| Same as Midimaster, using an array to store type handles, but with a difference, when a type is deleted, its handle in the array is replaced by the handle of the last type so the random function can't pick an empty element : It's slower with 40000 elements, but it goes straight with more, I tested with 4.000.000 and it takes 17 seconds here. Tested with a bank instead of an array : same time. Strange thing with your code Midimaster, the barrier is 65536 elements wich is exactly the maximum value of a short (2-bytes), maybe that the Rand() function is somehow based on this... |
| ||
| @Flanker nice idea with the HANDLEs. Did not know that the function exist in B3D. And what a genius idea to "copy" the handle, pointing to the last object, to the handle, which was just selected! I needed some minutes to understand... But this way the random area is "shrinking" all the time! Great |
| ||
| In the last example you're doing 4 million WriteByte calls. Why not use PokeByte into a temporary Bank in the loop, and then after it ends do a single WriteBytes to the file. It might squeeze some more milliseconds. Edit: also, use more descriptive variable names! Keeping them short like that won't impact performance at all, the compiler uses its own names for these variables later. |
| ||
| I thought that when you deleted a type variable the list points to the next one in the list. If so then, when you point your handle to the next one in the list, that should achieve the same effect. |
| ||
| An alternative way to do this is to simply sort the list in a random order on creation then delete them in sequence. |
| ||
| Matty An alternative way to do this is to simply sort the list in a random order on creation then delete them in sequence. That's what the first EE loop does. It starts from 1 to 4000000 but the integers are random when chosen for insertion. Basically your idea. From that I'm pulling them out randomly within the CT loop. What Floyd posted was right, 4000000 * 1000000 is too large for speed. I will have to rethink the method for doing this. |
| ||
| But but but....if they are inserted randomly why then delete them in random order...it is already random...instead just delete them in sequential order...!?? |
| ||
| But isnt the solution of Flanker not fast enough? 17 sec instead of 45min. That's more than 100 times faster! Which speed do you need? Could you test this with your original code? |
| ||
| I did not test the code of flanker yet. I have never seen the handle pointers before and need to find the documentation on the syntax. It's new to some of us. * I just tried his code and get a memory access violation. What version of BB is he using?* ** I'm using B3D, I think this is particular to Bmax ** |
| ||
| It is 100% B3D. I tested it on my B3D Version 1.106 and it works perfect. Did you change anything, or did you copy the code without changing it? Switch on the DEBUG ENABLED option to see, where the problem is! |
| ||
| Yes it's 100% B3D, i'm using the last version (1.108c), but this should work on any recent version. If you want informations about types handles, check this thread : http://www.blitzbasic.com/Community/posts.php?topic=75556 When you delete a type, its handle is freed but others keep theirs, it's like the linked lists in Bmax. BTW, on my I7 CPU it takes only 8 seconds to complete with 4 millions elements. |
| ||
| Just tried Flanker's code in Blitz3D v1.108 and with CT set to 4 million it completes in 10.5 seconds here. (AMD FX6350 @ 3.9 GHz.) |
| ||
| Hey, I got the code to work. I did the same as yesterday copy and paste and today for some reason it works. Probably needed to reboot yesterday. Now I need to understand the handle function documentation wherever it exists. * There is no help file for the handle function. Does someone have a reference or does someone understand the syntax? * ** Runs in 25.75 Secs on my older machine. Now I just need to get it to process the information ** |
| ||
You can search the forums for Object and Handle using Google.object handle site:www.blitzbasic.com The code archives can also be searched. object handle site:www.blitzbasic.com/codearcs |
| ||
| an "easy to understand" explanation: Each element (instance) of your type CH is saved anywhere in the RAM. A HANDLE is the adress, where this is. So the HANDLE() function returns an integer value which is representing the adress of the type element in the RAM. Type CH Field BT% End Type ab.CH=New CH ab\BT=123 A.INT=handle(ab) Print "Adress=" + A The "invers function" is... xy.CH = Object.CH(A) Print "Content=" + xy\BT Here you "cast" the content of a RAM adress to a type. Afterwards you can access this part of the RAM like a element of your type CH. |
| ||
| @Mididmaster It's incredible that you do not have to define xy as new to use it for the object function. |
| ||
| The variable xy.CH really just holds the address of a Type object. xy.CH = New CH New allocates memory for the object and returns an address, which is stored in xy. xy.CH = Object.CH(A) In this case Object.CH(A) returns the address of an object and that is stored in xy. |
| ||
| Sorry if I don't get it at all, and I apologize in advance for what'I'm going to say (it's been monthes I have a big headacke, so perhaps I missed something in the topic) But what's the purpose of all this ? Basically, you just start with nothing and end generating a 4000000 random data file and destroying the temporary stuff So, I guess the only purpose is to generate a random data file. The problem is : It doesn't require any of all the stuff involved here, type or array or handle/object, and it does even not require to randomize picking/poking at an index ...
Local Bank = CreateBank(4000000)
For i = 0 To 4000000-1
PokeByte(bank, i, Rand(1,100))
Next
WriteBytes(bank, WriteFile("out.txt"), 0, BankSize(bank))
Print "Done"
WaitKey()
End
This will do the same and should not tale more than a second. (I benchmarked it, it takes 300 ms in release, and 850 ms in debug mode)
Local t0 = MilliSecs()
Local Bank = CreateBank(4000000)
Local t1 = MilliSecs()
For i = 0 To 4000000-1
PokeByte(bank, i, Rand(1,100))
Next
Local t2 = MilliSecs()
WriteBytes(bank, WriteFile("out.txt"), 0, BankSize(bank))
Local t3 = MilliSecs()
Print "total : "+(t3-t0)+".ms"
Print "Empty bank : "+(t1-t0)+".ms"
Print "Randomiz bank : "+(t2-t1)+".ms"
Print "Write File : "+(t3-t2)+".ms"
Print "file is located at :"
Print CurrentDir()+"out.txt"
Print ""
Print "Hit Any Key To End"
WaitKey()
End
So, what is the purpose ? Does anyone here have a clue on why you're trying to solve something that is probably senseless ? I have the feeling dna is a beginner who wanted something but started something way to complicated for a simple task ... but I might be wrong. ps : Else, if you really need to have a data structur, then midimaster (I think it was him) is right, you already randomize the input, so randomizing the output is useless. And if it's the case, this will work too
Type CH
Field BT%
End Type
; randomize input
Local n.CH
Local i%
For i = 1 To 4000000
n.CH = New CH
n\BT = Rand(1,100)
Next
; create a bank, for faster export
Local bank = Createbank(4000000)
Local o% = 0
; fill the bank with the random values
Local a.CH = First CH
For a = Each CH
PokeByte bank,o, a\BT : o=o+1
Next
; export the bank to the file.
WriteBytes(bank, WriteFile("out.txt"), 0, BankSize(bank))
; if required, then you can delete all the instances of CH.
Delete Each CH
Print "Done - hit any key to end"
WaitKey()
End
|
| ||
| It was never precisely stated but I think the goal was really just to pick random items from a type list. The problem is easy with an array, but quite difficult with a list. If the list has reached its final form then the easiest way is probably just to copy it to an array. The problem is what to do if the list is dynamically growing/shrinking. |
| ||
| Well, there are at the same time tons of algorithm to do this task in an efficient way, and no real way to do it properly in a "generic" way. I suppose the worst case would be a random access of all the entries of a dynamic list in realtime (once or more times per loop), so it would need to be both fast on access, and fast on creation/destruction For all the other cases, there are sorting algorithm that will do it efficiently like qsort/bubble sort etc ... or a nested tree - the choice of the algorithm require to be aware of the final purpose, if it's made to be used once only in the program (or only for some tasks that don't suffer of realtime requirements, like saving data etc ...), if the data are persistent or only used for the task (so, a simple array can be created on the fly without complex structure to store the objects), and some more parameters like single or multiple access to an object are allowed or not, etc ... On the worst case, the biggest challenge would be to randomly access all the data in a different order anytime the task is run and have a list that is frequently updated Building the structure will depend on : is it more often updated or accessed ? A "not that bad" generic way to do it is to use a tree-like structure, like a TMap (where the key would be a random position) which is both fast and slow. ps : does the flanker's code works efficiently ? I didn't test it, but I'm pretty sure that it will not access randomly "all" the objects and will instead try to access them by order anytime the array limit decreases (whenever he removes an object, the array position of the removed object is updated to point to the last entry, so the removed slots all point to the same object which give it an higher probability to be accessed) but, once more, it depends on the need to export an efficiently randomized stuff or not. |
| ||
| I think the given question was: ... to loop through a type variable to place a specific one into another type variable... original code was: While CT>0 For AB.CH=Each CH BC=BC+1 If BC=BTR Then OB.CH=New CH OB\BT=AB\BT Text 20,20,CT Delete AB.CH CT=CT 1 ;Why this "1" behind the CT? Flip Cls Exit EndIf Next Wend Halt ;What is HALT? we did not get more informations... All additional code lines where added by me only to get a running example. So the type field with 4000000 entries is given, but the numbers of fields inside are maybe much more than one. Also the values are not defined as random. I only created random values to have anything in the fields. Now Dna wants to pick a type at a specific position BTR (not necessarily a random value) copy that hit type to a file and remove the entry. Mine and Flankers solutions are closed to this given situation. all others are long shots... |
| ||
| ps : does the flanker's code works efficiently ? I didn't test it, but I'm pretty sure that it will not access randomly "all" the objects and will instead try to access them by order anytime the array limit decreases (whenever he removes an object, the array position of the removed object is updated to point to the last entry, so the removed slots all point to the same object which give it an higher probability to be accessed) Yes it's efficient, at any time all the objects have the same probality to be accessed. When an object is removed, its array "pointer" is replaced by the last object in the list, but the Rand() function is also decreased by 1 (CT = CT - 1), so it will always be Rand(1,number of objects remaining). And as Midimaster stated, we don't exactly know what is the purpose of this, but if you want to access randomly to all your types, then here you go. |
| ||
| @MIDIMASTER The minus sign was missing in the original post. Here you can see it in the right spot. seedrnd millisecs() While EE<4000000 W=Rand(1,100):AB.CH=New CH:AB\BT=W:EE=EE+1 Wend CT=4000000 FH2=WriteFile(FLO$+"SFO2.TXT"):If FH2=0 Then End While CT>0 BTR=Rand(1,CT):BC=0 For AB.CH=Each CH:BC=BC+1 If BC=BTR Then WriteByte(FH2,AB\BT):Delete AB.CH:CT=CT-1:Exit Next Wend CloseFile(FH2) Print"DONE" |
| ||
| dna never answered my comment above earlier anyway which was that he has inserted items into the list in random order in any case so why not just delete them in sequence....they will be no less random than if he deletes them in random order after having inserted them? |
| ||
| If you add randomly - the stack is randomized if you then select randomly you will "fetch" things according to the distribution type of your "Pseudo Random Number Generator" - so eg.it often chooses "the center" (gaussian, normal distribution ...) If you now remove "in sequence", you will just move the "likelyness" to the right (or "bottom" of the stack). If you remove "randomly" (with the same PRNG) then you will propably remove one from the center - bringing some others more near the former center of the random number distribution. If your PRNG is doing a "equally distributed thing" then yes, it should not matter from which spot in a stack/list you remove. And of course only if you _always_ remove with "random" and nowhere with "remove first/last". And also you never should then do "draw the first 10 of a stack". bye Ron |
| ||
| @Matty The code I submitted used numbers which it did not have to do. I did present it in a odd way by using numbers without clearly defining what it was supposed to to which was to randomize a list. Supposed to have some application or a game that you want to randomize the placement of the items in your maze. EI: The refrigerator or, Ruler or, what ever else is in the game to be picked up, those items must not be in the same place every time the application is run. This can do that. I was just thinking ahead given the notion that the items were already randomized and so the next time the application is run, they would need to be randomized again to have them in a different spot. |
   |