Lua 5.1 # operator and string comparison (performance)
For this:
b = #{1,2,3}
c = 'deadbeef' == 'deadbabe'
Does b compute in O (n) or O (1)? What scenario? Is the behavior sequential or context-specific like the behavior of sparse arrays? Is string comparison O (1) or O (n)? I know strings are immutable and Lua compares hash values, but what if 2 different string hashes have the same value? Please don't answer "Don't worry about low-level behavior, son." I am interested in low-level behavior. Thank.
EDIT
3) Is the result # stored somewhere, or is it calculated every time I call it on the same array?
source to share
The length of tables is calculated in O(log n)
. The algorithm looks like this:
- Try to find the integer index mapped to
nil
by taking a step. The step size is doubled each time. (If you find the valuenil
at the end of a portion of the array, you can skip that portion.) - When such an index is found, use the division-and-rest algorithm between that index and the last known not index
nil
to find the non valuenil
followed by the valuenil
.
See here for details . This algorithm works well if you have a continuous sequence of values, but can produce unexpected results if there are gaps in the array.
EDIT: The results of the inline statement are #
not cached, so the above algorithm is executed every time you use #
on the table (no __len
metamethod).
Regarding string comparison (for equality): Newer versions of Lua have two types of strings internally: short strings (usually up to 40 bytes) and long strings. Long strings are compared using memcmp
(if the lengths are the same), which is why you get O(n)
. On the other hand, short strings are "interned", which means that when a specific short string is created in Lua, it checks to see if a string with the same content exists. If so, then the old line object is reused and no new line is allocated. This means that you can simply compare the memory address, to verify that short lines, that is O(1)
.
source to share
Lua strings are stored in a table to avoid creating duplicates of the same strings, so every time a string is created it has to be hashed and compared to something with the same hash value as it was created.
Comparing string objects after creation is O (1) as Lua already provided a reference to a unique string, so Lua just compares the base pointers.
since the whole string is internalized, string equality becomes pointer equality
#define eqstr(a,b) ((a) == (b))
lstring.h
x = "deadbeef" -- put in string table
y = "deadbabe" -- put in string table
c = x == y -- compared pointers
In the example table below
From injecting ltabl.c: int luaH_getn (Table * t) :
t = {1, 2, 3} -- requires creating a table, hashing all the values etc.
b = #t -- constant time as array part is full and no hash part (ergo # is the array size)
t = [3] = nil
b = #t -- boundary inside array part, binary search in array, b=2
b = #t -- another binary search
t = {1, 2, 3, [1000]=4}
b = #t -- array is full, and 4 is not a key in the hash, b = 3
source to share