[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Sieve of Eratosthenes performance question
- From: Rici Lake <lua@...>
- Date: Wed, 6 Jun 2007 13:33:27 -0500
On 6-Jun-07, at 1:27 PM, Shoaib Meenai wrote:
On 6/6/07, Philippe Lhoste <PhiLho@gmx.net> wrote:
... I believe the difference is because I made 'composite' an array
contiguous numerical indexes, with optimized access in Lua 5.1 (direct
offset computing), while in the previous code, Lua probably has to
more complex tests (hashing the index?) to see if the slot is empty
Might be a stupid question, but would the optimization apply even if
the first index was, say, 1296?
Probably not. The optimization requires (roughly) that the array uses
than half of the indices in the range [1, 2^k] for some integer k (and
applies to the indices in that range: anything outside of the range is
stored in the hash part of the table).