 |
10-06-2008, 09:40 PM
|
|
Newcomer
|
|
Join Date: Oct 2008
Posts: 6
|
|
Unique Loop
|
Hi,
I have some rather large nested loops, I'm trying to optimise in various ways, one is having unique loops (as i do not require duplicates)
IE:
Code:
for i = 0 to 10
for j = 0 to 10
for k = 0 to 10
for l = 0 to 10
Do something with the values
next l
next k
next j
next i
I could wait inside the loop letting it do its thing until all values are unique but thats still a bit slow, is there a way i can have say if i = j or i = k or i = l then l = l + 1... but with all values taken into account, every time i try it the numbers come out non unique or missing combinations, i don't understand... |
|
10-06-2008, 11:08 PM
|
 |
Hydrogen Powered
Administrator
* Expert *
|
|
Join Date: Jul 2003
Location: Sacramento, CA
Posts: 6,090
|
|
|
MaxMouseDLL -
Do you have a specific question?
Can you explain in more detail A) what you are trying to accomplish and B) what problem you are having with the code you posted?
|
__________________
"With the appearance of the AddressOf operator, an entire industry has developed among authors illustrating how to do previously impossible tasks using Visual Basic. Another industry is rapidly developing among consultants helping users who have gotten into trouble attempting these tasks." -Dan Appleman
|
10-07-2008, 07:36 AM
|
|
Senior Contributor
Forum Leader
|
|
Join Date: Oct 2003
Location: Central Florida
Posts: 1,205
|
|
I assume that when you say "unique," you're trying to combine items, but not redundantly.
Focusing on a simpler situation . . .
Code:
For i = 0 To 10
For j = 0 To 10
Print i, j
Next j
Next i
11 * 11 or 121 pairings. Think of an 11x11 square with all the cells filled.
This would match every i with every j, but also every j with i, so you get two pairings of a particular i and j. Not unique in most cases. You could check for duplications and weed them out as they occur. But there should be a better way, right?
Code:
For i = 0 To 10
For j = i To 10
Print i, j
Next j
Next i
We vary the starting point of the j-loop based upon the current value of i.
Think of an 11x11 square divided along the long diagonal, and with the lower left piece removed. Each j-iteration gets smaller than the last.
This gets rid of the duplications. Every i is matched with every j exactly once. However, each of the 11 numbers is also matched with itself once.
Code:
For i = 0 To 10
For j = (i+1) To 10
Print i, j
Next j
Next i
The same model, with the diagonal also removed.
This gets rid of the self-matches. this could represent a round-robin schedule for 11 teams or 11 players.
I get a headache in thinking about extending this to three or more dimensions, but the idea should be the same. Use the previous index in the current loop to unduplicate.
Does that help in any way? |
__________________
-- D.J.
I do not endorse any items advertised within this frame, and regret that the viewer is subjected to such.
|
10-07-2008, 04:46 PM
|
|
Newcomer
|
|
Join Date: Oct 2008
Posts: 6
|
|
Quote:
Originally Posted by ElderKnight
Does that help in any way?
|
the result is still missing entries... (IE: 1, 0 ... 3,0/3,1/3,2 etc) obviously because of where the second loop begins.
i think the only easy solution to this is to sit in the end loop checking.. when all values are unique
begin code... |
Last edited by MaxMouseDLL; 10-07-2008 at 04:51 PM.
|
10-07-2008, 05:52 PM
|
 |
