Quick profiling

p.lua

local md5 = require "main.md5"

local by_index = {}
local by_id = {}

local function time_it(fnc)
	local before = os.clock()
	fnc()
	print((os.clock() - before)*1000)
end


local function find_by_id(find_this)
	return by_id[find_this]
end

local function find_by_index(find_this)
	local id
	for i=1, #by_index do
		id = by_index[i]
		if find_this == id then
			return true
		end
	end
	return false
end

local function loop_all_index()
	local id
	local _trash = ""
	for i=1, #by_index do
		id = by_index[i]
		_trash = "well" .. "hi" .. "there"
	end
	return true
end

local function loop_all_id()
	local _trash = ""
	for id, _ in pairs(by_id) do
		_trash = "well" .. "hi" .. "there"
	end
	return true
end

function init(self)
	local before = os.clock()
	local total_elements = 1000000
	local m
	local id
	for i=1, total_elements do
		m = md5.new()
		m:update(tostring(i))
		id = md5.tohex(m:finish())
		by_id[id] = true
		by_index[#by_index + 1] = id
	end
	print("Setup", (os.clock() - before)*1000)
	
	local first = by_index[1]
	local mid = by_index[total_elements/2]
	local last = by_index[total_elements]

	print("find_by_id: first")
	time_it(function() find_by_id(first) end)
	print("find_by_id: mid")
	time_it(function() find_by_id(mid) end)
	print("find_by_id: last")
	time_it(function() find_by_id(last) end)

	print("find_by_index: first")
	time_it(function() find_by_index(first) end)
	print("find_by_index: mid")
	time_it(function() find_by_index(mid) end)
	print("find_by_index: last")
	time_it(function() find_by_index(last) end)

	print("loop: loop_all_id")
	time_it(loop_all_id)
	
	print("loop: loop_all_index")
	time_it(loop_all_index)
end

I had no idea lua was so bad at iterating through tables.

Do keep in mind that you are looping through 1,000,000 elements here, so that is not a realistic worst-case test for the Pokemon app - a more realistic test in this case might be 10,000. So, I would retry with fewer entries in your table, as there could be something inherent with very large numbers in tables that makes it slower.

Another thing to consider is how the games do PCs. The actual games (here I am thinking Sword and Shield) do not have 1,000.000 or 10,000 or even 50 pokemon in the PC - instead, they have 32 boxes each with 30 maximum pokemon. This divides things into buckets, and each bucket is surely loaded independently, so an individual bucket can be very fast. Of course, that's not happening in the app right now, but it could be a direction we could go if we find that having lots of pokemon causes things to chug.

Some other things you should profile include:

• Removing the first item (likely worst case for removal)
• Removing the last item (likely best case for removal)
• EDIT: Removing an item in the middle (which could also be bad)
• Inserting a new item (likely good for both arrays and tables)

And then I suggest trying out a potentially-best-of-both-worlds implementation: a sorted array. We talked about this a few weeks ago, and I think it might be an ideal candidate in this situation (where you want to have fast lookups AND fast iteration).

Here is a standard binary search:
https://github.com/Roblox/Wiki-Lua-Libraries/blob/master/StandardLibraries/BinarySearch.lua
Because the values are strings, the default comparator should be fine!

Did some more tests, had to keep it at 1m to even get some numbers on it. Anything lower and most stuff wouldn't show any thing. So first observation: The table need to have a lot of information in it to actually matter much.

Removing with an index (Pokemon number 123121 or something) was a lot faster in an indexed list but not by much at all. When removing by ID the hash table was a lot quicker, practically instant (showed 0 on the test) while it took a lot of time for the indexed table (24-35). Later test have also shown that that looping over an indexed table can also be slow.

I think we might be optimizing when there is no need either. But for now I will change it to use the "hashed" list.