killing a set of elements from a list...

[Mr. Strange]

... I suspect this is a pretty standard situation - so I'm wondering what a "better" solution might be:

I have a project which spawns lots of "weapon" objects, which take a variety of forms. To keep track of them, I have a table named "weapon" which I add to whenever a new weapon object is spawned. I want to delete weapons when they exceed some maximum distance from the player, which led me to something like this:

Code: Select all

for i = 1, table.maxn(weapon) do
     if((weapon[i].x - player.x)^2 + (weapon[i].y - player.y)^2 > weapon[i].killDistance) then
          table.remove(weapon, i)
     end
end

Of course, this doesn't work at all, because table.remove re-packs the table, which changes the ordinals of all the elements greater than the one I've just removed. I got around this by creating a temporary table, listing all of the elements from "weapon" which I want to remove, and then removing them all as a single operation outside of the for loop. Thusly:

Code: Select all

	local killset = {}
	
	for i = 1, table.maxn(weapon) do
		if((weapon[i].x - player.x)^2 + (weapon[i].y - player.y)^2 > weapon[i].killDistance) then
			table.insert(killset,i)
		end
	end
	
	for i = 1, table.maxn(killset) do
		local todie = killset[table.maxn(killset)]
		table.remove(killset, todie)
		table.remove(weapon, todie)
	end

This works fine, but I thought I'd put it out there for critique. Maybe it's better to do this OOP-style, and have each weapon run its own individual update? I'm not sure what hip things the kids are doing these days.

--Mr. Strange

[emonk]

Of course, this doesn't work at all, because table.remove re-packs the table, which changes the ordinals of all the elements greater than the one I've just removed.

This is less problematic if you traverse the list backwards.

Code: Select all

for i = #weapon,1,-1 do
    if not WeaponValid(weapon[i]) then
        table.remove(weapon, i);
    end;
end;

Alternatively if the weapon list is a simple Lua table (no metatables, etc) then you could just do something like:

Code: Select all

local tmp = weapon;
    weapon = {}
    for _, w in ipairs(tmp) do
        if WeaponValid(w) then table.insert(weapon, w); end;
    end;

Looks ugly, but if you're calling table.remove() a lot it could be less expensive doing it this way.

[Mr. Strange]

Awesome. Now I see that I was sort of walking the second table backwards, and that simply applying the same logic to my "weapon" table saves me half of my code.

Is there any difference betwen "table.maxn(weapon)" and"#weapon" from a speed preference? Certainly just using the length operator is cleaner looking...

--Mr. Strange

[mike]

Moved to Support and Development, because I can.

[surtic]

Is there any difference betwen "table.maxn(weapon)" and"#weapon" from a speed preference?

Using this very inaccurate code:

Code: Select all

collectgarbage("stop")

-- using table.maxn
t = {}
s = 0
t1 = os.clock()
for i = 1, 10000 do
   table.insert(t, i)
   s = s + table.maxn(t)
end
t2 = os.clock()
print(string.format("Using table.maxn: %f", t2 - t1))

-- using table.maxn without the extra lookup
t = {}
s = 0
maxn = table.maxn
t1 = os.clock()
for i = 1, 10000 do
   table.insert(t, i)
   s = s + maxn(t)
end
t2 = os.clock()
print(string.format("Using table.maxn (no lookup): %f", t2 - t1))

-- using the length operator (#)
t = {}
s = 0
t1 = os.clock()
for i = 1, 10000 do
   table.insert(t, i)
   s = s + #t
end
t2 = os.clock()
print(string.format("Using the length operator: %f", t2 - t1))

There seems to be a 300-fold speedup when using the length operator.

[Mr. Strange]

There seems to be a 300-fold speedup when using the length operator.

Ah.

Just to clarify for me then - table.maxn and # are functionally identical so long as the table is packed, correct? But if there are gaps in the table then table.maxn is probably what you really want to use.

--Mr. Strange

[surtic]

Just to clarify for me then - table.maxn and # are functionally identical so long as the table is packed, correct?

That's right.

But if there are gaps in the table then table.maxn is probably what you really want to use.

Depends what you want to use a table with gaps for. Personally I can't think of a very good reason to use table.maxn - if I use the table as a dictionary then table.maxn is quite meaningless, and if I use a table as a list then I don't want any gaps.

[Jake]

But if there are gaps in the table then table.maxn is probably what you really want to use.

If you want to count a table with gaps (or a dictionary) then writing your own count function would be best.

Code: Select all

function count(tab)
    local n = 0
    for k,v in pairs(n) do n = n + 1 end
    return n
end

local tab = {1,2,3,nil,4}

#tab -- 5
table.maxn(tab) -- 5
count(tab) -- 4

Edit: I say best, I don't know what the performance is like.

[emonk]

Just to clarify for me then - table.maxn and # are functionally identical so long as the table is packed, correct?

Pretty much, yeah. If your table has no nil values then #t == table.maxn(t).

But if there are gaps in the table then table.maxn is probably what you really want to use.

Absolutely. If your table has any nil values in it then #t is only loosely defined. This appears to be a topic of much discussion in the Lua mailing list.

2.5.5 - The Length Operator
.......
If the array has "holes" (that is, nil values between other non-nil values), then #t can be any of the indices that directly precedes a nil value (that is, it may consider any such nil value as the end of the array).

In other words, [almost] all bets are off. All you can be sure of is that t[#t+1] == nil.

[Mr. Strange]

In other words, [almost] all bets are off. All you can be sure of is that t[#t+1] == nil.

When you put it that way, it seems quite reasonable. t[#t+1] is the first empty spot, so it's always a good candidate for a location to add something. Rather than let gaps grow over time, inserting things in that manner would tend to keep your tables tightly packed.

Of course, I couldn't say how often that's something you want to do - but if it is, than the current implementations seems quite handy.

--Mr. Strange