Page 1 of 1
Loops
Posted: Sat Jun 25, 2011 6:11 pm
by 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?
Re: Loops
Posted: Sat Jun 25, 2011 6:48 pm
by 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.
Re: Loops
Posted: Sat Jun 25, 2011 7:24 pm
by 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
Re: Loops
Posted: Sun Jun 26, 2011 5:38 am
by 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
Re: Loops
Posted: Mon Jun 27, 2011 4:09 am
by 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.
Re: Loops
Posted: Mon Jun 27, 2011 5:12 pm
by Brittgriscom
That's what I had to begin with. It was slow, so I'm trying to speed it up.
Re: Loops
Posted: Mon Jun 27, 2011 7:34 pm
by FourthWorld
Slow? How many items are in that list?
Re: Loops
Posted: Mon Jun 27, 2011 10:44 pm
by Brittgriscom
Several hundred, and it is being resorted continuously.
Re: Loops
Posted: Mon Jun 27, 2011 11:28 pm
by 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.
Re: Loops
Posted: Tue Jun 28, 2011 3:11 pm
by 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.
Re: Loops
Posted: Tue Jun 28, 2011 4:01 pm
by FourthWorld
Brittgriscom wrote: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.
Re: Loops
Posted: Tue Jun 28, 2011 4:32 pm
by 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?
Re: Loops
Posted: Tue Jun 28, 2011 4:59 pm
by FourthWorld
Brittgriscom wrote:
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.
Re: Loops
Posted: Tue Jun 28, 2011 6:08 pm
by 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.
Re: Loops
Posted: Wed Jun 29, 2011 9:03 pm
by Brittgriscom
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