lua idiom: iteration with skips?

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

lua idiom: iteration with skips?

Gregg Reynolds-2-2
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

Reply | Threaded
Open this post in threaded view
|

RE: lua idiom: iteration with skips?

jdarling
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

Reply | Threaded
Open this post in threaded view
|

Re: lua idiom: iteration with skips?

David Given
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.org

iD8DBQFERnNtf9E0noFvlzgRAmmYAJ9VapcHbDZKQ6f40zZdkXV2OHOtRACglYy4
Lo4oQR2Q+w2nHHLW3eR8WdQ=
=HsA6
-----END PGP SIGNATURE-----
Reply | Threaded
Open this post in threaded view
|

Re: lua idiom: iteration with skips?

Greg Falcon
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.8
paying 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
Reply | Threaded
Open this post in threaded view
|

Re: lua idiom: iteration with skips?

Luiz Henrique de Figueiredo
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
Reply | Threaded
Open this post in threaded view
|

Re: lua idiom: iteration with skips?

Matthew M. Burke-2
In reply to this post by Gregg Reynolds-2-2
Gregg Reynolds wrote:

>
> 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.
>


Here's yet another way to skin this cat.  I think it's fairly lua-ish
because a number of other languages don't allow you to take this approach:



function hopscotch(table, processor)
   local index = 1
   return function ()
            if (table[index] == nil) then
               return nil
            else
               local i = index
               index = index + processor(table[index])
               return i, table[i]
            end
         end
end


t = {20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,
37, 38, 39}

--- if the value is even, we'll skip ahead 3
-- otherwise, we'll skip ahead 5
function p(v)
    if ( math.floor(v/2) == v/2) then
       return 3
    else
       return 5
    end
end


for k,v in hopscotch(t, p) do
    print(k, v)
end



Matt

Reply | Threaded
Open this post in threaded view
|

Re: lua idiom: iteration with skips?

Wim Couwenberg-2
>     if ( math.floor(v/2) == v/2) then

Note that Lua 5.1 introduced the % operator, so this can be written as

      if v%2 == 0 then

--
Wim