* Sorting implemented in Guile standard library
@ 2020-08-16 20:56 Zelphir Kaltstahl
2020-08-16 21:11 ` Bill Markmann
0 siblings, 1 reply; 4+ messages in thread
From: Zelphir Kaltstahl @ 2020-08-16 20:56 UTC (permalink / raw)
To: Guile User
Hello Guile Users!
I was checking out
https://www.gnu.org/software/guile/manual/html_node/Sorting.html and
noticed, that the definition of `sort` does not mention, which algorithm
is used for sorting:
> Sort the sequence items, which may be a list or a vector. less is used
for comparing the sequence elements. This is not a stable sort.
So my question is: Which algorithm is used for Guile's `sort` function?
Regards,
Zelphir
--
repositories: https://notabug.org/ZelphirKaltstahl
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Sorting implemented in Guile standard library 2020-08-16 20:56 Sorting implemented in Guile standard library Zelphir Kaltstahl @ 2020-08-16 21:11 ` Bill Markmann 2020-08-18 19:32 ` Zelphir Kaltstahl 0 siblings, 1 reply; 4+ messages in thread From: Bill Markmann @ 2020-08-16 21:11 UTC (permalink / raw) To: Zelphir Kaltstahl; +Cc: Guile User I'm not a guile hacker, but looking at the source for "libguile/sort.c", it looks like quicksort: #include "sort.h" /* We have two quicksort variants: one for SCM (#t) arrays and one for typed arrays. */ #define NAME quicksort #define INC_PARAM ssize_t inc, #define VEC_PARAM SCM * ra, #define GET(i) ra[(i)*inc] #define SET(i, val) ra[(i)*inc] = val #include "quicksort.i.c" The sort functions look like they call "s_scm_restricted_vector_sort_x", and then in there: if (handle.element_type == SCM_ARRAY_ELEMENT_TYPE_SCM) quicksort (scm_array_handle_writable_elements (&handle) - dims[0].lbnd * dims[0].inc, spos, epos, dims[0].inc, less); else quicksorta (&handle, spos, epos, less); I'd assume that's what is underneath (sort items less) and friends. Just a guess, though... :-) On Sun, Aug 16, 2020 at 4:56 PM Zelphir Kaltstahl < zelphirkaltstahl@posteo.de> wrote: > Hello Guile Users! > > I was checking out > https://www.gnu.org/software/guile/manual/html_node/Sorting.html and > noticed, that the definition of `sort` does not mention, which algorithm > is used for sorting: > > > Sort the sequence items, which may be a list or a vector. less is used > for comparing the sequence elements. This is not a stable sort. > > So my question is: Which algorithm is used for Guile's `sort` function? > > Regards, > Zelphir > > -- > repositories: https://notabug.org/ZelphirKaltstahl > > > ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Sorting implemented in Guile standard library 2020-08-16 21:11 ` Bill Markmann @ 2020-08-18 19:32 ` Zelphir Kaltstahl 2020-08-18 20:01 ` Stefan Israelsson Tampe 0 siblings, 1 reply; 4+ messages in thread From: Zelphir Kaltstahl @ 2020-08-18 19:32 UTC (permalink / raw) To: Bill Markmann; +Cc: Guile User Hello Bill! Thanks for looking into it! Regards, Zelphir On 16.08.20 23:11, Bill Markmann wrote: > I'm not a guile hacker, but looking at the source for > "libguile/sort.c", it looks like quicksort: > > #include "sort.h" > > /* We have two quicksort variants: one for SCM (#t) arrays and one for > typed arrays. > */ > > #define NAME quicksort > #define INC_PARAM ssize_t inc, > #define VEC_PARAM SCM * ra, > #define GET(i) ra[(i)*inc] > #define SET(i, val) ra[(i)*inc] = val > #include "quicksort.i.c" > > The sort functions look like they > call "s_scm_restricted_vector_sort_x", and then in there: > > if (handle.element_type == SCM_ARRAY_ELEMENT_TYPE_SCM) > quicksort (scm_array_handle_writable_elements (&handle) - > dims[0].lbnd * dims[0].inc, > spos, epos, dims[0].inc, less); > else > quicksorta (&handle, spos, epos, less); > > > I'd assume that's what is underneath (sort items less) and friends. > Just a guess, though... :-) > > > On Sun, Aug 16, 2020 at 4:56 PM Zelphir Kaltstahl > <zelphirkaltstahl@posteo.de <mailto:zelphirkaltstahl@posteo.de>> wrote: > > Hello Guile Users! > > I was checking out > https://www.gnu.org/software/guile/manual/html_node/Sorting.html and > noticed, that the definition of `sort` does not mention, which > algorithm > is used for sorting: > > > Sort the sequence items, which may be a list or a vector. less > is used > for comparing the sequence elements. This is not a stable sort. > > So my question is: Which algorithm is used for Guile's `sort` > function? > > Regards, > Zelphir > > -- > repositories: https://notabug.org/ZelphirKaltstahl > > -- repositories: https://notabug.org/ZelphirKaltstahl ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Sorting implemented in Guile standard library 2020-08-18 19:32 ` Zelphir Kaltstahl @ 2020-08-18 20:01 ` Stefan Israelsson Tampe 0 siblings, 0 replies; 4+ messages in thread From: Stefan Israelsson Tampe @ 2020-08-18 20:01 UTC (permalink / raw) To: Zelphir Kaltstahl; +Cc: Guile User Can we get some benchmarking, calling out to scheme for each comparison seam expensive. I could think of an algorithm that dispatch on the <,>,else and use fast C for '<','>' and a scheme implementation for 'else'. On Tue, Aug 18, 2020 at 9:33 PM Zelphir Kaltstahl < zelphirkaltstahl@posteo.de> wrote: > Hello Bill! > > Thanks for looking into it! > > Regards, > Zelphir > > On 16.08.20 23:11, Bill Markmann wrote: > > I'm not a guile hacker, but looking at the source for > > "libguile/sort.c", it looks like quicksort: > > > > #include "sort.h" > > > > /* We have two quicksort variants: one for SCM (#t) arrays and one for > > typed arrays. > > */ > > > > #define NAME quicksort > > #define INC_PARAM ssize_t inc, > > #define VEC_PARAM SCM * ra, > > #define GET(i) ra[(i)*inc] > > #define SET(i, val) ra[(i)*inc] = val > > #include "quicksort.i.c" > > > > The sort functions look like they > > call "s_scm_restricted_vector_sort_x", and then in there: > > > > if (handle.element_type == SCM_ARRAY_ELEMENT_TYPE_SCM) > > quicksort (scm_array_handle_writable_elements (&handle) - > > dims[0].lbnd * dims[0].inc, > > spos, epos, dims[0].inc, less); > > else > > quicksorta (&handle, spos, epos, less); > > > > > > I'd assume that's what is underneath (sort items less) and friends. > > Just a guess, though... :-) > > > > > > On Sun, Aug 16, 2020 at 4:56 PM Zelphir Kaltstahl > > <zelphirkaltstahl@posteo.de <mailto:zelphirkaltstahl@posteo.de>> wrote: > > > > Hello Guile Users! > > > > I was checking out > > https://www.gnu.org/software/guile/manual/html_node/Sorting.html and > > noticed, that the definition of `sort` does not mention, which > > algorithm > > is used for sorting: > > > > > Sort the sequence items, which may be a list or a vector. less > > is used > > for comparing the sequence elements. This is not a stable sort. > > > > So my question is: Which algorithm is used for Guile's `sort` > > function? > > > > Regards, > > Zelphir > > > > -- > > repositories: https://notabug.org/ZelphirKaltstahl > > > > > -- > repositories: https://notabug.org/ZelphirKaltstahl > > ^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2020-08-18 20:01 UTC | newest] Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-08-16 20:56 Sorting implemented in Guile standard library Zelphir Kaltstahl 2020-08-16 21:11 ` Bill Markmann 2020-08-18 19:32 ` Zelphir Kaltstahl 2020-08-18 20:01 ` Stefan Israelsson Tampe
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).