Joseph Koss
* Guru *
|
|
Join Date: Aug 2003
Location: Unfashionable End
Posts: 3,615
|
|
The easy solution is to use an array which flags the indexes which are already "used"
Code:
Dim flags(0 to 10) As Boolean
For i = 0 to 10
flags(i) = True
For j = 0 to 10
If Not flags(j) Then
flags(j) = True
For k = 0 to 10
If Not flags(k) Then
flags(k) = True
For l = 0 to 10
If Not flags(l) Then
flags(l) = True
...
flags(l) = False
End If
Next
flags(k) = False
End If
Next
flags(j) = False
End If
Next
flags(i) = False
Next
|
|
10-07-2008, 06:22 PM
|
|
Newcomer
|
|
Join Date: Oct 2008
Posts: 6
|
|
Quote:
Originally Posted by Rockoon
The easy solution is to use an array which flags the indexes which are already "used"
Code:
Dim flags(0 to 10) As Boolean
For i = 0 to 10
flags(i) = True
For j = 0 to 10
If Not flags(j) Then
flags(j) = True
For k = 0 to 10
If Not flags(k) Then
flags(k) = True
For l = 0 to 10
If Not flags(l) Then
flags(l) = True
...
flags(l) = False
End If
Next
flags(k) = False
End If
Next
flags(j) = False
End If
Next
flags(i) = False
Next
|
Thats quite nice... I'll scale this up to the numbers I'm using (1615 at the moment... but it'll eventually be around 2000) and see if there are any performance benefits.... thanks |
|
10-07-2008, 07:52 PM
|
|
Joseph Koss
* Guru *
|
|
Join Date: Aug 2003
Location: Unfashionable End
Posts: 3,615
|
|
Quote:
Originally Posted by MaxMouseDLL
Thats quite nice... I'll scale this up to the numbers I'm using (1615 at the moment... but it'll eventually be around 2000) and see if there are any performance benefits.... thanks
|
2000^4 = 16,000,000,000,000
The theoretical ideal minimum cost/iteration on a 3ghz cpu is 1 clock cycle, or 3,000,000,000 iterations per second. At that blazing (and unrealistic) speed your loops will still take over 88 minutes to complete. |
|
10-07-2008, 08:54 PM
|
|
Newcomer
|
|
Join Date: Oct 2008
Posts: 6
|
|
Quote:
Originally Posted by Rockoon
2000^4 = 16,000,000,000,000
The theoretical ideal minimum cost/iteration on a 3ghz cpu is 1 clock cycle, or 3,000,000,000 iterations per second. At that blazing (and unrealistic) speed your loops will still take over 88 minutes to complete.
|
I know, i have done the math... unfortunately within that loop there are several SHA-1 hashes, and some other hashes between loops, meaning on my 3.2GHZ Dual i get about 8,000 iterations per second at full throttle (And now probably a bit less).
I already knew this before i started the project, as such it's always been a distributed affair with an ASP back-end to do the co-ordination.
Things are minimalised using the flagged loop (no duplicates), which is a very nice piece of code, API doevents (only when needed), and by trying to minimalise maximum loop values.
Even so, i may have to rethink some aspects. |
|
10-07-2008, 10:32 PM
|
 |
CodeASaurus Hex
Forum Leader
* Expert *
|
|
Join Date: Jul 2006
Location: San Antonio TX
Posts: 2,427
|
|
|
My math has to be rusty due to my old age because if it is even close my thought is "Why Bother"
If my figures are close based on the information of Rockoon and your figure of 8000 iterations per cycle You will be a very old man by the time it finishes.
At my age I would never see it finish. (got to be wrong on the math 63 Years!)
|
__________________
Code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live. ~Martin Golding
The user is a peripheral that types when you issue a read request. ~Peter Williams
MSDN Visual Basic .NET General FAQ
|
10-07-2008, 10:58 PM
|
|
Joseph Koss
* Guru *
|
|
Join Date: Aug 2003
Location: Unfashionable End
Posts: 3,615
|
|
|
There is a pretty solid understanding in the simulation field that simulations should not be embarked upon if they take over 4 years to complete.
This 4 year figure is not arbitrary, it is approximately twice the rate of doubling of computational power. That rate of doubling is known as Moores Law.
If a simulation takes 6 years to complete and you begin today, it'll take 6 years (duh.)
If instead you wait 2 years, it will only take 3 additional years to complete. 2 + 3 = 5 years. Waiting saves you a year!
This does not apply to simulations that can be migrated to better hardware midway through, or simulations that begin giving usefull answers immediately.
In actuality, several weeks is typically the upper limit on simulation runtime (most climate simulations, for example)
|
|
10-09-2008, 02:32 AM
|
|
Newcomer
|
|
Join Date: Oct 2008
Posts: 6
|
|
|
Hmm...
8,000 Iterations per second
1615 ^ 4 = 6802837650625 calculations total
Till Completion:
6802837650625 / 8,000 = 850354706.328125 Seconds
850354706.328125 / 60 = 14172578.438802083 Mins
14172578.438802083 / 60 = 236209.64064670138 Hours
236209.64064670138 / 24 = 9842.068360 Days
9842.068360 / 365 = 26.9645708 Years
But say if 1,000 people are contributing (distributed) each performing 8,000 per second, that time goes down drastically (9 days)
The problem I'm facing is this, the calculations total will probably be more than 1615 ^ 4, infact it'll probably be around 6 times more. The contributers will probably not number anywhere near 1,000. The entire iteration process needs to be done over 3,000 times, resulting in collosal numbers.
(1615 ^ 4) * 6 = 40817025903750 * 3000 = 122451077711250000 Calculations total (Minimum!), which is 485362 years if i attempt this with a single computer at 8,000 per second.
Obviously, cutting down duplicates in loops decreases things a little... however, I'm still going to have to re think this...
I could possibly decrease the loop to 3 instead of 4, but that detracts from the results (Yes, this is a distributed SHA-1 crack attempt on 3,000+ hashes, which are derived from the PSP (PlayStation Portable) NID commandset EG: 0x0785C974 = sceDrmBBCipherUpdate - 0x0785C974 Is the first 8 characters (Reordered a little bit) of the SHA-1 hash of the string sceDrmBBCipherUpdate, there are 3,000 more or so of these "NIDS" which have not been cracked. This is a prefixed dictionary based attack project to attempt that. Commands could be in various formats EG: sce<word><word>... / sce_<word>_<word>... / sce<word>_<word>... / <word><word>... / <word>_<word> which is why the iterations start getting ramped up, my rethink will be on more focus, not including certain attempts, and a minimal dictionary, in order to get the most out of this.)
Grrr! hashes are annoying!
*** Roger: at completion (if i run it as it is, which i wont...) you'll be 78... hehe :P
|
Last edited by MaxMouseDLL; 10-09-2008 at 02:48 AM.
|
|
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
|
|
|
| Thread Tools |
|
|
| Display Modes |
 Linear Mode
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|
|
