lhs and rhs in table.sort

classic Classic list List threaded Threaded
20 messages Options
Reply | Threaded
Open this post in threaded view
|

lhs and rhs in table.sort

iain morland
Greetings all,

I am researching the different compare functions that are available for use with the table.sort function.

After some searching online, I was able to use the following as the second argument in table.sort:

function(lhs,rhs) return myTable[lhs] < myTable[rhs] end

In turn, I used this to sort another table of the same size like so:

table.sort(otherTable,function(lhs,rhs) return myTable[lhs] < myTable[rhs] end)

However I couldn’t find reference to the use of "lhs" or “rhs" in the Lua documentation, and feel frustrated that I don’t fully understand what’s happening in the above code.

So I have two questions:

1. Could anyone explain (or direct me to an explanation of) the different compare functions that can be used with table.sort?

2. Are there any documented examples of how these functions work when sorting one table by the result of sorting another table?

Thanks in advance
iain
Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Oliver Kroth
Hi,

table.sort is described in chapter 20.2 of Programming in Lua. The
optional function argument is being called with two elements of the
table to be sorted and has to return true if the first of its arguments
shall come first in the sorted table.

Note that the function is actually only defined for an array, which is a
table with subsequent numbers as indices.

--
Oliver

Am 24.08.2015 um 16:54 schrieb iain morland:

> Greetings all,
>
> I am researching the different compare functions that are available for use with the table.sort function.
>
> After some searching online, I was able to use the following as the second argument in table.sort:
>
> function(lhs,rhs) return myTable[lhs] < myTable[rhs] end
>
> In turn, I used this to sort another table of the same size like so:
>
> table.sort(otherTable,function(lhs,rhs) return myTable[lhs] < myTable[rhs] end)
>
> However I couldn’t find reference to the use of "lhs" or “rhs" in the Lua documentation, and feel frustrated that I don’t fully understand what’s happening in the above code.
>
> So I have two questions:
>
> 1. Could anyone explain (or direct me to an explanation of) the different compare functions that can be used with table.sort?
>
> 2. Are there any documented examples of how these functions work when sorting one table by the result of sorting another table?
>
> Thanks in advance
> iain


Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

iain morland
In reply to this post by iain morland
Thank you Oliver; you are quite right about the function requiring an array.

I read the description of table.sort in PiL but am still unsure over “lhs" and “rhs". I couldn’t see those mentioned anywhere (in the whole book - unless Robert can please correct me!). How would a person know to use myArray[lhs] < myArray[rhs] in the first place? Are there other terms that might be used in place of “lhs” and “rhs” to do other things with the array? I feel that I am missing a crucial piece of understanding about this.

Regards
iain


>
> Hi,
>
> table.sort is described in chapter 20.2 of Programming in Lua. The
> optional function argument is being called with two elements of the
> table to be sorted and has to return true if the first of its arguments
> shall come first in the sorted table.
>
> Note that the function is actually only defined for an array, which is a
> table with subsequent numbers as indices.
>
> --
> Oliver
>
> Am 24.08.2015 um 16:54 schrieb iain morland:
>> Greetings all,
>>
>> I am researching the different compare functions that are available for use with the table.sort function.
>>
>> After some searching online, I was able to use the following as the second argument in table.sort:
>>
>> function(lhs,rhs) return myTable[lhs] < myTable[rhs] end
>>
>> In turn, I used this to sort another table of the same size like so:
>>
>> table.sort(otherTable,function(lhs,rhs) return myTable[lhs] < myTable[rhs] end)
>>
>> However I couldn’t find reference to the use of "lhs" or “rhs" in the Lua documentation, and feel frustrated that I don’t fully understand what’s happening in the above code.
>>
>> So I have two questions:
>>
>> 1. Could anyone explain (or direct me to an explanation of) the different compare functions that can be used with table.sort?
>>
>> 2. Are there any documented examples of how these functions work when sorting one table by the result of sorting another table?
>>
>> Thanks in advance
>> iain
>


Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Jonathan Goble
On Mon, Aug 24, 2015 at 5:00 PM, iain morland <[hidden email]> wrote:
> I read the description of table.sort in PiL but am still unsure over “lhs" and “rhs". I couldn’t see those mentioned anywhere (in the whole book - unless Robert can please correct me!). How would a person know to use myArray[lhs] < myArray[rhs] in the first place? Are there other terms that might be used in place of “lhs” and “rhs” to do other things with the array? I feel that I am missing a crucial piece of understanding about this.

