Introduction
Recently, I’ve been exploring competitive programming with mathematics and realized that things get tough to compute with 64 bits (even 32). Because I had a specific library made in Lua, I decided to solve a specific problem through Luau to make things more simple. I soon realized that I’ve reached the maximum table element limit Luau supports. This value is 0b100000000000000000000000000 or more standardly known as 67108864 (or 2^26) elements.
The module allows you to keep track of values larger than the Roblox limit. This of course comes with some disadvantages (listed at the end).
This was also not made to be used in an actual game but rather for computing large stuff. If it is ever implemented in a game, I’d be curious to know how efficient it is and how time/memory is managed.
API
InfTable.new(tableType: ‘index’ | ‘dict’)
*Note: The default value for tableType is a dictionnary
Methods
| Method Name | Description | Argument(s) | Return Value(s) | Time Complexity |
|---|---|---|---|---|
GetChunk |
Returns the chunk at the specified index. | chunkIndex: number |
{ any }? |
O(1) |
SetChunk |
Sets the chunk at the specified index | chunkIndex: number, value: { any } |
nil |
O(1) |
GetTotalElementLen |
Returns the amount of elements in the InfTable | nil |
number |
O(n) or O(m)
|
Iterate |
Iterate through the InfTable | predicate: ((number, any, { any }) -> any?) |
predicateReturn: any? |
O(m) |
Find |
Goes through the table and finds this value | value: any |
indexInChunk: number?, indexInTable: number, chunkIndex: number? |
O(m) |
GetValueAtIndex |
Gets the value at specified index | index: any |
valueInChunk: any?, chunkIndex: number?, yourIndex: number? |
O(n) |
Add |
Add element to table | indexOrValue: any, value: any? |
nil |
O(n) |
RemoveIndex |
Remove index from table | index: any |
nil |
O(1) |
Replace |
Replace index in table | index: any, newValue: any |
nil |
O(1) |
n is the amount of chunks, and m is the amount of elements.
Usage
Usage for index based tables
local InfTable = require(game:GetService'ReplicatedStorage'.InfTable)
local t = InfTable.new('index')
local limit = 30
local i = 0
while i < limit do
i += 1
t:Add(i)
end
t:Iterate(function(index: number, value: any, chunk: { any }): boolean
if value == 4 then
return true
end
end)
print(t:Find(8))
print(t:GetTotalElementLen())
print(t:GetValueAtIndex(5))
t:Replace(5, 'replace thing')
print(t:GetValueAtIndex(5))
Usage for index & value based tables (dictionnary/map)
local InfTable = require(game:GetService'ReplicatedStorage'.InfTable)
local t = InfTable.new('dict')
local limit = 500
local i = 0
while i < limit do
i += 1
t:Add(string.char(math.random(97, 122)), 'value')
end
print(t:GetTotalElementLen())
if t:GetValueAtIndex('a') then
print('a was found')
t:Replace('a', 'replace thing')
end
print(t:GetValueAtIndex('a'))
local HttpService = game:GetService('HttpService')
local InfTable = require(game:GetService'ReplicatedStorage'.InfTable)
local t = InfTable.new('dict')
local limit = 500
local i = 0
while i < limit do
i += 1
t:Add(HttpService:GenerateGUID(false), math.random())
end
local predicateAnswer = t:Iterate(function(index: number, value: any, chunk: { any }): boolean
if value*10 > 9.8 then
return index
end
end)
print(t:GetTotalElementLen())
print(t:GetValueAtIndex(predicateAnswer))
Limitations
- You can not have mixed tables.
- Keys for dictionaries may duplicate (to fix maybe)
- Compatibility problem with functions that table in tables as argument (to fix soon)
- Less performant than the actual implementation of tables
Fun fact: Reaching 2^26 elements in a table takes under 1 second if you insert them strategically (and this is without using table.create). The same approach would take almost 15 seconds with InfTable.
Source
Expand for source code
--[[
InfTable.lua
uhi_o
A module used to store table larger than Roblox Luau's (or C's) table limit
Example:
local tableName = InfTable.new('index')
-- populate the table
local i, limit = 0, 30
while i < limit do
i += 1
t:Add({i, i*2})
end
t:Iterate(function(index: number, value: any, chunk: { any }): boolean
if value == 4 then
print('a', index)
return true
end
end)
print(t:GetValueAtIndex(5))
t:RemoveIndex(5)
print(t:GetValueAtIndex(5))
--
]]
local LIMIT = bit32.lshift(1, 26) -- Luau source code (ltable.cpp): #define MAXBITS 26 #define MAXSIZE (1 << MAXBITS)
export type InfTableObject = {
_type: string?,
_chunks: { { any } },
GetChunk: (number) -> { any }?,
SetChunk: (number, { any? }) -> (),
GetTotalElementLen: () -> (),
Iterate: ((number, any, { any }) -> any) -> (any?),
Find: (any) -> (number?, number, number?),
GetValueAtIndex: (number) -> (any?, number?, number?),
Add: (any, any?) -> (),
Replace: (number, any) -> ()
}
local module = {} :: { new: (string?) -> InfTableObject }
local function countInDict(dict: { [any]: any }): number
local res = 0
for _ in pairs(dict) do
res += 1
end
return res
end
function module.new(tableType: 'index' | 'dict')
local InfTable = {
_type = tableType or 'dict', -- assuming it is a dictionnary as default
_chunks = {}
}
function InfTable:GetChunk(index: number)
return self._chunks[index]
end
function InfTable:SetChunk(chunk, value)
self._chunks[chunk] = value
end
function InfTable:GetTotalElementLen()
local i, res = 1, 0
while self._chunks[i] ~= nil do
res += self._type == 'index' and #self._chunks[i] or countInDict(self._chunks[i])
i += 1
end
return res
end
function InfTable:Iterate(predicate)
local finish = false
local i = 1
while self._chunks[i] and not finish do
local chunk = self._chunks[i]
if self._type == 'index' then
for j = 1, #chunk do
local predicateAnswer = predicate(j, chunk[j], chunk)
if predicateAnswer then
return predicateAnswer
end
end
else
for k, v in pairs(chunk) do
local predicateAnswer = predicate(k, v, chunk)
if predicateAnswer then
return predicateAnswer
end
end
end
i += 1
end
end
function InfTable:Find(value)
local i, items = 1, 0
while self._chunks[i] do
local chunk = self._chunks[i]
local chunkLen
if self._type == 'index' then
chunkLen = #chunk
for j = 1, chunkLen do
if chunk[j] == value then return j, items+j, i end
end
else
chunkLen = countInDict(chunk)
for k, v in pairs(chunk) do
if v == value then return k, items+k, i end
end
end
i += 1
items += chunkLen
end
end
function InfTable:GetValueAtIndex(index)
local i, items = 1, 0
while self._chunks[i] do
local chunk = self._chunks[i]
local chunkLen
if self._type == 'index' then
chunkLen = #chunk
if items+chunkLen >= index then
return chunk[index-items], i, index-items
end
else
chunkLen = countInDict(chunk)
if chunk[index] then return chunk[index], i, index end
end
items += chunkLen
i += 1
end
end
function InfTable:Add(indexOrValue, value)
if indexOrValue == nil then
return warn('InfTable -> Can not insert nil for index nor value')
end
local cost = 1
local i = 0
while true do
i += 1
local chunk = self._chunks[i]
if not chunk then
if self._type == 'index' then self._chunks[i] = { indexOrValue }
else self._chunks[i] = { [indexOrValue] = value }
end
break
end
-- No space in this chunk
local chunkLen = self._type == 'index' and #chunk or countInDict(chunk)
if LIMIT - chunkLen <= cost then continue end
if self._type == 'index' then table.insert(chunk, indexOrValue) print('ins')
else chunk[indexOrValue] = value
end
break
end
end
function InfTable:RemoveIndex(index)
if index == nil then
return warn('InfTable -> Unknown index to remove')
end
local value, chunkn, chunkIndex = self:GetValueAtIndex(index)
if not value then return end
local chunk = self._chunks[chunkn]
if not chunk then return end
chunk[self._type == 'index' and chunkIndex or index] = nil
if next(chunk) == nil or countInDict(chunk) == 0 then
self._chunks[chunkn] = nil
-- Push down subsequent chunks to fill the whole
local n = 1
while self._chunks[chunkn+n] do
local chunk = self._chunks[chunkn+n]
-- Move chunk down
self._chunks[chunkn+n-1] = chunk
self._chunks[chunkn+n] = nil
n += 1
end
elseif self._type == 'index' then
-- fill in empty gaps in table
for i = chunkIndex, #chunk do
chunk[i] = chunk[i+1]
end
end
end
function InfTable:Replace(index, newValue)
if newValue == nil then
return self:RemoveIndex(index)
end
local value, chunkn, chunkIndex = self:GetValueAtIndex(index)
if not value then return end
local chunk = self._chunks[chunkn]
if not chunk then return end
chunk[chunkIndex] = newValue
end
return InfTable :: InfTableObject
end
return module
