Python Forum
How does the builtin function argpartition works?
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
How does the builtin function argpartition works?
#1
Hi Frnds,

I'm new to numpy.. Can you please explain how the builtin function argpartition works?

>>> x = np.array([3, 4, 2, 1])
>>> x[np.argpartition(x, 3)]
array([2, 1, 3, 4])
>>> x[np.argpartition(x, (1, 3))]
array([1, 2, 3, 4])
>>>
>>> x = [3, 4, 2, 1]
>>> np.array(x)[np.argpartition(x, 3)]
array([2, 1, 3, 4])
I tried to understand the above example, but unfortunately I couldn't..:(
Reply
#2
It's easier to understand it by understanding np.partition first. np.partition(x, 3) takes the 3rd item in sorted order, and puts it in the correct place if the array was sorted. All shorter elements are moved before the 3rd item, and all larger items are moved after the 3rd item, but not necessarily in sorted order.

np.argpartition is like partition, but it gives the indexes of x in the order those items would be in the result of np.partition. So if you look at just np.argpartition(x), it is array([2, 3, 0, 1], dtype=int64). You can match those indexes from your original x to the second x after re-indexing it with argpartition. Note that your first use of argpartition could just be done with the partition method: x.partition(3).

If you give partition/argpartition a sequences of indexes, as in your second example, all of those indexes are put in the correct sorted position and the rest of the items are partitioned.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#3
Thanks for the explanation Craig.. It's really helpful:)

But, When i try to use the sequence for the k parameter, its not sorting the array as expected:

arr = np.array([90, 14, 24, 13, 13, 590, 0, 45, 16, 50])

arr[np.argpartition(arr,(1,5))]
array([  0,  13,  14,  13,  16,  24,  45,  50,  90, 590])
It should be have returned something like
Quote:array([ 0, 13, 13, 14, 16, 24, 45, 50, 90, 590])
right?
Reply
#4
It's a partition, not a sort. It's putting things in groups (partitions) based on the k's you give it, but not necessarily sorting them within those groups. Partition your list with 4 and 7 instead:

>>> arr = np.array([90, 14, 24, 13, 13, 590, 0, 45, 16, 50])
>>> arr.partition((4, 7))
>>> arr
array([ 13,   0,  13,  14,  16,  24,  45,  50, 590,  90])
14 (the 4th item) and 45 (the 7th item) are in the correct sorted positions. Think of them as walls. Everything less than 14 is to the left of the 14 wall. Everything between 14 and 45 is in between the two walls, and everything greater than 45 is to the right of the 45 wall. So the two walls create three partitions. Within the partitions, things are not sorted, they're just thrown in there and land where they will.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#5
Thank you so much Craig..U're awesome!!:)
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020