About the structure of the Sorted function, how does it work?

Question

The instruction below is done as many times as the vector size sub. What is the result of this instruction?

sorted(sub, key = lambda x : size(x) )

Where x are the values from 0 to 31 inclusive and sub is a matrix of this genus

sub = [0,1,2,3, (...), 30, 31]

and size is this function:

def size(int_type):
   length = 0
   count = 0
   while (int_type):
       count += (int_type & 1)
       length += 1
       int_type >>= 1
   return count

Answer 1

Usually the function sorted will sort using the list values themselves, comparing them. For example, sorted([-2, 1, 0]) return the list [-2, 0, 1].

The parameter key is responsible for changing the property that will be taken into account when making the ordination. Instead of using the elements themselves, the sort will be done based on the result of the function defined in key.

If in the original list it would be -2 < 0 < 1, when defining key=func the list that will be ordered will be [func(-2), func(1), func(0)], however, without changing the initial values of the list.

Imagine that func calculates the square of the number:

func = lambda x: x**2

lista = [-2, 1, 0]

print(sorted(lista, key=func))

The return will be the list [0, 1, -2], because when considering the squares of the numbers, 0² < 1² < (-2)².

In your case, the list sub will be ordered according to the results of the function size.

Answer 2

This calling the function sorted() classifying the elements of the list sub that you know what it is. What you probably don’t know is the argument calling key.

If you don’t know this, I say it’s a named argument, which is different from the arguments we normally use which is identified by the position it is used, so it would be the first argument played in the variable of the first parameter of the called function, and the second goes to the second parameter and so on. It doesn’t matter what position you’re in, you say his name, but the great advantage is that it documents better what you’re doing, in which case it’s indicating how the classification key should be composed.

Here comes the other thing you may not know is that the lambda. It is a way to define a very simple algorithm, more or less like you do in a function, but it will not run as normally occurs with normal functions. You are passing the algorithm as argument, who will run this algorithm is the internal part of the function sorted(). Then there the classification will occur according to the function result size(), on each element of the list sub there will be an interaction and during the classification the element of that interaction will be passed as an argument to the lambda, therefore this value will be received in x and this will be used as argument in function size().

As far as I understand the function size() takes how many connected bits are in the number passed, until you find the first 0. The algorithm has a unused variable, something tells me it doesn’t do what you expect it to do.

To lambda is a way for you to delay the execution of an algorithm that needs to be defined at that time.

If you want to understand more about lambda, can read another answer in another language, but the concept is the same, and has links there for other answers that help understand. I did not want to go into the details of the inner workings of a lambda, but in essence it is a nameless function of only one line (it cannot have a complex algorithm) and a reference to this code is that it is passed as argument to then run where it needs at the right time.

You can see how it is used internally (this is a function of Sort well simplified just to illustrate the use of lambda):

def sorting(list, key):
    for i in range(len(list)):
        for j in range(i, len(list)):
            if key(list[i]) > key(list[j]):  #a lambda sendo chamada aqui
                list[i], list[j] = list[j], list[i]
def size(int_type):
   length = 0
   count = 0
   while (int_type):
       count += (int_type & 1)
       length += 1
       int_type >>= 1
   return count
arr = [5,4,3,1,6,8,10,9]
sorting(arr, lambda x : size(x))
print(arr)

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.