Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Associatively sorting a table by value in Lua

Tags:

I have a key => value table I'd like to sort in Lua. The keys are all integers, but aren't consecutive (and have meaning). Lua's only sort function appears to be table.sort, which treats tables as simple arrays, discarding the original keys and their association with particular items. Instead, I'd essentially like to be able to use PHP's asort() function.

What I have:

items = {     [1004] = "foo",     [1234] = "bar",     [3188] = "baz",     [7007] = "quux", } 

What I want after the sort operation:

items = {     [1234] = "bar",     [3188] = "baz",     [1004] = "foo",     [7007] = "quux", } 

Any ideas?

Edit: Based on answers, I'm going to assume that it's simply an odd quirk of the particular embedded Lua interpreter I'm working with, but in all of my tests, pairs() always returns table items in the order in which they were added to the table. (i.e. the two above declarations would iterate differently).

Unfortunately, because that isn't normal behavior, it looks like I can't get what I need; Lua doesn't have the necessary tools built-in (of course) and the embedded environment is too limited for me to work around it.

Still, thanks for your help, all!

like image 464
Ben Blank Avatar asked Jan 10 '10 20:01

Ben Blank


People also ask

Is Lua table sort stable?

"[Table. sort] algorithm is not stable; that is, elements considered equal by the given order may have their relative positions changed by the sort." Any ideas when Table.

What sorting algorithm does Lua use?

The table library provides an in-place sort function, based on the quicksort algorithm [wikipedia].

Are Lua tables hash tables?

We all know that a Lua table is a hash table, which uses a hash function to map a key into one of the table's slots. However, the result of the hash function is not unique. There exist some keys that have the same hash value, i.e., it may map some different keys into the same slot.

How are Lua tables stored in memory?

Instead, Lua programmers use regular tables with integer indices to implement arrays. Lua 5.0 uses a new algorithm that detects whether tables are being used as arrays and automatically stores the values associated to numeric indices in an actual array, instead of adding them to the hash table.


2 Answers

You seem to misunderstand something. What you have here is a associative array. Associative arrays have no explicit order on them, e.g. it's only the internal representation (usually sorted) that orders them.

In short -- in Lua, both of the arrays you posted are the same.

What you would want instead, is such a representation:

items = {     {1004, "foo"},     {1234, "bar"},     {3188, "baz"},     {7007, "quux"}, } 

While you can't get them by index now (they are indexed 1, 2, 3, 4, but you can create another index array), you can sort them using table.sort.

A sorting function would be then:

function compare(a,b)   return a[1] < b[1] end  table.sort(items, compare) 
like image 112
Kornel Kisielewicz Avatar answered Oct 10 '22 15:10

Kornel Kisielewicz


As Komel said, you're dealing with associative arrays, which have no guaranteed ordering.

If you want key ordering based on its associated value while also preserving associative array functionality, you can do something like this:

function getKeysSortedByValue(tbl, sortFunction)   local keys = {}   for key in pairs(tbl) do     table.insert(keys, key)   end    table.sort(keys, function(a, b)     return sortFunction(tbl[a], tbl[b])   end)    return keys end  items = {     [1004] = "foo",     [1234] = "bar",     [3188] = "baz",     [7007] = "quux", }  local sortedKeys = getKeysSortedByValue(items, function(a, b) return a < b end) 

sortedKeys is {1234,3188,1004,7007}, and you can access your data like so:

for _, key in ipairs(sortedKeys) do   print(key, items[key]) end 

result:

1234     bar      3188     baz      1004     foo      7007     quux     
like image 32
Karl Avatar answered Oct 10 '22 17:10

Karl