Re: Progressively worse performance from a table

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

On Thu, Jan 08, 2004 at 05:48:28AM +0100, Edgar Toernig wrote:
> 
> 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
> 

Doh! Thanks for the reminder.  Well, at least that discussion will now show
up under another set of search terms in the archive. :)

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

[good code snipped]

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

You called it.  

real    0m1.062s 
user    0m0.940s

I really appreciate the lesson.  And the indirect reminder that tables in
Lua are _NOT_ hash tables in Perl.  Order is preserved, which was one of
requirements of my application (although not evident in the simplified
sample I presented.)  Maybe I'll finally be able to remember that about
tables now.

As I was typing this, my producer handed me the freshly arrived 'Programming 
in Lua' book ordered around Dec 15th from Amazon US.  Maybe with its help, 
I can shake the habit of C-like algorithms for good!

scott

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