Re: Progressively worse performance from a table

[Edgar Toernig <froese@...>]

scott wrote:
> 
> 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
> 
> -------------------------------------------------------------------

You experience the O(n) behaviour of next (which is used by pairs)
where n is not the number of elements in the table but the currently
allocated size of the table.  See the recent thread:

  http://lua-users.org/lists/lua-l/2003-11/msg00247.html


> Is there something I can do to keep the table perky after a series of
> deletions?

You have to add some elements.  A table will only be reorganized
when it runs out of space.

> Is there anything I did wrong?

Yes, you use a C-like algorithm ;-)  The Lua way is to use the word
as the key in the table:

----------
#!/usr/local/bin/lua

words = {}
numWords = 0

print ("-mark- beginning read")

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

print ("-mark- beginning delete")

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

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

And I guess the "Lua version" in less then 1 second :-)

Ciao, ET.