SitePoint Sponsor

User Tag List

Results 1 to 9 of 9

Thread: Massive Loops

  1. #1
    SitePoint Enthusiast
    Join Date
    Feb 2005
    Posts
    27
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Massive Loops

    I am trying to write a test harness for one of my apps, I need to check that all possible inputs return all possible correct outputs. My problem is that the for loop itself is running painfully slowly.. my code:

    Code:
    counter = 0
    
    for card1 in (1..52)
    	for card2 in (card1+1..52)
    		for card3 in (card2+1..52)
    			for card4 in (card3+1..52)
    				for card5 in (card4+1..52)
    					for card6 in (card5+1..52)
    						for card7 in (card6+1..52)
    							counter += 1
    							# run tests here with card1 - card7
    						end
    					end
    				end
    			end
    		end
    	end
    end
    
    # show set checksums
    puts counter
    The idea being that I am testing about 133 million different combinations of cards. I expected ruby to be slower than the equivalent code in other languages, but geez, on my MacBook Pro this loop is running at just over 2 minutes, compared to 30 seconds for logically equiv. code in php, and less than 5 seconds in c++.

    Is there some smarter way of doing this? It seems the bulk of the work is in the Range operations... What I really want is just an old-school for loop

  2. #2
    SitePoint Guru
    Join Date
    Aug 2005
    Posts
    986
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Isn't it easier to prove that the code is correct?

    Code Ruby:
    n.upto(m) do |x|
      ...
    end
     
    # == 
     
    for x in n..m
      ...
    end

  3. #3
    SitePoint Enthusiast
    Join Date
    Feb 2005
    Posts
    27
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Well, basically I need to test each possible combination of 52 cards in a 7 card hand... I have been running tests with randomizing the cards, but I want to run all possible 133 million hands and generate a checksum to prove the algorithm is correct. I can't think of any other way except the nested loops to do that

  4. #4
    Team SitePoint
    Join Date
    Apr 2006
    Posts
    72
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Just be thankful you're not using Lua...

    Code:
    #!/usr/bin/lua
    
    local counter = 0
    -- for card1=1,52 do
         for card2=1,52 do
            for card3=1,52 do
                for card4=1,52 do
                    for card5=1,52 do
                        for card6=1,52 do
                            for card7=1,52 do
                                counter = counter + 1
                            end
                        end
                    end
                end
            end
         end
    -- end
    print(counter)
    (outer loop commented out - too slow to test)

    Code:
    paul@macbuntupro:~/code/lua$ time ./loops.lua 
    19770609664
    
    real    5m58.054s
    user    5m4.799s
    sys     0m53.179s
    .. multiplied by 52 for the outer loop, that's 5.17 hours for the full 7 loops!

  5. #5
    SitePoint Guru
    Join Date
    Aug 2005
    Posts
    986
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Strange:

    Lua is fast

    Lua has a deserved reputation for performance. To claim to be "as fast as Lua" is an aspiration of other scripting languages. Several benchmarks show Lua as the fastest language in the realm of interpreted scripting languages. Lua is fast not only in fine-tuned benchmark programs, but in real life too. A substantial fraction of large applications have been written in Lua
    -- http://www.lua.org/about.html

    Edit: you're doing far too much work.

    52^7 =

    1028071702528
    vs
    133784560

    You're doing the full 1..52 loop every time. You only need to do card[n-1]+1..52.

  6. #6
    Team SitePoint
    Join Date
    Apr 2006
    Posts
    72
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Fenrir: well spotted, thanks.

    The reason I tried it in Lua in the first place was because I was expecting it to be way faster than Ruby, PHP etc. And it is...

    Code Lua:
    local counter = 0
     
    for card1=1,52 do
        for card2=card1+1,52 do
                     for card3=card2+1,52 do
                            for card4=card3+1,52 do
                                     for card5=card4+1,52 do
                                            for card6=card5+1,52 do
                                                     for card7=card6+1,52 do
                                                             counter = counter + 1
                                                     end
                                             end
                                     end
                             end
                     end
             end
    end
     
    print(counter)

    Code:
    paul@macbuntupro:~/code/lua$ time lua loops.lua 
    133784560
    
    real    0m5.408s
    user    0m5.016s
    sys     0m0.392s

  7. #7
    SitePoint Wizard samsm's Avatar
    Join Date
    Nov 2001
    Location
    Atlanta, GA, USA
    Posts
    5,011
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Ruby Inline comes to mind for the speed problem.

    Maybe I'm misunderstanding the purpose of this code but ... is examining every possible outcome a maintainable testing strategy? I'm imagining testing a login form by trying every possible password.
    Using your unpaid time to add free content to SitePoint Pty Ltd's portfolio?

  8. #8
    SitePoint Guru
    Join Date
    Aug 2005
    Posts
    986
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Yes, examples are better. Unit tests are good if they're fast: testing should be cheap. Try to prove (like, mathematically) that your code is correct if you need to be certain.

    I doubt Ruby Inline will help, because performing the function to be tested in the loop is going to be more expensive than the loop.

  9. #9
    SitePoint Enthusiast
    Join Date
    Feb 2005
    Posts
    27
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    My application is an evaluator for 7 card poker hands, it finds the best 5 card hand. This isn't a unit test so much as a proof that I am generating the correct number of the different types of hands. These hand type checksum values are widely available, which lets me be confident that my algorithm is correct.

    That said, I do have a pretty comprehensive set of unit tests that gives me a high degree of certainty, I would just like to be able to compare my overall figures to the checksums, and to do that I need to check every possible hand combination.

    I am actually looking at moving the performance heavy bits of the app into a c extension, but at the minute its a bit outside of my comfort zone


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •