[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Sorting implemented in Guile standard library
From: |
Stefan Israelsson Tampe |
Subject: |
Re: Sorting implemented in Guile standard library |
Date: |
Tue, 18 Aug 2020 22:01:10 +0200 |
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
>
>