Re: Progressively worse performance from a table

["Leandro Candido" <enclle@...>]

Hello Edgar/scott,

    I tested the 2 codes (the one from scott and the one from Edgar), and
they aren't the same. The code from Edgar doesn't allow to add duplicated
words (lines, in code examples).

before

print ("-mark- beginning delete")

in the 2 codes, add:

totalItemsInTable = 0;
table.foreach(words,function() totalItemsInTable = totalItemsInTable + 1
end);
print("Number of items in table words:",totalItemsInTable);

The result will be different for scott's and for Edgar's code.
This is because in the Edgar's code, if the item is already in the table, it
isn't added twice. This is a good thing, but the idea of Edgar was to mimics
the behavior from scott's code, and in this case, it isn't equal.

                                                            The God's Peace,


Leandro.



----- Original Message -----
From: "Edgar Toernig" <froese@gmx.de>
To: "Lua list" <lua@bazar2.conectiva.com.br>
Sent: Thursday, January 08, 2004 2:48 AM
Subject: Re: Progressively worse performance from a table


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