killing a set of elements from a list...

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Mr. Strange
Party member
Posts: 101
Joined: Mon Aug 11, 2008 5:19 am

killing a set of elements from a list...

Post by 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
Prole
Posts: 24
Joined: Tue Aug 12, 2008 11:43 am

Re: killing a set of elements from a list...

Post by emonk »

Mr. Strange wrote: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.
Sarcasm - just one of the services I offer.
Mr. Strange
Party member
Posts: 101
Joined: Mon Aug 11, 2008 5:19 am

Re: killing a set of elements from a list...

Post by 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
User avatar
mike
Administrator
Posts: 364
Joined: Mon Feb 04, 2008 5:24 pm

Re: killing a set of elements from a list...

Post by mike »

Moved to Support and Development, because I can.
Now posting IN STEREO (where available)
surtic
Citizen
Posts: 74
Joined: Sat Jul 12, 2008 12:18 am

Re: killing a set of elements from a list...

Post by 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
Party member
Posts: 101
Joined: Mon Aug 11, 2008 5:19 am

Re: killing a set of elements from a list...

Post by Mr. Strange »

surtic wrote: 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
Citizen
Posts: 74
Joined: Sat Jul 12, 2008 12:18 am

Re: killing a set of elements from a list...

Post by 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.
User avatar
Jake
Prole
Posts: 27
Joined: Sun Jul 20, 2008 2:01 pm

Re: killing a set of elements from a list...

Post by 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
Prole
Posts: 24
Joined: Tue Aug 12, 2008 11:43 am

Re: killing a set of elements from a list...

Post by emonk »

Mr. Strange wrote: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).
Mr. Strange wrote: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.
Lua 5.1 Reference Manual wrote: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.
Sarcasm - just one of the services I offer.
Mr. Strange
Party member
Posts: 101
Joined: Mon Aug 11, 2008 5:19 am

Re: killing a set of elements from a list...

Post by Mr. Strange »

emonk wrote: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
Post Reply

Who is online

Users browsing this forum: No registered users and 55 guests