That's purely an example function, with "lhs" and "rhs" used as
example parameter names. You can write any function you want which can
be as complex as you want. The only requirement is that the function
takes two parameters, each an element in the array, and returns true
if the first argument should come before the second argument in the
finished sort. Here's another example I used in a personal script to
sort a sports league standings table:

    table.sort( list, function( n1, n2 )
        local a = n1.confWins + n1.confLosses > 0 and n1.confWins /
(n1.confWins + n1.confLosses) or 0.01
        local b = n2.confWins + n2.confLosses > 0 and n2.confWins /
(n2.confWins + n2.confLosses) or 0.01
        if n1.wins + n1.losses > 0 and n2.wins + n2.losses > 0 and
n1.wins / (n1.wins + n1.losses) ~= n2.wins / (n2.wins + n2.losses)
then
            return n1.wins / (n1.wins + n1.losses) > n2.wins /
(n2.wins + n2.losses)
        elseif a ~= b then
            return a > b
        elseif n1.h2hWins ~= n2.h2hWins then
            return n1.h2hWins > n2.h2hWins
        elseif n1.pointDiff ~= n2.pointDiff then
            return n1.pointDiff > n2.pointDiff
        elseif n1.pointsAllowed ~= n2.pointsAllowed then
            return n1.pointsAllowed < n2.pointsAllowed
        else
            return n1.randomNumber > n2.randomNumber
        end
    end )

Here, "list" is the array I want to sort, and "n1" and "n2" are the
parameter names I arbitrarily chose to represent the arguments. This
particular function sorts the array based on overall win/loss
percentage unless tied, in which case it tries conference win/loss
percentage unless that is also tied. In that case, it goes through
several other tiebreakers until it finds one that isn't tied and sorts
based on that.

So you can write whatever function you want here. The lhs and rhs is
simply an example.

Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Jonathan Goble
On Mon, Aug 24, 2015 at 5:15 PM, Jonathan Goble <[hidden email]> wrote:

>     table.sort( list, function( n1, n2 )
>         local a = n1.confWins + n1.confLosses > 0 and n1.confWins /
> (n1.confWins + n1.confLosses) or 0.01
>         local b = n2.confWins + n2.confLosses > 0 and n2.confWins /
> (n2.confWins + n2.confLosses) or 0.01
>         if n1.wins + n1.losses > 0 and n2.wins + n2.losses > 0 and
> n1.wins / (n1.wins + n1.losses) ~= n2.wins / (n2.wins + n2.losses)
> then
>             return n1.wins / (n1.wins + n1.losses) > n2.wins /
> (n2.wins + n2.losses)
>         elseif a ~= b then
>             return a > b
>         elseif n1.h2hWins ~= n2.h2hWins then
>             return n1.h2hWins > n2.h2hWins
>         elseif n1.pointDiff ~= n2.pointDiff then
>             return n1.pointDiff > n2.pointDiff
>         elseif n1.pointsAllowed ~= n2.pointsAllowed then
>             return n1.pointsAllowed < n2.pointsAllowed
>         else
>             return n1.randomNumber > n2.randomNumber
>         end
>     end )

