CODEWITHSUNDEEP
python
matsuo_basho
matsuo_basho

Reputation: 3030

Pythonic way of getting hierarchy of elements in numeric list

I have a numeric list a and I want to output a list with the hierarchical position of every element in a (0 for the highest value, 1 for the second-highest, etc).

I want to know if this is the most Pythonic and efficient way to do this. Perhaps there is a better way?

a = [3,5,6,25,-3,100]
b = sorted(a)
b = b[::-1]
[b.index(i) for i in a]

Upvotes: 1

Views: 352

Answers (4)

Sunitha
Sunitha

Reputation: 12015

First, zip the list with a with range(len(a)) to create a list of tuples (of element and their positions), sort this list in reverse order, zip this with range(len(a)) to mark the positions of each element after the sort, now unsort this list (by sorting this based on the original position of each element), and finally grab the position of each element when it was sorted

>>> a = [3,5,6,25,-3,100]
>>> [i for _,i in sorted(zip(sorted(zip(a, range(len(a))), reverse=True), range(len(a))), key=lambda t:t[0][1])]
[4, 3, 2, 1, 5, 0]

Upvotes: 0

blhsing
blhsing

Reputation: 106881

@ThierryLathuille's answer works only if there are no duplicates in the input list since the answer relies on a dict with the list values as keys. If there can be duplicates in the list, you should sort the items in the input list with their indices generated by enumerate, and map those indices to their sorted positions instead:

from operator import itemgetter
mapping = dict(zip(map(itemgetter(0), sorted(enumerate(a), key=itemgetter(1), reverse=True)), range(len(a))))

mapping becomes:

{5: 0, 3: 1, 2: 2, 1: 3, 0: 4, 4: 5}

so that you can then iterate an index over the length of the list to obtain the sorted positions in order:

[mapping[i] for i in range(len(a))]

which returns:

[4, 3, 2, 1, 5, 0]

Upvotes: 1

Thierry Lathuille
Thierry Lathuille

Reputation: 24272

One problem with your solution is the repeated use of index, that will make your final comprehension O(n**2), as index has to go over the sorted list each time.

It would be more efficient to build a dict with the rank of each value in the sorted list:

a = [3,5,6,25,-3,100]

ranks = {val:idx for idx, val in enumerate(sorted(a, reverse=True))}
# {100: 0, 25: 1, 6: 2, 5: 3, 3: 4, -3: 5}
out = [ranks[val] for val in a]

print(out)
# [4, 3, 2, 1, 5, 0]

in order to have a final step in O(n).

Upvotes: 1

blue note
blue note

Reputation: 29089

You could also you numpy.argsort(-a) (-a because argsort assumes ascending order). It could have better performance for large arrays (though there's no official analysis that I know of).

Upvotes: 1

Related Questions