Dear pkg developers, Are there any ways to check which sorting algorithm is being used when calling `order` function? Documentation at https://stat.ethz.ch/R-manual/R-devel/library/base/html/sort.html says it is radix for length < 2^31 On the other hand, I am using R_orderVector1, passing in double float smaller than 2^31. Short description of it states "Fast version of 1-argument case of R_orderVector". Should I expect R_orderVector1 follow the same algo as R's order()? If so it should be radix as well. https://github.com/wch/r-source/blob/ed51d34ec195b89462a8531b9ef30b7b72e47204/src/main/sort.c#L1133 If there is no way to check sorting algo, could anyone describe which one R_orderVector1 uses, and if there is easy API to use different ones from C? Best Regards, Jan Gorecki
[R-pkg-devel] R_orderVector1 - algo: radix, shell, or another?
7 messages · Jeff Newmiller, Simon Urbanek, Ivan Krylov +1 more
Have you read the output of order entered at the R console?
On September 24, 2023 1:38:41 AM PDT, Jan Gorecki <j.gorecki at wit.edu.pl> wrote:
Dear pkg developers, Are there any ways to check which sorting algorithm is being used when calling `order` function? Documentation at https://stat.ethz.ch/R-manual/R-devel/library/base/html/sort.html says it is radix for length < 2^31 On the other hand, I am using R_orderVector1, passing in double float smaller than 2^31. Short description of it states "Fast version of 1-argument case of R_orderVector". Should I expect R_orderVector1 follow the same algo as R's order()? If so it should be radix as well. https://github.com/wch/r-source/blob/ed51d34ec195b89462a8531b9ef30b7b72e47204/src/main/sort.c#L1133 If there is no way to check sorting algo, could anyone describe which one R_orderVector1 uses, and if there is easy API to use different ones from C? Best Regards, Jan Gorecki [[alternative HTML version deleted]]
______________________________________________ R-package-devel at r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-package-devel
Sent from my phone. Please excuse my brevity.
Hi Jeff, Yes I did. My question is about R_orderVector1 which is part of public R C api. Should I notice something relevant in the source of R's order? Best Jan
On Sun, Sep 24, 2023, 17:27 Jeff Newmiller <jdnewmil at dcn.davis.ca.us> wrote:
Have you read the output of order entered at the R console? On September 24, 2023 1:38:41 AM PDT, Jan Gorecki <j.gorecki at wit.edu.pl> wrote:
Dear pkg developers, Are there any ways to check which sorting algorithm is being used when calling `order` function? Documentation at https://stat.ethz.ch/R-manual/R-devel/library/base/html/sort.html says it is radix for length < 2^31 On the other hand, I am using R_orderVector1, passing in double float smaller than 2^31. Short description of it states "Fast version of 1-argument case of R_orderVector". Should I expect R_orderVector1 follow the same algo as R's order()? If so it should be radix as well.
If there is no way to check sorting algo, could anyone describe which one R_orderVector1 uses, and if there is easy API to use different ones from
C?
Best Regards,
Jan Gorecki
[[alternative HTML version deleted]]
______________________________________________ R-package-devel at r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-package-devel
-- Sent from my phone. Please excuse my brevity.
You asked how order works. From the R source you can follow which C functions are executed, and since you seem familiar with C you can answer your own question.
On September 24, 2023 11:10:53 AM PDT, Jan Gorecki <j.gorecki at wit.edu.pl> wrote:
Hi Jeff, Yes I did. My question is about R_orderVector1 which is part of public R C api. Should I notice something relevant in the source of R's order? Best Jan On Sun, Sep 24, 2023, 17:27 Jeff Newmiller <jdnewmil at dcn.davis.ca.us> wrote:
Have you read the output of order entered at the R console? On September 24, 2023 1:38:41 AM PDT, Jan Gorecki <j.gorecki at wit.edu.pl> wrote:
Dear pkg developers, Are there any ways to check which sorting algorithm is being used when calling `order` function? Documentation at https://stat.ethz.ch/R-manual/R-devel/library/base/html/sort.html says it is radix for length < 2^31 On the other hand, I am using R_orderVector1, passing in double float smaller than 2^31. Short description of it states "Fast version of 1-argument case of R_orderVector". Should I expect R_orderVector1 follow the same algo as R's order()? If so it should be radix as well.
If there is no way to check sorting algo, could anyone describe which one R_orderVector1 uses, and if there is easy API to use different ones from
C?
Best Regards,
Jan Gorecki
[[alternative HTML version deleted]]
______________________________________________ R-package-devel at r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-package-devel
-- Sent from my phone. Please excuse my brevity.
Sent from my phone. Please excuse my brevity.
I think the logic Jeff had in mind is that R order() uses C do_order() for method="shell" and since do_order() uses orderVector1() by induction it is the shell-sort implementation. order() itself uses whatever you specify in method=. Cheers, Simon
On Sep 25, 2023, at 7:10 AM, Jan Gorecki <j.gorecki at wit.edu.pl> wrote: Hi Jeff, Yes I did. My question is about R_orderVector1 which is part of public R C api. Should I notice something relevant in the source of R's order? Best Jan On Sun, Sep 24, 2023, 17:27 Jeff Newmiller <jdnewmil at dcn.davis.ca.us> wrote:
Have you read the output of order entered at the R console? On September 24, 2023 1:38:41 AM PDT, Jan Gorecki <j.gorecki at wit.edu.pl> wrote:
Dear pkg developers, Are there any ways to check which sorting algorithm is being used when calling `order` function? Documentation at https://stat.ethz.ch/R-manual/R-devel/library/base/html/sort.html says it is radix for length < 2^31 On the other hand, I am using R_orderVector1, passing in double float smaller than 2^31. Short description of it states "Fast version of 1-argument case of R_orderVector". Should I expect R_orderVector1 follow the same algo as R's order()? If so it should be radix as well.
If there is no way to check sorting algo, could anyone describe which one R_orderVector1 uses, and if there is easy API to use different ones from
C?
Best Regards,
Jan Gorecki
[[alternative HTML version deleted]]
______________________________________________ R-package-devel at r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-package-devel
-- Sent from my phone. Please excuse my brevity.
[[alternative HTML version deleted]]
______________________________________________ R-package-devel at r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-package-devel
? Sun, 24 Sep 2023 10:38:41 +0200 Jan Gorecki <j.gorecki at wit.edu.pl> ?????:
could anyone describe which one R_orderVector1 uses,
The body of the sorting algorithm is defined in the sort2_with_index macro. This is shell sort. (I don't actually recognise sorting algorithms on sight, but the "sincs" array gave it away: <https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/3>.)
and if there is easy API to use different ones from C?
No easy ones, I think. You could construct a call to order(..., method = 'radix') from R or bundle a sort implementation of your own. These are all undocumented implementation details. They could change in a new version of R (although quite a lot of it hasn't changed in 11-22 years). Why are you looking for specific sorting algorithms? Could there be a better way to solve your problem?
Best regards, Ivan
1 day later
Thank you Ivan for all detail. I was looking for particular algo for benchmarking purpose.
On Mon, Sep 25, 2023 at 9:26?AM Ivan Krylov <krylov.r00t at gmail.com> wrote:
? Sun, 24 Sep 2023 10:38:41 +0200 Jan Gorecki <j.gorecki at wit.edu.pl> ?????:
could anyone describe which one R_orderVector1 uses,
The body of the sorting algorithm is defined in the sort2_with_index macro. This is shell sort. (I don't actually recognise sorting algorithms on sight, but the "sincs" array gave it away: < https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/3
.)
and if there is easy API to use different ones from C?
No easy ones, I think. You could construct a call to order(..., method = 'radix') from R or bundle a sort implementation of your own. These are all undocumented implementation details. They could change in a new version of R (although quite a lot of it hasn't changed in 11-22 years). Why are you looking for specific sorting algorithms? Could there be a better way to solve your problem? -- Best regards, Ivan