于 2013-11-2 23:23, Liam Devine 写道:
On 02/11/13 14:32, Pasi Mankinen wrote:
Hisham wrote:
After a number of times when I had to
iterate arrays, mark some
elements for removal, and then remove them in a second loop, I
wished
I'd be able to do it in one go. Doing it "by hand" with a
while loop
managing the index variable explicitly sounded cumbersome, so
it
occured to me I could write a custom iterator instead.
Hello Hisham and all, this is my first post to this great list.
Removing elements from array is classic problem that can be
solved easily with backwards loop:
print("** Remove backwards: **")
local t = { "a", "b", "c", "d", "e" }
for i=#t,1,-1 do
local v = t[i]
print(i, v)
if v == "c" then
table.remove(t, i)
end
end
Looping is extremely fast, moving items in memory is very slow.
By looping backwards we have least amount of items to move.
Think of situation where you want to remove { "a", "c", "d", "e"
} from t, in this case there will be only one memory move: "b"
from index 2 to index 1.
Basically when you optimize memory allocations and memory moves
you have optimized your code well - in any language.
Regards,
Pasi Mankinen
Finland
This is a best case senario for the situation and in your example
code it does not seem to matter what position elements are in. I
would therefore recommend not to use such as method which has a
very poor worst case instead I would personally use the same trick
which is used in C++ swap and pop.
local t = { "c", "a", "b", "c", "d", "e", "c", "f" }
local index = 1
local size = #t
while index <= size do
if t[index] == 'c' then
t[index] = t[size]
t[size] = nil
size = size - 1
else index = index + 1
end
end
That's a very nice trick, and I have used that several times. It
operates at just one end
of the array(thus 'pop'), and Lua has very good performance in this
situation.
Just to remind, this algorithm doesn't preserve the order in the
original array.
so it is suitable for the "list type" array, but not for the
"sequence type" array.
For the latter, I personally would still use the two pass method.
|