Loops

[Brittgriscom]

I am trying to use a binary heap sort to speed up an A* Algorithm. You don't need to know how to do that to help me though. I just need help with loops. Basically, I'm trying to have the smallest number bubble up to the top of a list. I don't want to do a conventional sort though, because that makes my algorithm slow. Binary heaps are a way to have the smallest number bubble up to the top, while leaving the rest essentially in a heap.

The stack is attached, but my code as it stands is this:

Code: Select all

on mouseUp
   repeat with m = 1 to 9
      put line m of fld 1 into line m of fld 2
      put m/2 - (m mod 2)/2 into tNoRemainder
      if line m of field 2 <= line tNoRemainder of fld 2 then
         put line tNoRemainder of fld 2 into tTemp
         put line m of fld 2 into line tNoRemainder of fld 2
         put tTemp into line m of fld 2
      end if
      repeat while tNoRemainder > 1
         put tNoRemainder into n
         put n/2 - (n mod 2)/2 into tNoRemainder
         if line n of field 2 <= line tNoRemainder of fld 2 then
            put line tNoRemainder of fld 2 into tTemp
            put line n of fld 2 into line tNoRemainder of fld 2
            put tTemp into line n of fld 2
         end if
      end repeat
   end repeat
end mouseUp

This works, but it is redundant. Also, I need to round down on every m/2 and I use a clumsy way of doing that. Is there a better way to round down?

[jacque]

Have you looked at the built-in sort commands? They will be far faster than what you're trying to do. You can sort descending by several criteria in order to get the smallest values to the top.

