Log In  

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!

P#14208 2015-09-15 16:18 ( Edited 2018-04-02 05:37)

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.

P#14211 2015-09-15 16:57 ( Edited 2015-09-15 20:57)
:: impbox

there's no function exposed to sort a table in pico8, but you can write your own.

P#14216 2015-09-15 21:00 ( Edited 2015-09-16 01:00)

@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

P#14232 2015-09-16 02:14 ( Edited 2015-09-16 06:14)
:: impbox
1

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.

P#14233 2015-09-16 02:33 ( Edited 2015-09-16 06:33)
:: impbox

you could make it take a callback to do the comparison if you want to sort based on some other logic.

P#14234 2015-09-16 02:36 ( Edited 2015-09-16 06:36)

@impbox - Thanks that worked! (And apologies, I realised after the fact I could have googled just a little bit harder!)

P#14257 2015-09-16 15:43 ( Edited 2015-09-16 19:43)
1

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.

P#18374 2016-01-20 11:53 ( Edited 2016-01-20 17:13)

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
P#40157 2017-05-03 15:20 ( Edited 2017-05-03 19:20)

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

P#50426 2018-03-14 20:25 ( Edited 2018-03-15 00:28)

Did you look ar the sample code provided in the above github?
Each data element you sort needs a ‘key’ attribute...

P#50430 2018-03-15 02:48 ( Edited 2018-03-15 06:48)
:: Felice
1

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.

P#50434 2018-03-15 03:57 ( Edited 2018-03-19 01:11)
:: Felice

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.

P#50439 2018-03-15 08:19 ( Edited 2018-03-15 12:20)

Thanks! I'll look into it tonight, and give these a try.

P#50443 2018-03-15 12:27 ( Edited 2018-03-15 16:27)

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.

P#50453 2018-03-15 18:39 ( Edited 2018-03-15 22:39)

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. :/

P#50455 2018-03-15 18:52 ( Edited 2018-03-15 22:52)

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
P#50456 2018-03-15 19:32 ( Edited 2018-03-15 23:33)

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.

Cart #50554 | 2018-03-18 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

P#50555 2018-03-18 03:59 ( Edited 2018-03-18 08:01)
:: Felice

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.

P#50565 2018-03-18 12:20 ( Edited 2018-03-18 17:54)
:: Felice

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.)

P#50568 2018-03-18 13:52 ( Edited 2018-03-18 17:52)

That's excellent, thanks for doing the analysis @Felice!

I don't feel so gluttonous using them now.

P#50907 2018-03-27 17:25 ( Edited 2018-03-27 21:25)

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.

P#51164 2018-04-02 01:37 ( Edited 2018-04-02 05:42)

[Please log in to post a comment]

Follow Lexaloffle:        
Generated 2020-05-31 11:13 | 0.054s | 4194k | Q:71