(Oh, and feel free to laugh at my programming skills here. This
function was written on a deadline during my first week of learning
how to program in something other than BASIC, over two years ago.
Suffice it to say that I've learned a lot since then. :-P )

Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Parke
In reply to this post by iain morland
On Mon, Aug 24, 2015 at 7:54 AM, iain morland <[hidden email]> wrote:
> So I have two questions:
>
> 1. Could anyone explain (or direct me to an explanation of) the different compare functions that can be used with table.sort?

Various sort algorithms use only two operations: compare and swap.
For example, bubble sort, merge sort, quick sort - all these use only
compare and swap.

https://en.wikipedia.org/wiki/Quicksort

Swap is generic (at least on a Lua table), so you do not need to
provide a swap function.

To answer your question:  Any compare function can be used.  It all
depends on what order you want as a result.  In other words, you
specify the order you want by providing the compare function of your
choice.

In your example, the compare function depends not only on the two
elements being compared, but also on the values associated (via
myTable) with those two elements.

-Parke

Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

iain morland
In reply to this post by iain morland
Thank you for the further responses. I now see that rhs/lhs was a red herring!

Unfortunately I still don’t confidently grasp how the function works. Take the example in Roberto’s PiL book:

table.sort(network, function(a,b) return (a.name > b.name) end)

Presumably the function in the second argument returns true or false - right? Either a.name is greater than b.name or not.

But what are a and b? Does table.sort repeatedly call the function using successive pairs of items from the table ‘network’ as arguments a and b?

And if the arguments passed to this function refer to a *different* table from that which is being sorted, where (in memory) is the sorting occurring? The other table doesn’t get sorted in-place, for its order remains the same.

I think the crux of my confusion is that the function in the second argument iterates, but it doesn’t look like an iterator - at least to the less trained reader.

Thanks
Iain
Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Coda Highland
On Wed, Aug 26, 2015 at 1:44 PM, iain morland <[hidden email]> wrote:
> Thank you for the further responses. I now see that rhs/lhs was a red herring!
>
> Unfortunately I still don’t confidently grasp how the function works. Take the example in Roberto’s PiL book:
>
> table.sort(network, function(a,b) return (a.name > b.name) end)
>
> Presumably the function in the second argument returns true or false - right? Either a.name is greater than b.name or not.
>
> But what are a and b? Does table.sort repeatedly call the function using successive pairs of items from the table ‘network’ as arguments a and b?

Pretty much, yeah. I wouldn't describe them as "successive" -- it'll
call it whenever it needs to compare two items no matter where they
are in the input -- but it does get repeatedly called with various
pairs of items as necessary.

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Oliver Kroth
In reply to this post by iain morland
Hi iain,

the thing works like this:

There is a generic sort algorithm that swaps two values if the rhs is
"larger than" the lhs. rhs is right-hand-side, lhs is left-hand-side and
refers to the left and right side of a < operator.

You don't have to know how the sort algorithm works, as long as you
provide it with a function that  gives it a clue when to swap two values
of the array. You define the ordering, the sort function works based on
this.

E.g., you have a database with cars, and you want to sort them based on:
a)    mileage
b)    top speed
c)    age,

you just provide to the generic sort() function a function that compares
the relevant fields in the records and returns the result.
If you are smart, you don't sort the data, but an index on it, and this
not more difficult, as you sort the index, and your comparison function
returns the result of the comparison of the two indexed values (instead
the comparison of the indices.)

More theoretical:
If on your data a comparison "<=" can be defined for which for any three
data a,b,c this is true: if a <=b and b<=c then a<=c, , you can sort them.

More practical:
Sorting is generic, the comparison function is custom specific. You just
call the sort() function and it will ask you (by calling back the
comparison function that you provided) which one of two value shall come
first. When the sort function is finished, it has sorted the array
according to your ordering function.

--
Oliver





Am 26.08.2015 um 22:44 schrieb iain morland:

> Thank you for the further responses. I now see that rhs/lhs was a red herring!
>
> Unfortunately I still don’t confidently grasp how the function works. Take the example in Roberto’s PiL book:
>
> table.sort(network, function(a,b) return (a.name > b.name) end)
>
> Presumably the function in the second argument returns true or false - right? Either a.name is greater than b.name or not.
>
> But what are a and b? Does table.sort repeatedly call the function using successive pairs of items from the table ‘network’ as arguments a and b?
>
> And if the arguments passed to this function refer to a *different* table from that which is being sorted, where (in memory) is the sorting occurring? The other table doesn’t get sorted in-place, for its order remains the same.
>
> I think the crux of my confusion is that the function in the second argument iterates, but it doesn’t look like an iterator - at least to the less trained reader.
>
> Thanks
> Iain


Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Tim Hill
In reply to this post by iain morland

> On Aug 26, 2015, at 1:44 PM, iain morland <[hidden email]> wrote:
>
> Thank you for the further responses. I now see that rhs/lhs was a red herring!
>
> Unfortunately I still don’t confidently grasp how the function works. Take the example in Roberto’s PiL book:
>
> table.sort(network, function(a,b) return (a.name > b.name) end)
>
> Presumably the function in the second argument returns true or false - right? Either a.name is greater than b.name or not.
>
> But what are a and b? Does table.sort repeatedly call the function using successive pairs of items from the table ‘network’ as arguments a and b?
>
> And if the arguments passed to this function refer to a *different* table from that which is being sorted, where (in memory) is the sorting occurring? The other table doesn’t get sorted in-place, for its order remains the same.
>
> I think the crux of my confusion is that the function in the second argument iterates, but it doesn’t look like an iterator - at least to the less trained reader.
>
> Thanks
> Iain

Sorting a table is generic in the sense that the *process* of sorting can be handled by the table.sort() function internally, but the desired *order* of the sort is left up to you, as caller of the table.sort() function. To allow you to specify the desired order of the sort, you supply a “compare” function that defines the sort order. How does this work? As the table.sort() progresses, the sorter needs to be able to compare two arbitrary entries in the list of items being sorted (that is, the array within the table).