Your code, as written, will be very slow. Moving data in and out of fields is just about the slowest thing you can do. Repeat loops can also be slow, and repeat loops that use a counter variable are the slowest type (though with only 9 instances in the counter, it won't be that noticable.) If you do want to write your own sort routines then you should put the field contents into a variable and work with that in RAM.

Assuming your values are all numeric, this will place the smallest numbers at the top:

put fld 1 into tData
sort tData descending numeric

You can also provide a custom sorting function and pass that to the sort command. If you can explain a little more what results you want, we can help you do that.

Also, if all you really want is to extract the smallest value, take a look at the min() function in the dictionary. Just feed it your list and it will spit back what you want.

[jacque]

I downloaded your stack. Is this what you want?

Code: Select all

on mouseup
  get fld 1
  replace cr with comma in it
  put min(it)
end mouseup

[Brittgriscom]

That works for that stack, but that stack is really a simple version of what I'm trying to do. I'm really trying to speed up the A* algorithm in the 8-puzzle in the runrev lessons.

I have a variable called pStatesToExplore that looks like this

Code: Select all

08,04, 04 01 03 09 02 06 05 08 07, 09 01 03 04 02 06 05 08 07
06,01 02, 01 02 03 04 09 06 05 08 07, 01 09 03 04 02 06 05 08 07, 09 01 03 04 02 06 05 08 07
08,01 03, 01 03 09 04 02 06 05 08 07, 01 09 03 04 02 06 05 08 07, 09 01 03 04 02 06 05 08 07

The first comma-delimited item of each line shows the manhattan distance from the goal.
The second item shows the path taken (the tiles moved) so far.
The third item shows the states we have gone through to get to the current state.

As the algorithm searches along different paths, it generates many many lines of possible paths. I want to continually bring the shortest-cost path to the top of the list. I want to do this without sorting the whole list, because that takes too long.

The min() function looks promising. How would I adapt it to this?

I'd love to attach my stack, but it is way too big. Here is my current code:

Code: Select all

      #binary heap sort
   put the number of lines of pStatesToExplore into n
   repeat while tNoRemainder > 1
         #round down
      put n/2 - (n mod 2)/2 into tNoRemainder
      if item 1 of line n of pStatesToExplore <= item 1 of line tNoRemainder of pStatesToExplore then
         #bubble up the smaller one
         put line tNoRemainder of pStatesToExplore into tTemp
         put line n of pStatesToExplore into line tNoRemainder of pStatesToExplore
         put tTemp into line n of pStatesToExplore
      end if
            put tNoRemainder into n
   end repeat
  

[jacque]

I confess to being confused about what you're trying to do. Are you just looking for the smallest first item of all the lines? If so:

sort pStatesToExplore numeric by item 1 of each

That will pop the smallest one to the top. It will only look at the first item. Take a look at the "sort" command in the dictionary, there are so many ways to handle it that I've never needed to write one of my own. If the built-in ways don't work you can usually write a custom function and sort by that, but in this case I don't think you'll need to.

LiveCode uses a very fast sort, I don't think speed will be an issue.

[Brittgriscom]

That's what I had to begin with. It was slow, so I'm trying to speed it up.

[FourthWorld]

Slow? How many items are in that list?

[Brittgriscom]

Several hundred, and it is being resorted continuously.

[FourthWorld]

You recently mentioned that your original code used the sort command. Can you post that code?

If it's working but just slow, I'll bet there's a relatively painless way to get an order of magnitude speed boost out of it. I might be wrong, but with all the field references and "repeat with" statements in the later example you posted here my hunch is we can get that original version with "sort" working well for you.

[Brittgriscom]

Code: Select all

   #original sort
   --   sort lines of pStatesToExplore numeric by item 1 of each

An even bigger culprit is this function, which compares every new board state to the hundreds or thousands of board states we have seen before:

Code: Select all

#tests if we have seen that state before
function stateMatch pPath, pPathList     
   local tPath, tLineCount     
   repeat for each line tPath in pPathList 
      #give time to move tiles and update timer 
      wait 0 milliseconds with messages      
       add 1 to tLineCount         
      if item 3 of tPath is item 3 of pPath 
      then             
         return tLineCount         
      end if     
   end repeat     
   return false
end stateMatch

That function is called by this handler:

Code: Select all

command pruneStateSpace pNewPaths, @pStatesToExplore, @pExploredStates     
   local tPath, tStatesToExploreDuplicate, tExploredStatesDuplicate, tAddFlag  
    repeat for each line tPath in pNewPaths         
      put false into tAddFlag         
      # find out if the new state to explore exists          
      # as a head in one of the already explored states         
      put stateMatch (tPath, pExploredStates) into tExploredStatesDuplicate         
      # find out if the new state to explore exists         
      # as a head in one of the states that are still to be explored         
      put stateMatch (tPath, pStatesToExplore) into tStatesToExploreDuplicate         
      if tExploredStatesDuplicate is false and tStatesToExploreDuplicate is false 
      then             
         # if we found no match, then set a flag to add the new path             
         # to the paths that are to be explored             
         put true into tAddFlag         
      else if tExploredStatesDuplicate is not false and item 1 of tPath < \            
       item 1 of line tExploredStatesDuplicate of pExploredStates then              
         # if we found a match with the states we already explored and the new path             
         # is cheaper then remove the matched state from the explored states            
          # and set the flag to add the new path to the paths that are to be explored             
         delete line tExploredStatesDuplicate of pExploredStates             
         put true into tAddFlag         
      else if tStatesToExploreDuplicate is not false and item 1 of tPath < \            
       item 1 of line tStatesToExploreDuplicate of pStatesToExplore then             
          # if we found a match with the states we have not yet explored and the new             
         # path is cheaper then remove the matched state from the unexplored states             
         # and set the flag to add the new path to the paths that are to be explored             
         delete line tStatesToExploreDuplicate of pStatesToExplore              
         put true into tAddFlag         
      end if         
      # if tAddFlag is set then add the new path to the paths that are to be explored         
      # any new paths that exist for which tAddFlag is not set to true are skipped         
      if tAddFlag is true then            
          if pStatesToExplore is not empty then                 
            put cr after pStatesToExplore             
         end if             
         put tPath after pStatesToExplore         
      end if     
   end repeat 
end pruneStateSpace

This is all code from the A* Algorithm Lesson:
http://lessons.runrev.com/spaces/lesson ... e-Using-A-

Do you know what it means when a parameter has '@' in front of it, as in '@pExploredStates'?

The board state-matching function is so slow, I'm considering just leaving it out.

[FourthWorld]

Code: Select all

   #original sort
   --   sort lines of pStatesToExplore numeric by item 1 of each

If that's the routine that ran slowly, it may be helpful to see the entire handler. The sort command is implemented internally in reasonably efficient C++, so aside from the modest overhead of packaging up the data to hand off to it, it's likely not the source of performance issues.

Do you know what it means when a parameter has '@' in front of it, as in '@pExploredStates'?

@ is used when passing a variable by reference; without it, variables as passed by value.

[Brittgriscom]

If that's the routine that ran slowly, it may be helpful to see the entire handler. The sort command is implemented internally in reasonably efficient C++, so aside from the modest overhead of packaging up the data to hand off to it, it's likely not the source of performance issues.

The main culprit, as I said, is the function above, which seeks to match each new board state with every previous board state. I'm actually considering leaving it out.

@ is used when passing a variable by reference; without it, variables as passed by value.

What is the difference?

[FourthWorld]

If that's the routine that ran slowly, it may be helpful to see the entire handler. The sort command is implemented internally in reasonably efficient C++, so aside from the modest overhead of packaging up the data to hand off to it, it's likely not the source of performance issues.

The main culprit, as I said, is the function above, which seeks to match each new board state with every previous board state. I'm actually considering leaving it out.

Ah, I had misunderstood. I'll see if I can get some time to look into that later today, but offhand I can see a couple things that can boost performance dramatically:

1. Using "repeat for each..." is much faster than using "repeat with i =...", and avoiding "get line <lineNumber>..." within a loop can be very helpful as well, for the reasons described here:
http://lists.runrev.com/pipermail/use-l ... 19032.html

2. Accessing data in fields is much slower than accessing data in a variable. For a long but hopefully enjoyable metaphor explaining why this is the case, this may be a fun read:
http://lists.runrev.com/pipermail/use-l ... 11478.html

Also, this article offers general tips on measuring performance:
http://livecodejournal.com/tutorials/be ... vtalk.html

@ is used when passing a variable by reference; without it, variables as passed by value.

What is the difference?

Passing by value copies the contents of the variable into the parameter of the receiving handler, so the data the receiving handler works on is a duplicate, leaving the original data in the calling handler untouched. Passing by reference uses a pointer to the original data, so the receiving handler is working on the same original data. Both are useful, but in different circumstances.

If you're going to be altering the data to extract a new value (such as one might do in crafting a pull-parser, which chops items off the front as it goes) and you'll still need the original data in the calling handler for other operations, passing by value is ideal.

But if the handler being called will be returning the data in a modified form and you want to use that modified form in the calling handler, passing by reference is a simpler way to do that, so you can write "ModifyData tData" instead of "put ModifiedData(tData) into tData".

Another minor benefit to passing by reference is that when working with really large data (many MBs) it can save a little memory, since it doesn't need to make a copy of the data when passing it along to another handler.

[Brittgriscom]

Thank you very much.

I think there may be a more fundamental problem with my code, because if I understand correctly, no board state in the 8-puzzle should be more than 24 moves from its starting position. However, my path-finding algorithm is often searching 26 moves deep. In other words, I think it is somehow missing the best path.

If you'd like to see my stack, I could put it in dropbox.

[Brittgriscom]

1. Using "repeat for each..." is much faster than using "repeat with i =...", and avoiding "get line <lineNumber>..." within a loop can be very helpful as well, for the reasons described here:
http://lists.runrev.com/pipermail/use-l ... 19032.html

When I try that, I get a syntax error:
card "New Puzzle": compilation error at line 52 (repeat: bad termination condition) near "button", char 18

Here's the code I tried it with:

Code: Select all

      repeat for each button tButton of group "Bot"
         if tButton < 10 then
            put 0 before tButton
         end if
         # get the x and y positions of the button (converts array into game grid)
         #Where it should be
         put (wordOffset (tButton, sWinningState) - 1) mod sTilesX into tButton1H
         put (wordOffset (tButton, sWinningState) - 1) div sTilesY into tButton1V
         #Where it is
         put (wordOffset (tButton, pBoardState) - 1) mod sTilesX into tButton2H
         put (wordOffset (tButton, pBoardState) - 1) div sTilesY into tButton2V
         add abs (tButton1H - tButton2H) + abs (tButton1V - tButton2V) to tBotResult
      end repeat