Is it possible to sort a table in pico8?
I think that tables aren't (necessarily) ordered in Lua (not sure about pico8), but I need to do some rudimentary depth sorting...
Solutions or workarounds gratefully received!
I'm not a Lua expert so there may be a better way, but when I was faced with this problem, I ended up creating a (doubly) linked list with ordered insertion. I then held onto this list from frame to frame. When something moved, I deleted it from the list and reinserted. This worked in my case because things weren't moving often, but I needed to traverse them in order on every frame.
there's no function exposed to sort a table in pico8, but you can write your own.
@eruonna a linked list would work, but I would need to adjust per frame, which I fear would not be very performance friendly.
@impbox - I don't see how I could write a sort function without splice, or even unshift functionality - can you elaborate?
Most Lua examples use pairs for table manipulation, but pairs doesn't seem to be in pico8
here's an implementation of an Insertion Sort
function sort(a) for i=1,#a do local j = i while j > 1 and a[j-1] > a[j] do a[j],a[j-1] = a[j-1],a[j] j = j - 1 end end end |
not the most efficient sort, but should be fine for smallish lists.
you could make it take a callback to do the comparison if you want to sort based on some other logic.
@impbox - Thanks that worked! (And apologies, I realised after the fact I could have googled just a little bit harder!)
Bumping an old thread, but I thought I'd suggest some alternative sorting algorithms. I've been using some sorts to help with render sorting (by depth, y axis, and creation order) on a game I'm working on.
I found this heapsort implementation which appears to be part of an archived set of benchmarks for Lua 5.1 described here (PDF). It is MIT licensed.
I adapted that code to have slightly-more-descriptive variable names, some pico8 shorthands, and made it take a comparator.
function heapsort(t, cmp)
local n = #t
local i, j, temp
local lower = flr(n / 2) + 1
local upper = n
while 1 do
if lower > 1 then
lower -= 1
temp = t[lower]
else
temp = t[upper]
t[upper] = t[1]
upper -= 1
if upper == 1 then
t[1] = temp
return
end
end
i = lower
j = lower * 2
while j <= upper do
if j < upper and cmp(t[j], t[j+1]) < 0 then
j += 1
end
if cmp(temp, t[j]) < 0 then
t[i] = t[j]
i = j
j += i
else
j = upper + 1
end
end
t[i] = temp
end
end
|
According to pico8 0.1.4 it's 170 tokens. It's still early testing, but I found this had fairly low CPU usage, heapsort is O(n log n) and low memory usage. The codesize kind of probably can't be reduced much, but for a huge improvement in sorting performance, it might be worth a shot!
And here's a much-smaller quick-sort algorithm I tried, but I think the recursion and O(n^2) worst case kind of kills it. It may just be because of the choice of pivot, but I dunno.
function qsort(t, cmp, i, j)
i = i or 1
j = j or #t
if i < j then
local p = i
for k = i, j - 1 do
if cmp(t[k], t[j]) <= 0 then
t[p], t[k] = t[k], t[p]
p = p + 1
end
end
t[p], t[j] = t[j], t[p]
qsort(t, cmp, i, p - 1)
qsort(t, cmp, p + 1, j)
end
end
|
That one is 108 tokens.
I was able to beat the performance of the earlier heap sort Overkill listed by 1.5x-3x. Here's the result, I made a full cart for profiling and debugging sorting on my github (https://github.com/morgan3d/misc/tree/master/p8sort).
My fast implementation is a PICO-8 optimized version of the heap sort from The Graphics Codex (http://graphicscodex.com), which has a more-commented version explaining the two steps. The siftdown helper function is inlined, making it a little more confusing but giving a 25% additional boost.
function ce_heap_sort(data)
local n = #data
-- form a max heap
for i = flr(n / 2) + 1, 1, -1 do
-- m is the index of the max child
local parent, value, m = i, data[i], i + i
local key = value.key
while m <= n do
-- find the max child
if ((m < n) and (data[m + 1].key > data[m].key)) m += 1
local mval = data[m]
if (key > mval.key) break
data[parent] = mval
parent = m
m += m
end
data[parent] = value
end
-- read out the values,
-- restoring the heap property
-- after each step
for i = n, 2, -1 do
-- swap root with last
local value = data[i]
data[i], data[1] = data[1], value
-- restore the heap
local parent, terminate, m = 1, i - 1, 2
local key = value.key
while m <= terminate do
local mval = data[m]
local mkey = mval.key
if (m < terminate) and (data[m + 1].key > mkey) then
m += 1
mval = data[m]
mkey = mval.key
end
if (key > mkey) break
data[parent] = mval
parent = m
m += m
end
data[parent] = value
end
end
|
Thanks for the post folks. Trying to get my table sorted for depth sorting on the y as well, however all of these options give me an error when plugging in my table. "attempt to compare two nil values".
I'm no expert programmer and have just started into lua, so I'm not sure what I'm doing wrong? Any help would be appreciated
For the latter option there it's specifically "if ((m < n) and (data[m + 1].key > data[m].key += 1" that's pushing the error
Did you look ar the sample code provided in the above github?
Each data element you sort needs a ‘key’ attribute...
I posted a 3-way quicksort earlier, but I forgot someone invented the dual-pivot quicksort, which is better, so I deleted it. Here's an implementation of the dual-pivot version:
-- common comparators function ascending(a,b) return a<b end function descending(a,b) return a>b end -- a: array to be sorted in-place -- c: comparator (optional, defaults to ascending) -- l: first index to be sorted (optional, defaults to 1) -- r: last index to be sorted (optional, defaults to #a) function qsort(a,c,l,r) c,l,r=c or ascending,l or 1,r or #a if l<r then if c(a[r],a[l]) then a[l],a[r]=a[r],a[l] end local lp,rp,k,p,q=l+1,r-1,l+1,a[l],a[r] while k<=rp do if c(a[k],p) then a[k],a[lp]=a[lp],a[k] lp+=1 elseif not c(a[k],q) then while c(q,a[rp]) and k<rp do rp-=1 end a[k],a[rp]=a[rp],a[k] rp-=1 if c(a[k],p) then a[k],a[lp]=a[lp],a[k] lp+=1 end end k+=1 end lp-=1 rp+=1 a[l],a[lp]=a[lp],a[l] a[r],a[rp]=a[rp],a[r] qsort(a,c,l,lp-1 ) qsort(a,c, lp+1,rp-1 ) qsort(a,c, rp+1,r) end end |
Some examples:
-- sort on value, ascending
qsort(values)
or
qsort(values, ascending)
-- sort on value, descending
qsort(values, descending)
-- sort on depth, ascending
qsort(objects, function(a,b) return a.z<b.z end)
-- sort on depth, descending
qsort(objects, function(a,b) return a.z>b.z end)
-- sort on name, ascending
function bylastfirst(a,b)
return a.lastname<b.lastname
or a.lastname==b.lastname and a.firstname<b.firstname
end
qsort(users, bylastfirst)
qsort(admins, bylastfirst)
|
It's based on the implementation here, if you want comments. ;)
https://www.geeksforgeeks.org/dual-pivot-quicksort/
The dual-pivot quicksort is considered the best general-purpose sort, and is now the default algorithm for the C/C++ standard library. There are some pathological cases (e.g. nearly-sorted-but-in-reverse can be bad because it causes bad pivot choices), and if you were to know you had one consistently, you might want another sort, but 99% of common use cases work very well with it.
Edit: updated to use comparators, since they turned out to be pretty cheap.
As an aside, if you need to do depth sorting of triangles for a 3D scene, you may find you're much better off using a bucket sort where the buckets are similar in size to typical polygons.
Bucket sorts work well with a scene that's tessellated to a reasonable level, but not so well with a scene where large and small polys are mixed. The latter is difficult to sort at all, usually calling for BSP trees. Most PSX games (where there was no Z buffer) used one and/or the other of the two. People doing 3D on PICO-8 would probably do well to look at how things were done on PSX.
Still a bit over my head I guess. I'll try and figure it out. But how would I plug in my table of "actors" and sort them based on their y value.
I have a table that I'm adding and removing objects to and from when they're created and destroyed. I just want to sort them to simulate depth.
What would I then put in as the variables in dpquicksort(actors,?,?).
Sorry, just never done much coding before. Even understanding what pivot means in this regards is going to take some a bit more of me struggling through it to understand.
It's not the nicest way to do it, but you could just modify the insertion sort posted by impbox.
function sortByY(a)
for i=1,#a do
local j = i
while j > 1 and a[j-1].y > a[j].y do
a[j].y,a[j-1].y = a[j-1].y,a[j].y
j = j - 1
end
end
end
|
All I did was add .y to the end of any access to the array. This means you should be able to pass a table of actors in (or table of anything with a y property), and it should return with the lowest actor at the end of the table.
I can't test this now (at work), so let me know if it doesn't work!
Extra for experts: a more flexible way to do this would be to have a sort() that takes a "comparator" function. A comparator just decides if one thing is greater or less than another thing. This means you could sort any table in any way you like, without modifying the sort function. This would probably come at a speed cost tho. :/
Ah, thanks aaaidan. It was close , but it was actually sorting the y values. My coder friend just tweaked it a little and it worked. Here's the working version.
function sortByY(a)
for i=1,#a do
local j = i
while j > 1 and a[j-1].y > a[j].y do
a[j],a[j-1] = a[j-1],a[j]
j = j - 1
end
end
end
|
Ah, of course! what a silly oversight. Glad you got it ... sorted. (b'dumm tish)
In any case, here's that "comparator" based sort I mentioned.
function sort(a,cmp)
for i=1,#a do
local j = i
while j > 1 and cmp(a[j-1],a[j]) do
a[j],a[j-1] = a[j-1],a[j]
j = j - 1
end
end
end
|
This function is exactly the same as the (correct) one you posted, but in addition to a list, you also pass it a
comparator function it will use to decide whether one element is "greater than" another. Because it's a function you can use any logic you can think of.
In this particular comparator sort, the comparator is expected to return true if its first argument (a) is greater than the second (b). So to sort based on x (ascending), you could say:
sort(actors, function(a, b) return a.x > b.x end) |
You can change the > to a < to sort descending. And, of course, you can change the .xs to .y, or .health, or any other property on the objects in your list.
It's perhaps a little strange to see function declarations just stuffed into a function call like that, but it's quite common in other languages, like JavaScript. These functions are often called anonymous functions, because they don't need to be given a name (or assigned to a variable) to be useful.
This approach really starts to make sense when you want to sort a list by a more complicated idea, such as the distance to a particular point. Say you'd like to sort the actors on how far away they are from the player.
-- get the distance between two actors (incl. player) function distance(a,b) local dx = abs(a.x - b.x) local dy = abs(a.y - b.y) return sqrt(dx^2 + dy^2) end sort(actors, function(a,b) return distance(player, a) > distance(player,b) end) |
There's also no reason you have to use an anonymous function for the comparator. If you're using the same type of sort in lots of places, you could just pass it a regular old named function.
-- sorting by x again function byX(a,b) return a.x > b.x end sort(actors, byX) |
One downside to this approach is that it's probably a lot slower than sorting with a hard-coded sort like sortByY(). But that's a bit like saying a whippet is a lot slower than a cheetah: it's still "really fast". I wouldn't let this put you off if you can see it being useful, because you're unlikely to run into performance problems unless you're doing some really heavy computation. In the event you do, there are lots of ways to respond, including switching to a more efficient sorting algorithm (which is probably the first port of call), rather than dropping the comparator.
Anyway, this post got a bit epic, but hope it helps, or is at least interesting. Happy to chat if you got questions.
I haven't given the issue of the token limit much thought, but it seems to me that it's possible this could save quite a few tokens on a big project, because so much code is reused. Let me know anyone, if you have thoughts to the contrary.
Here's a demo of this sort code.
| aaaiden said:
One downside to this approach is that it's probably a lot slower than sorting with a hard-coded sort |
It's actually not that bad a difference to use a comparator instead of an inline comparison. I ran the two through my benchmark and this is how they came out:
cyc code --- ------------------------ 10 cmp(a[j-1],a[j]) (with cmp() being a local pointing to byX()) 6 a[j-1].x<a[j].x |
There's a lot of other overhead in that while loop and the outer loop around it, so 4 cycles more is a relatively-negligible cost, really.
The reason why it's still quite cheap even with the function overhead is that usual added cost of setting up arguments to a function is negated by the ability of the array-access operations to write directly into the function arguments.
Given that comparators have turned out to be pretty inexpensive, I updated my dual-pivot quicksort above to use them. See here:
https://www.lexaloffle.com/bbs/?pid=50434#p50434
Thus, to sort actors on ascending x values, @denmanrooke could do this with it:
qsort(actors, function(a,b) return a.x < b.x end) |
(That's assuming order is meant to be ascending. For descending, use a.x > b.x.)
I wanted something smallish and reusable so I implemented a shellsort that assumes every element is a table and uses "cmp_idx" as the sort key. Haven't benchmarked it.
shell_gaps = {701, 301, 132, 57, 23, 10, 4, 1} -- ciura's sequence
function shellsort(a,cmp_idx)
for gap in all(shell_gaps) do
if gap <= #a then
for i = gap, #a do
local t = a[i]
local j = i
while j > gap and a[j - gap][cmp_idx] > t[cmp_idx] do
a[j] = a[j - gap]
j -= gap
end
a[j] = t
end
end
end
end
|
Q: What is shellsort good at?
A: Basically, souped up insertion sort. Only slightly more complex, does very well with mostly sorted data.
[Please log in to post a comment]