When the sorter calls your compare function, it is asking “Here are two of the items in the list you told me to sort .. please tell me which one should come first in the sort?”. The two items to compare are specified by the first and second arguments to the function you supply (you can give them any names you like). You return true if the first item should come before the second, false otherwise. The table.sort() function will call your “compare” function many times during the sort, comparing many different pairs of items as needed until the sort is complete.

For example:

t = { 10, 5, 99, -17 }

— Returns true if a is smaller then b, meaning sort will be smallest to largest
function comp1(a, b)
        print(“Comparing: “, a, b)
        return a < b
end

print(“Starting sort”)
table.sort(t, comp1)
print(“Done!”)


—Tim



Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Dirk Laurie-2
2015-08-26 23:47 GMT+02:00 Tim Hill <[hidden email]>:

> When the sorter calls your compare function, it is asking
> “Here are two of the items in the list you told me to sort ..
> please tell me which one should come first in the sort?”.

You can supply any function you like as long as it satisfies
the basic rules of ordering.

1. "A must come before B" and "B must come before A"
may not both be true (but may both be false).
2. If "A must come before B" and "B must come before C"
are both true, then "C must come before A" may not also
be true.

If you function is capricious, anything can happen.

1. (Best) The sort routine detects it and give an error.
2. (Bad) The sort routine returns the original items in some
meaningless order.
3. (Worst) The sort routine does not return at all. (I have
been told this but never actually encountered it.)

Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Coda Highland
On Wed, Aug 26, 2015 at 11:58 PM, Dirk Laurie <[hidden email]> wrote:

> 2015-08-26 23:47 GMT+02:00 Tim Hill <[hidden email]>:
>
>> When the sorter calls your compare function, it is asking
>> “Here are two of the items in the list you told me to sort ..
>> please tell me which one should come first in the sort?”.
>
> You can supply any function you like as long as it satisfies
> the basic rules of ordering.
>
> 1. "A must come before B" and "B must come before A"
> may not both be true (but may both be false).
> 2. If "A must come before B" and "B must come before C"
> are both true, then "C must come before A" may not also
> be true.
>
> If you function is capricious, anything can happen.
>
> 1. (Best) The sort routine detects it and give an error.
> 2. (Bad) The sort routine returns the original items in some
> meaningless order.
> 3. (Worst) The sort routine does not return at all. (I have
> been told this but never actually encountered it.)
>

3 can't happen with most sorting algorithms. Merge sort has a fixed
running time regardless of the input or the comparator. Selection sort
and insertion sort never move elements after they've been put in their
final sorted position. Quicksort can have really bad performance
characteristics in the face of a bad comparator, but its methodology
protects it from hitting an infinite loop. (I'm not sure about heap
sort.)

Bubble sort, on the other hand, is especially vulnerable to bad
comparators, because it tries to sort the entire array on every pass.
An example of a comparator that would get a bubble sort stuck in an
infinite loop is one that tries to break ties between equal elements
by comparing their positions in the array and always saying the one
with the higher index is the smaller one. (This could, for example, be
a buggy implementation of a stable-sort comparator; for a stable sort,
it should break ties by saying the one with the SMALLER index is the
smaller element.) The bubble sort would swap their positions on every
pass through the loop and therefore never reach its termination
condition.

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Paul K-2
>> 3. (Worst) The sort routine does not return at all. (I have
>> been told this but never actually encountered it.)

> Bubble sort, on the other hand, is especially vulnerable to bad
> comparators, because it tries to sort the entire array on every pass.

I made a "bad" sort comparator once, as described in this thread:
http://lua-users.org/lists/lua-l/2012-06/msg00312.html

The easiest way to trigger "invalid order function for sorting" with
Lua 5.2+ is to run something like this: table.sort({1,2,3,4,5},
function() return true end).

Paul.

On Thu, Aug 27, 2015 at 8:55 AM, Coda Highland <[hidden email]> wrote:

