Progressively worse performance from a table

[scott <scott+lua@...>]

I'm curious about what I can do to prevent the progressively worse
performance I am experiencing from tables.  I have written a small script
which, although useless, quickly reproduces what I am seeing.

-------------------------------------------------------------------

#!/usr/local/bin/lua

words = {}
numWords = 0

print ("-mark- beginning read")

for word in io.lines("/usr/share/dict/words") do
    numWords = numWords + 1
    words[numWords] = word
end

print ("-mark- beginning delete")

deletedWordCount = 0
for word in io.lines("/usr/share/dict/words") do
    for idx,word2 in pairs(words) do -- loop foo
        if ( word2 == word ) then
            words[idx] = nil
            break
        end
    end
    deletedWordCount = deletedWordCount + 1
    if ( math.mod(deletedWordCount, 1000) == 0 ) then
        print("-mark- " .. deletedWordCount .. " " .. table.getn(words))
    end
end

-------------------------------------------------------------------

The first thing I do is fill a table indexed by integer keys with strings.
(45392 on my test machine).  I then iterate over that same list of
strings, searching for each one in my table, removing it by setting its
indexed position in the table to nil.  Since I'm going through the list of
words to delete in the same order that I added them, the entry with the
lowest index in the table (the first word) always matches the word I want
to delete.  However the performance degrades as if were searching further
and further into the table each time to find the match.   I've verified
that the loop marked 'loop foo' above only iterates once before finding
the match, but it sure takes longer and longer to delete each set of 1000
words.  Is there anything I did wrong?  Is there something I can do to
keep the table perky after a series of deletions?  

The code above takes over a minute to run on my machine.  An
implementation of the same steps that uses data structures similar to
linked lists takes 2 seconds.  

scott


-- 
------------------------------------------------------------------------
scott jacobs                                   scott+lua@escherichia.net
------------------------------------------------------------------------