Re: Progressively worse performance from a table

[Joe Myers <joe31416@...>]

Edgar's posting was a very interesting read.

However, if you replace
     for idx,word2 in pairs(words) do -- loop foo

with
     for idx,word2 in ipairs(words) do -- loop foo

it will become delightfully perky. This takes advantage that you're
deleting words in the same order as their occurance, of course.

Joe


On Wed, 7 Jan 2004, 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
>
> -------------------------------------------------------------------
>
> 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
> ------------------------------------------------------------------------
>