Sortperm

Users
1

I know that there is a sort module with the ability to sort arrays/lists. Is there a “sortperm” function (to use the Julia term for it), that rather than sorting the array returns the resulting permutation instead?

Thanks.

–shiv–

2

Hi @00shiv —

I believe that Arkouda has a feature like this in its argsort() routine (take a look and see if it matches what you're looking for): Sorting - arkouda documentation But I'm not aware offhand of whether Chapel's libraries do at present. I'm not seeing that feature in the Sort module's documentation, but let me check with a few people to see whether it exists as an undocumented feature.

(If we don't, since Arkouda's sorts are written in Chapel, note that they could likely be extracted and used from a native Chapel program without buying into Arkouda as a whole).

-Brad

3

Chapel has no builtin argSort or sortperm, but you can write one yourself pretty easily

proc argSort(arr) {
  use Sort;
  record CMP: relativeComparator {
    proc compare(a, b) {
      if arr[a] < arr[b] then return -1;
      else if arr[b] < arr[a] then return 1;
      else return 0;
    }
  }
  return sorted(arr.domain.these(), comparator=new CMP());
}

This should work for most arrays, as long as the data type has a < operator defined

-Jade

1 Like
4

Hi @00shiv,

A colleague actually pointed out to me that if you first create an array of tuples and then sort that, you will get much better sort performance

proc argSort(arr: [?d]) {
  use Sort;
  var arrIdx: [d] (arr.eltType, int) = [(a, i) in zip(arr, d)] (a, i);
  sort(arrIdx);
  var idx: [d] int = [ai in arrIdx] ai(1);
  return idx;
}

This should work for primitive types, you may need to write a custom comparator and implement a key or keyPart method for more complex types like a record.

-Jade

1 Like
5

This was going to be my fallback, but it does use more temporary memory than needed, and I was hoping for a more efficient implementation.

Thanks @bradcray @jabraham for all the replies. Appreciate it.

–shiv–

6

Between the two solutions I gave, there is a tradeoff between space complexity and time complexity.

The version with the temp array of tuples will take more memory, but will likely sort faster (no indirection in the sort, able to use radix sort). The version with proc compare will use less temporary memory and make less copies, at the cost of longer sort times.

I'll also add that sorted(arr.domain.these(), ...) may not be very performant or work in a distributed case (if arr is distributed, the result won't be). You could fix that with something like this

var idx: [arr.domain] int = arr.domain;
sort(idx, ...);
return idx;

-Jade

7

@jabraham

But the sorted(arr.domain.these(), …) will work with multi-dimensional arrays, whereas the other one won’t, I think?

–shiv–

8

That is true, sorted(arr.domain.these(), …) will work with multi-dimensional arrays and give you a 1D array of indices.

But if arr is a distributed multi-dimensional array, sorted(arr.domain.these(), …) won't work. In that case you will need to have a way of maintaining the distribution while still creating a 1D array.

-Jade

9

@00shiv — Could you tell us about what you would want to happen when sorting or argsort/sortperm-ing a multidimensional array? Is it just a sort of the array's elements with no regards to the multidimensional structure, or something more than that?

(note that the following issue wrestled with this question a bit and didn't come up with any solid interpretations of multidimensional sorts: How should `proc sort` handle non-1D/non-rectangular arrays · Issue #25171 · chapel-lang/chapel · GitHub )

Thanks!
-Brad

10

@brad Thanks for pointing me to the earlier issue as I now see that sorted could be another option to argSort.

As for my use case, it is pretty complex, so rather than try explain it, I believe that an argSort of a multidimensional array that returns a 1D array of valid indices back into the original array would suffice.

So if arr : [1..N1, 1..N2, 1..N3] real yields order = argSort(arr), then arr[order[1]] must be a valid access and it must be the smallest number in arr.

However I do not see how sort by itself would be useful to me.

Thanks,

–shiv–

11

Hi @00shiv —

I'm just realizing that I never got back to you here after your last response. To make sure I'm understanding: Is it accurate to say that, as far as the sorting itself goes, the 3D nature of the array is inconsequential (apart from forming the 3D indices of the array elements)? Put another way, the goal is to sort the values in the array as though they were all values in a 1D array or a list or whatever, but then to have the names/indices of the elements returned by the argsort be their 3D coordinates?

And in your case, are the 3D arrays distributed, or local?

Finally, since some time has passed, I wanted to see whether this question was blocking you or whether Jade's previous answers gave you something to work with?

Thanks,
-Brad

12

I have inlined my answers.

Someone mentioned you in a post.
bradcray https://chapel.discourse.group/u/bradcray Core Chapel Developer
February 10

Hi @00shiv https://chapel.discourse.group/u/00shiv —

00shiv:

I believe that an argSort of a multidimensional array that returns a 1D
array of valid indices back into the original array would suffice.

I'm just realizing that I never got back to you here after your last
response. To make sure I'm understanding: Is it accurate to say that, as
far as the sorting itself goes, the 3D nature of the array is
inconsequential (apart from forming the 3D indices of the array elements)?
Put another way, the goal is to sort the values in the array as though they
were all values in a 1D array or a list or whatever, but then to have the
names/indices of the elements returned by the argsort be their 3D
coordinates?

Yes, this would be sufficient for me.

And in your case, are the 3D arrays distributed, or local?

They are all local.

Finally, since some time has passed, I wanted to see whether this question
was blocking you or whether Jade's previous answers gave you something to
work with?

Yes, Jade's answer was enough for me to get going.

Thanks for following up.
--shiv--

1 Like
13

@00shiv —

Thanks for the quick response and confirmation.

Would you be willing to open a feature request issue on our repository for a sortperm/argsort equivalent? Issue 18091 arguably already covers this, but I think that the routine belongs in the Sort module rather than the LinearAlgebra module, and also that issues are more likely to be completed if they are focused and bite-sized, whereas 18091 has a number of aspects to it, and has also been around for awhile.

If not, I'll work on capturing your request in an issue myself.

-Brad

14

I have been trying to create a feature request all morning, but I just keep
getting a spinning cursor. Will try again later!
--shiv--

15

@00shiv : Did you ever get a chance to try this again? The spinning cursor behavior isn't familiar to me (though I know GitHub had some service issues in the past week or two).

-Brad

16

Just tried again and succeeded!
Hope it is sufficiently descriptive?
Thanks.
--shiv--