From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.user Subject: Re: Sorting implemented in Guile standard library Date: Tue, 18 Aug 2020 22:01:10 +0200 Message-ID: References: <1218f943-ea4d-2c67-7ff4-b4747a12194d@posteo.de> <17ea014c-ac7f-a36b-f252-dc62785263ad@posteo.de> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="37844"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Guile User To: Zelphir Kaltstahl Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Tue Aug 18 22:01:39 2020 Return-path: Envelope-to: guile-user@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1k87ne-0009jT-W3 for guile-user@m.gmane-mx.org; Tue, 18 Aug 2020 22:01:38 +0200 Original-Received: from localhost ([::1]:36700 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1k87nd-00040G-Ri for guile-user@m.gmane-mx.org; Tue, 18 Aug 2020 16:01:37 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:37888) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1k87nT-000405-EX for guile-user@gnu.org; Tue, 18 Aug 2020 16:01:27 -0400 Original-Received: from mail-wm1-x333.google.com ([2a00:1450:4864:20::333]:38005) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1k87nQ-0002CH-64 for guile-user@gnu.org; Tue, 18 Aug 2020 16:01:27 -0400 Original-Received: by mail-wm1-x333.google.com with SMTP id t14so75479wmi.3 for ; Tue, 18 Aug 2020 13:01:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=2bcyIRpkJ9tjZF5JNx3XY9Bd//6kNAL5S42Zc/jmpIc=; b=exrV7ZDd6yrRyOEmeRryRHFbhxYKOXIdXuhIWD8zWZHvpvOVAyHunBjOUIe5nOU4Uv B8/V6LNUw754KRxuqda1aPCCiKSeE6o9BDAU8Urfg3BWHXBPw9WM0RaAlr8kaWG9HjfG /dnuH1inG68OVTByyASJQ4qjNVBKlRw4yCXYC+/LIhd2mMIzJ5X7ZQkqmpII1sPrNwK7 7dU8udKQhZmNMDweRmmSyqmR3NfOEsv997xXQm7O5U58QHkyiSZYBGJUhF2AuG0rQrem RcuWRQgfqjF5JMAjxUhy3tdvJ0mdhUdtJ1PdjVRn9zNq83mE1Kxvwjlbdpb8aONzMJT9 XZZA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=2bcyIRpkJ9tjZF5JNx3XY9Bd//6kNAL5S42Zc/jmpIc=; b=d7HkEKE8Jy1Hq9cmtzaPqn/9fGimIPRzREvn8U2YYzfYVWQdM2MKeEnQBAsOZzEMdo l/vLqsFyY85QqY3/E17ohFAHS4U1VuQjwTFaXnnRKo/GU3pS4xznk1QFFDphRaNFz85U abJqxchKLqq20y6N1KvAxECGXRcQwLhuCypYQW+6M8+DyIk27bB8Op30y8ylMWJkO/0Z dQQ58mXZu7Urvitk9Vjh/U8BX+o8t1YFy2i1w5Hqe6jywPQ7HZvlDOJUHcoGTeShCltN 8nLQGfdxz8Pzgz6I5dZltnBwQ2qFKBEx3I2jMhuDKu6hQUmdkxYmcqq8CvpRFBSEkPCM /3zA== X-Gm-Message-State: AOAM530De9VmOP3d5XBJ2bRwZDNVhaSfEzwgqKrDsuph6RVbddVxkTbt wL7gDjCgFNT8iWYQSX1lYV16ZfU/XgChAPN16E8= X-Google-Smtp-Source: ABdhPJwUeTndie638f8yBwR1/cWb/9JNyzBfryLpFD0Z5mG1yhHNO5hy8D7m6wg7Ze5HajUKqeiy2DfdPeD38uMhglM= X-Received: by 2002:a7b:c954:: with SMTP id i20mr1512526wml.189.1597780881689; Tue, 18 Aug 2020 13:01:21 -0700 (PDT) In-Reply-To: <17ea014c-ac7f-a36b-f252-dc62785263ad@posteo.de> Received-SPF: pass client-ip=2a00:1450:4864:20::333; envelope-from=stefan.itampe@gmail.com; helo=mail-wm1-x333.google.com X-detected-operating-system: by eggs.gnu.org: No matching host in p0f cache. That's all we know. X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Content-Filtered-By: Mailman/MimeDel 2.1.23 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Original-Sender: "guile-user" Xref: news.gmane.io gmane.lisp.guile.user:16816 Archived-At: 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 > > > 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 > >