# lua idiom: iteration with skips?

7 messages
Open this post in threaded view
|

## lua idiom: iteration with skips?

 Hi, I need to iterate over a list of items with skip logic.  For example, if item[i] fits some criteria, then skip to item[i+n] else skip to item[i+m]. If I understand the manual, altering an iteration variable is a no-no, so I can't use a for loop for this. So here's what I come up with using recursion in psuedo-code: input = { ... } output = { ... } function process(i)   ... use input[i] to update output[i]   if ( ... test output[j]... ) then      process(i+m)   else      process(i+n)   end process(1) or the like.  (I haven't tested this yet.)  My question is, what is the natural, idiomatic way to do this sort of thing in lua?  I'm new to it, so I want to learn the lua way. -gregg
Open this post in threaded view
|

## RE: lua idiom: iteration with skips?

 I can't say what the "Typical Lua" way of doing this is, but as a general point of view I can say that with some knowns this becomes a trivial process not requiring recursion. Knowns:   1) Indexing is done with a numerical method (IE: You don't use MyTable['MyIndex'] instead you use MyTable[1]..MyTable[n] where n is the largest element)   2) Indexing has no breaks (see #1, basically you don't go 1, 2, 5, 6, 7 instead you have 1, 2, 3, 4, 5, 6, 7)   3) Processing happens in a depth first aproach If these are true then you can do something as follows (untested) input = {MyVal1, MyVal2, MyVal3} output = {} function Process(AnInput, AnOutput, n=1, m=2)   local processStack = {}   table.insert(processStack,1)   while table.getn(processStack)>0 do     local tblIndex = processStack[table.getn(processStack)]     AnOutput[tblIndex] = AnInput[tblIndex]     table.remove(processStack,tblIndex)     if (AnInput[tblIndex]~=nil) then       if (... test AnOutput[tblIndex]) then         table.insert(processStack, tblIndex+m)       else         table.insert(processStack, tblIndex+n)       end     end   end end Process(input, output) Using this method should lower the Lua stack overhead and produce a lower running cost overall.  Of course you MUST make sure that the first if statement tests to make sure that the index is vald, this may involve editing the line "if (AnInput[tblIndex]~=nil) then" quite a bit.  - Jeremy "Help I suffer from the oxymoron Corporate Security." > -------- Original Message -------- > Subject: lua idiom: iteration with skips? > From: Gregg Reynolds <[hidden email]> > Date: Wed, April 19, 2006 11:49 am > To: lualist <[hidden email]> > > Hi, > > I need to iterate over a list of items with skip logic.  For example, if > item[i] fits some criteria, then skip to item[i+n] else skip to item[i+m]. > > If I understand the manual, altering an iteration variable is a no-no, > so I can't use a for loop for this. > > So here's what I come up with using recursion in psuedo-code: > > input = { ... } > output = { ... } > function process(i) >   ... use input[i] to update output[i] >   if ( ... test output[j]... ) then >      process(i+m) >   else >      process(i+n) >   end > process(1) > > or the like.  (I haven't tested this yet.)  My question is, what is the > natural, idiomatic way to do this sort of thing in lua?  I'm new to it, > so I want to learn the lua way. > > -gregg
Open this post in threaded view
|

## Re: lua idiom: iteration with skips?

 In reply to this post by Gregg Reynolds-2-2 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Gregg Reynolds wrote: [...] > So here's what I come up with using recursion in psuedo-code: [...] >   if ( ... test output[j]... ) then >      process(i+m) >   else >      process(i+n) >   end That'll work, but you need to say 'return process(i+m)' to allow tail recursion to kick in, otherwise you'll use lots of stack space. Plus, every time you call process() the system will have to generate a new closure. This isn't particularly expensive, but it's more expensive than a simple loop. I'd be inclined just to do the simple, naïve thing: local i = 1 while true do     ...do action here...     if (test output[j]) then       i = i + m     else       i = i + n     end end (You don't mention any kind of termination condition.) > My question is, what is the > natural, idiomatic way to do this sort of thing in lua?  I'm new to it, > so I want to learn the lua way. The Lua way is to do what *you* want. The language is sufficiently flexible that it can be molded to suit your needs. There are things it's good it, but it's fundamentally there for you pleasure. What idiom are you comfortable using? Sorry, that probably wasn't helpful... (Just out of interest, is the byte-code compiler intelligent enough to optimise 'while true do'... into a noop? Because it's a very common idiom.) - -- +- David Given --McQ-+ |  [hidden email]    | "Those that repeat truisms, are also forced to | ([hidden email]) | repeat them." --- Anonymous from Slashdot +- www.cowlark.com --+ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.orgiD8DBQFERnNtf9E0noFvlzgRAmmYAJ9VapcHbDZKQ6f40zZdkXV2OHOtRACglYy4 Lo4oQR2Q+w2nHHLW3eR8WdQ= =HsA6 -----END PGP SIGNATURE-----
Open this post in threaded view
|

## Re: lua idiom: iteration with skips?

 In reply to this post by Gregg Reynolds-2-2 On 4/19/06, Gregg Reynolds <[hidden email]> wrote: > So here's what I come up with using recursion in psuedo-code: > > input = { ... } > output = { ... } > function process(i) >   ... use input[i] to update output[i] >   if ( ... test output[j]... ) then >      process(i+m) >   else >      process(i+n) >   end > process(1) > > or the like.  [...] I'd like to point out that Lua is propery tail recursive, so if you replace the line "process(i+m)" with "return process(i+m)" and so on, the Lua virtual machine will be able to run your program without any additional stack overhead.  (I am assuming you meant to put an "end" before "process(1)", so that the recursive call was the very last thing executed in your function.) Using tail recursion is a fine way to solve a problem.  Be careful, though; some things that look like tail calls aren't.  Refer to the manual at   http://www.lua.org/manual/5.1/manual.html#2.5.8paying close attention to the examples at the end of the section. Note that I probably would have solved your problem with a repeat loop, something like (untested code follows): local i=1 repeat   ... use input[i] to update output[i]   if ( ... test output[i] ... ) then     i=i+m   else     i=i+n   end until   ??? (you never specified your exit condition) But there's nothing wrong with using recursion here. Greg F
Open this post in threaded view
|

## Re: lua idiom: iteration with skips?

 In reply to this post by David Given > (Just out of interest, is the byte-code compiler intelligent enough to > optimise 'while true do'... into a noop? Because it's a very common idiom.) Definitely. See for yourself with         echo 'while true do end' | luac -l -p - This will print         1 [1] JMP       -1 ; to 1         2 [1] RETURN   0 1 Note that there is just a jump instruction, no test. The code generator does several other optimizations like that. --lhf