Last fall I was experimenting in Codea with sets of arbitrary values, and wanted to access the elements sometimes in random order and sometimes in sorted order (especially when debugging). In the process I learned a little about Lua’s native sorting mechanism for tables and also about iterators.
The elements of my sets were defined in a class “Value” that could hold numbers, strings, tables, etc. Each Value has a type field (number, string, etc) and a value field.
One of the functions defined in Value is “lt()”, which implements the less-than relation, that is, it returns “true” when “self < v”. For my Value objects, values of different, incompatible types had to have a well-defined ordering. For example, I arbitrarily decided that a numeric value was always “less than” a string value. Within one type, less-than means the obvious thing.
Sets are stored an ordinary Lua tables, mapping from integers to Values. The indexes run from 1 to N, the number of elements.
With this obvious representation and my less-than function, a set S could be sorted by Lua with this simple call:
table.sort(S, Value:lt)
This sorts the table in place, and I’ve read that Lua uses quicksort, so I expect it to be quite fast. Since only the less-than relation is used for sorting, values that are equal may appear in any order. (But if sets are constrained to contain only unique values, this doesn’t happen.)
To iterate through this sorted table, you can use the obvious method:
for i, e in S do
-- The values “e” appear in ascending order
end
I rewrote this as an iterator for my own purposes, for those cases where I didn’t need the index “i”. It was a bit of a learning experience, but here’s what I came up with:
function setpairs(ss) -- iterator, ordered
local v = ss
local i = 0
return function()
i = i + 1
return v[i]
end
end
-- used in a loop like this:
for e in setpairs(self) do
-- The values “e” also appear in non-descending order
end
If you have never seen iterators, they are very powerful, but I’m not going to try to describe them here. Look it up! I will just say that each time the iterator function ‘setpairs’ is called internally by Lua, it returns the “next” value in the table.
I used the name ‘setpairs’ because it reminds me of ipairs, but it doesn’t return a pair, so “setpairs” is something of a misnomer.
I also wanted to be able to access the elements of a set in random order, without repeating any, and wrote another iterator to do this:
function setpairsR(ss) -- iterator that returns all elements in a random order
local v = {}
local i = #ss + 1
local j = 0
for e,f in pairs(ss) do
j = j + 1
v[j] = f
end
local function iter()
i = i - 1
if i > 0 then
j = math.random(i)
v[i], v[j] = v[j], v[i]
return v[i]
else
return nil
end
end
return iter
end
-- used like this:
for e in setpairsR(S) do
-- The values “e” appear in random order
end
The trick here is to build an internal table with the integers from 1 to N, and then use the Fisher–Yates shuffle algorithm to pick them off in random order. (The reason it makes a copy of the table in the variable v is that you don’t want to be changing the original table. It also allows the iterator to work with unsorted tables, I believe.)
Note that once the set is sorted, these two iterators give both ordered and random access to the whole set in O(n) time. The sorting is done in O(n log n) time so they whole business is about as fast as you could hope for.
By the way, I rather thought the Fisher-Yates algorithm would be new to the Codea community. But no, it has already been mentioned by @Andrew_Stacy.
I’m curious what others think of this, and especially if there are improvements or better methods that anyone can think of.