topic Re: Efficient sort of numeric arrays in SAS Programming

Efficient sort of numeric arrays

AndersS — Sat, 30 Dec 2023 18:52:35 GMT

Hi! I need to sort rather large arrays in the Data step. All Numeric values, unique. No. of values up to 50 thousand, perhaps more.

Is Quicksort the best?

Where can I find the best SAS code for Quicksort?

What alternatives are there for Quicksort?

I use SAS ODA (OnDemand for Academics). I want to write code that can be published and is very general.

Many thanks in advance!
(I have been googling for a white. Not easy to find the best answer)

/Br AndersS

Re: Efficient sort of numeric arrays

Kurt_Bremser — Sat, 30 Dec 2023 19:35:54 GMT

Fifty thousand variables in a single observation? Really?

Because otherwise an array makes no sense.

Re: Efficient sort of numeric arrays

AndersS — Sat, 30 Dec 2023 20:24:19 GMT

Hi! YES!

p.s.

The limit in SAS ODA is around 250 million values.

Re: Efficient sort of numeric arrays

Cynthia_sas — Sat, 30 Dec 2023 21:28:41 GMT

Hi:

My tendency would be to use CALL SORTN, which is designed for sorting numeric array members. I did find a reference to "QUICKSORT" in this older user group paper by Paul Dorfman https://support.sas.com/resources/papers/proceedings/proceedings/sugi26/p096-26.pdf , however, I believe the paper may have pre-dated the introduction of CALL SORTN.

You may be limited by memory as to the size of the array, this previous forum thread discusses memory as a limiting factor in array size https://communities.sas.com/t5/SAS-Programming/what-s-the-limit-to-how-many-elements-variables-a-SAS-array-can/td-p/499675 .

I'm sure that others with more experience sorting arrays will have additional feedback.

Cynthia

Re: Efficient sort of numeric arrays

Tom — Sun, 31 Dec 2023 00:56:53 GMT

Transpose the data and use PROC SORT.

Re: Efficient sort of numeric arrays

mkeintz — Sun, 31 Dec 2023 01:46:41 GMT

Like @Cynthia_sas, I would use the CALL SORTN subroutine. It works in a single data step, and sorting 50,000 numeric variables shouldn't add very much demand for memory.

And even if the quicksort algorithm were faster, you would need to include a lot more code (probably as a macro) than the single statement call sortn. Given that your objective is to generate code that "can be published and is very general", you might be better off using the simplest SAS code possible.

Re: Efficient sort of numeric arrays

AndersS — Tue, 02 Jan 2024 16:32:49 GMT

Hi! I have made some tests on the Linux server for SAS ODA.

I used PROC NLIN – quadratic model.
CPU in seconds for CALL SORTN.
SIZE in millions of array elements.

(Good with all the examples in SAS Documentation. Just cut-and-paste)

Result: An almost straight line.
Sorting methods are often linear (like BigOrdo (N*log (N)) for "small models"

and more quadratic (like BigOrdo(N*N)) for "large models".