> On Wed, Aug 26, 2015 at 11:58 PM, Dirk Laurie <[hidden email]> wrote:
>> 2015-08-26 23:47 GMT+02:00 Tim Hill <[hidden email]>:
>>
>>> When the sorter calls your compare function, it is asking
>>> “Here are two of the items in the list you told me to sort ..
>>> please tell me which one should come first in the sort?”.
>>
>> You can supply any function you like as long as it satisfies
>> the basic rules of ordering.
>>
>> 1. "A must come before B" and "B must come before A"
>> may not both be true (but may both be false).
>> 2. If "A must come before B" and "B must come before C"
>> are both true, then "C must come before A" may not also
>> be true.
>>
>> If you function is capricious, anything can happen.
>>
>> 1. (Best) The sort routine detects it and give an error.
>> 2. (Bad) The sort routine returns the original items in some
>> meaningless order.
>> 3. (Worst) The sort routine does not return at all. (I have
>> been told this but never actually encountered it.)
>>
>
> 3 can't happen with most sorting algorithms. Merge sort has a fixed
> running time regardless of the input or the comparator. Selection sort
> and insertion sort never move elements after they've been put in their
> final sorted position. Quicksort can have really bad performance
> characteristics in the face of a bad comparator, but its methodology
> protects it from hitting an infinite loop. (I'm not sure about heap
> sort.)
>
> Bubble sort, on the other hand, is especially vulnerable to bad
> comparators, because it tries to sort the entire array on every pass.
> An example of a comparator that would get a bubble sort stuck in an
> infinite loop is one that tries to break ties between equal elements
> by comparing their positions in the array and always saying the one
> with the higher index is the smaller one. (This could, for example, be
> a buggy implementation of a stable-sort comparator; for a stable sort,
> it should break ties by saying the one with the SMALLER index is the
> smaller element.) The bubble sort would swap their positions on every
> pass through the loop and therefore never reach its termination
> condition.
>
> /s/ Adam
>


Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Parke
In reply to this post by Coda Highland
On Thu, Aug 27, 2015 at 8:55 AM, Coda Highland <[hidden email]> wrote:
> Bubble sort, on the other hand, is especially vulnerable to bad
> comparators, because it tries to sort the entire array on every pass.

Bubble sort can be trivially improved to walk over one less element on
each successive pass, guaranteeing termination (unless the compare
function itself never returns).

https://en.wikipedia.org/wiki/Bubblesort#Optimizing_bubble_sort

-Parke

Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Roberto Ierusalimschy
> https://en.wikipedia.org/wiki/Bubblesort#Optimizing_bubble_sort

Optimizing_bubble_sort is an oxymoron :-)

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Sean Conner
It was thus said that the Great Roberto Ierusalimschy once stated:
> > https://en.wikipedia.org/wiki/Bubblesort#Optimizing_bubble_sort
>
> Optimizing_bubble_sort is an oxymoron :-)

  Still faster than Bogo Sort.

  https://en.wikipedia.org/wiki/Bogosort

  -spc


Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Dirk Laurie-2
In reply to this post by Coda Highland
2015-08-27 17:55 GMT+02:00 Coda Highland <[hidden email]>:

> I'm not sure about heap sort.

Heap sort has best case, average case, worst case, all O(n log n),
only the multipliers differ. Auxiliary storage O(1). See Nijenhuis and
Wilf's book, available online [1].

[1] http://www.math.upenn.edu/%7Ewilf/website/CombAlgDownld.html

Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

David Birnhak
In reply to this post by Sean Conner
Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

Coda Highland
In reply to this post by Dirk Laurie-2
On Thu, Aug 27, 2015 at 12:49 PM, Dirk Laurie <[hidden email]> wrote:

> 2015-08-27 17:55 GMT+02:00 Coda Highland <[hidden email]>:
>
>> I'm not sure about heap sort.
>
> Heap sort has best case, average case, worst case, all O(n log n),
> only the multipliers differ. Auxiliary storage O(1). See Nijenhuis and
> Wilf's book, available online [1].
>
> [1] http://www.math.upenn.edu/%7Ewilf/website/CombAlgDownld.html
>

Yes, I know this, but this analysis is based upon having a total
ordering. I'm pretty sure if I tried I could come up with an O(n log
n) worst-case algorithm that would nonetheless fail when given a
misbehaving predicate. Ultimately, this is a security question ("is it
possible to mount a DoS attack against this algorithm given control
over the comparator?"), not an algorithm analysis question.

That said, I did take some more time looking at a heap sort
implementation earlier and I think that a bogus predicate might be
able to trigger some bad performance (depending on the implementation
details) but not break it entirely since there's a fixed O(n)
insertions, and the sifting phase for each insertion is pretty trivial
to prove terminates.

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: lhs and rhs in table.sort

iain morland
In reply to this post by iain morland
Thanks for the further detailed responses on this. I understand it much better now!

Roberto, may I suggest giving a little more detail on this aspect of table.sort() in the next edition of PiL? I believe newcomers would benefit from it.

Regards
Iain