SitePoint Sponsor

User Tag List

Results 1 to 9 of 9
  1. #1
    SitePoint Guru aamonkey's Avatar
    Join Date
    Sep 2004
    Location
    kansas
    Posts
    953
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    permutations - recursive function needs speed increase

    I'm currently working on a sudoku puzzle class that will (hopefully) be able to solve ANY sudoku puzzle...yeah, i'm a little bored....

    Everything is working to this point, but I've run into a speed bump with a function I wrote to get all possible permutations of a multi-dimensional array. The function works, but it is ssssslllllooooowwww.....
    It works great on small md-arrays, but on an array with 10000 possible permutations (for example) it takes about 1/4 of a second.

    With literally millions of permutations to calculate, this obviously isn't going to work....not to mention that I will probably be facing some memory problems here soon.

    Here is the function (an excerpt from the class)....If anyone has any ideas to speed it up I would love to hear them. Recursion seemed the most obvious solution to this problem, and honestly I'm not sure how to approach this in another way:

    PHP Code:
           
               
    /*
        -- get all the possible permutations for a multidimensional array. --
           
                $mdArray should be a multi-dimensional array like so:
                
                   array(
                       array('a1', 'a2', 'a3'),
                       array('b1', 'b2'),
                       array('c1', 'c2', 'c3', 'c4'),
                   );
         */
           
               
    function getAllPermutations($mdArray$firstTime=true$tempArray=array()) {
               
                   
    // initialize results array
                   
    if ($firstTime) { $this->permutationsResultsArray = array(); }
               
                   
    // find first sub array and iterate through it
                   
    $thisArray array_shift($mdArray);
           
                   foreach (
    $thisArray as $key => $elem) {
                       
    $tempArray[] = $elem;
                       
                       if (
    count($mdArray) == 0) {
                     
    $this->permutationsResultsArray[] = $tempArray;
                       } else {
                  
    $this->getAllPermutations($mdArrayfalse$tempArray);
                       }
                       
    array_pop($tempArray);
                       
                   }
           
               } 
    thanks for any advice on this....


    [ edit ]

    after posting this, I realized a severe inefficiency in the function: since in a sudoku puzzle each number (1-9) can only be used once per row, column, and "sector", I don't actually need EVERY permutation, just the ones that contain unique combinations. changing the function to this sped it up about 40x:

    PHP Code:
          function getAllPossiblePermutations($mdArray$firstTime=true$tempArray=array()) {
          
              
    // initialize results array
              
    if ($firstTime) { $this->permutationsResultsArray = array(); }
          
              
    // find first sub array and iterate through it
              
    $thisArray array_shift($mdArray);
      
              foreach (
    $thisArray as $key => $elem) {
              
                 
    // if this number has already been used, skip this possible permutation
                  
    if (in_array($elem$tempArray)) { continue; }
                  
                  
    $tempArray[] = $elem;
                  
                  if (
    count($mdArray) == 0) {
                     
    $this->permutationsResultsArray[] = $tempArray;
                  } else {
                  
    $this->getAllPossiblePermutations($mdArrayfalse$tempArray);
                  }
                  
    array_pop($tempArray);
                  
              }
      
          } 
    i'm still looking for a faster algorithm though, if anyone can help....
    Last edited by aamonkey; Jun 3, 2006 at 17:34.

  2. #2
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Umm...

    PHP Code:
    // ...
    // initialize results array
              
    if ($firstTime) { $this->permutationsResultsArray = array(); } 
    Well you could remove the need for this, and instead class this class method first, to initialise the algorithm, and then instead of recursing from within this class method, recurse to a secondary class method, which basically does the same thing yes?

    So, you can execute the first recursive class method to act as the catalyst, and from there, continue the recursion from the secondary class method, which therefore returns the results for you.

    Also, is there not a way to remove the temp. store? If you could remove that as well, then that may help.

  3. #3
    SitePoint Enthusiast
    Join Date
    Mar 2005
    Posts
    94
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    The best way to optimize speed of recursive algorithms, is to remove the
    recursion. This is easily done with a while loop and an array that emulates
    the callstack.
    I've also done some more subtle optimizations like the isset() vs. count() and
    redundant negation. This version is two times faster now.
    The code looks a litte bit ugly but i hope you get the idea.

    Of course optimizing the algorithm logic could bring up more performance,
    but thats too much for a rainy sunday.

    PHP Code:
        function getAllPossiblePermutations2($MdArray, &$Result, &$TempArray=array())
        {
            
    $stack = array(array($MdArray, &$Result, &$TempArray));
            while (
    $arg array_pop($stack))
            {
                
    $mdArray =& $arg[0];
                
    $result =& $arg[1];
                
    $tempArray =& $arg[2];
                
    $thisArray array_shift($mdArray);
                foreach (
    $thisArray as $elem)
                {
                    if (
    in_array($elem$tempArray))
                        continue;
                    
    $tempArray[] = $elem;
                    if (isset(
    $mdArray[0])) {
                        
    $stack[] = array($mdArray, &$result, &$tempArray);
                    } else {
                        
    $result[] = $tempArray;
                    }
                    
    array_pop($tempArray);
                }
            }
        } 

  4. #4
    SitePoint Guru aamonkey's Avatar
    Join Date
    Sep 2004
    Location
    kansas
    Posts
    953
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    thanks for the help guys....

    Dr. Livingston--
    I did notice a small speed increase removing the boolean and using 2 class methods. unfortunately i can't get rid of the tempArray, as that's where each permutation is stored. I appreciate the help.

    elias--
    I tried your way (very nice btw--it never occured to me that you could fake recursion like that), but didn't notice a 2x speed difference....using isset() instead of count() made a noticable difference, but when the functions were identical with 1 using recursion and one without, the speeds were pretty much identical.

  5. #5
    SitePoint Enthusiast
    Join Date
    Mar 2005
    Posts
    94
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by aamonkey
    but when the functions were identical with 1 using recursion and one without, the speeds were pretty much identical.
    Yes this happens if you don't have much to "recurse". With your example
    array from above you'll not gain much performance, but if you extend it
    like this:

    PHP Code:
    array(
         array(
    'a1''a2''a3'),
         array(
    'b1''b2'),
         array(
    'c1''c2''c3''c4'),
         array(
    'd1''d2''d3''d4'),
         array(
    'e1''e2''e3''e4'),
         array(
    'f1''f2''f3''f4'),
    ); 
    the non-recursive version will speed up. Here is a small benchmark to see the proportions.

    Code:
    //your example array
    1 - 0.000317
    2 - 0.000241
    
    //extended array
    1 - 0.016237
    2 - 0.008070

  6. #6
    SitePoint Guru aamonkey's Avatar
    Join Date
    Sep 2004
    Location
    kansas
    Posts
    953
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I've probably screwed up something in your code then....I've been testing on an array with 30,000+ possible permutations, and I was getting some errors / incorrect results, so I modified the code to this:

    PHP Code:
       
       $tempArray 
    = array();
       
       function 
    getAllPossiblePermutations2($mdArray, &$result, &$tempArray) {
       
               
               
    $stack = array(array($mdArray, &$result, &$tempArray));
               
               while (
    $arg array_pop($stack)) {
                   
                   
    $mdArray =& $arg[0];
                   
    $result =& $arg[1];
                   
    $tempArray =& $arg[2];
                   
    $thisArray array_shift($mdArray);
       
                   foreach (
    $thisArray as $elem) {
                       if (
    in_array($elem$tempArray)) { continue; }
                       
                       
    $tempArray[] = $elem;
                       if (isset(
    $mdArray[0])) {
                      
    $stack[] = array($mdArray, &$result$tempArray);
                       } else {
                           
    $result[] = $tempArray;
                       }
                       
    array_pop($tempArray);
               }
           }
       } 
    I couldn't get the function argument "&$tempArray=array()" to work -- I kept getting an "unexpected '(' in line [ function line]" error. I think I read something about this being available in php 5, unfortunately I'm still stuck on vs. 4. Also, when I used the line
    PHP Code:
       $stack[] = array($mdArray, &$result, &$tempArray); 
    the function did not work...it worked when I removed the $temparray reference (as in code above), but I'm not seeing the speed increase...

  7. #7
    SitePoint Enthusiast
    Join Date
    Mar 2005
    Posts
    94
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by aamonkey
    I couldn't get the function argument "&$tempArray=array()" to work -- I kept getting an "unexpected '(' in line [ function line]" error. I think I read something about this being available in php 5, unfortunately I'm still stuck on vs. 4.
    Oh yes i'm runnning php5.2dev here and have no php4.

    Quote Originally Posted by aamonkey
    but I'm not seeing the speed increase...
    Edit:


    Two mistakes:
    - benchmarked versus your first implementation
    - wrong results

    Now i've got almost the same performance with recursive and non recursive
    versions too. Well, the latter will never smash on recursion limits.
    Last edited by elias; Jun 5, 2006 at 06:24.

  8. #8
    SitePoint Wizard DougBTX's Avatar
    Join Date
    Nov 2001
    Location
    Bath, UK
    Posts
    2,498
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by aamonkey
    i'm still looking for a faster algorithm though, if anyone can help....
    There was a competition here to write a sudoku solver, it's all open ssource so you can see quite a few ways people have tried to do it if you want some ideas.

    Douglas
    Hello World

  9. #9
    SitePoint Guru aamonkey's Avatar
    Join Date
    Sep 2004
    Location
    kansas
    Posts
    953
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    thanks DougBTX,

    if only I could read Ruby....

    I did manage to wade my way through a few scripts and got a couple ideas off of that.

    That site is great, btw....almost makes me want to convert to Ruby just to participate (if only there were a php equivalent!)--thanks much for the link


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
  •