From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Roland Orre Newsgroups: gmane.lisp.guile.user Subject: Re: Sort on vectors slow Date: Thu, 14 Oct 2004 16:22:35 +0200 Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Message-ID: <1097763755.5279.3655.camel@localhost> NNTP-Posting-Host: deer.gmane.org Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Trace: sea.gmane.org 1097764050 17261 80.91.229.6 (14 Oct 2004 14:27:30 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Thu, 14 Oct 2004 14:27:30 +0000 (UTC) Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Thu Oct 14 16:27:20 2004 Return-path: Original-Received: from lists.gnu.org ([199.232.76.165]) by deer.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1CI6Zc-0004hY-00 for ; Thu, 14 Oct 2004 16:27:20 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.33) id 1CI6gh-0002HC-EJ for guile-user@m.gmane.org; Thu, 14 Oct 2004 10:34:39 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.33) id 1CI6gc-0002H5-Pi for guile-user@gnu.org; Thu, 14 Oct 2004 10:34:34 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.33) id 1CI6gc-0002Gs-6v for guile-user@gnu.org; Thu, 14 Oct 2004 10:34:34 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.33) id 1CI6gb-0002Gp-3p for guile-user@gnu.org; Thu, 14 Oct 2004 10:34:34 -0400 Original-Received: from [195.47.247.21] (helo=csmtp.b-one.net) by monty-python.gnu.org with esmtp (Exim 4.34) id 1CI6ZJ-0002Q5-PG for guile-user@gnu.org; Thu, 14 Oct 2004 10:27:01 -0400 Original-Received: from bari.bacon.su.se (bari.bacon.su.se [130.237.152.231]) by csmtp.b-one.net (Postfix) with ESMTP id 8747AFBA4B; Thu, 14 Oct 2004 16:27:00 +0200 (CEST) Original-To: guile-user@gnu.org X-Mailer: Ximian Evolution 1.4.6 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.5 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.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.user:3569 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:3569 On Thu, 2004-10-14 at 14:28, Roland Orre wrote: > PS. Code to the restricted-vector-msort! below. I suggest that this > should go into the distribution, alternatively we should replace the > current default quicksort for vectors with merge sort. Typical, the code I sent contained a little bug, which I hadn't noticed as I'm usually using a temporary vector (optional arg) supplied. So, here is a new version of restricted-vector-msort! if anyone is interested or maybe consider it should be put into the distribution. /Roland SCM_DEFINE (scm_restricted_vector_msort_x, "restricted-vector-msort!", 4, 1, 0, (SCM vec, SCM less, SCM startpos, SCM endpos, SCM tmpv), "Sort the sequence @var{items}, which may be a list or a\n" "vector. @var{less} is used for comparing the sequence elements.\n" "The sorting is destructive, that means that the input sequence\n" "is modified to produce the sorted result.\n" "This is a stable sort.") #define FUNC_NAME s_scm_restricted_vector_msort_x { const scm_t_trampoline_2 cmp = compare_function (less, 2, FUNC_NAME); size_t vlen, spos, high; if (SCM_VECTORP (vec)) { SCM *temp; vlen = SCM_VECTOR_LENGTH (vec); SCM_VALIDATE_INUM_MIN_COPY (3, startpos, 0, spos); SCM_ASSERT_RANGE (3, startpos, spos <= vlen); SCM_VALIDATE_INUM_RANGE (4, endpos,0, vlen); high = SCM_INUM (endpos) - spos; /* the following array does not contain any new references to SCM objects, so we can get away with allocing it on the heap. */ if (SCM_UNBNDP(tmpv)) { temp = scm_malloc (vlen * sizeof(SCM)); } else if (SCM_VECTORP(tmpv) && (SCM_VECTOR_LENGTH(tmpv) >= vlen)) { temp = SCM_WRITABLE_VELTS(tmpv); } else SCM_WRONG_TYPE_ARG (5, tmpv); scm_merge_vector_step (vec, temp, cmp, less, spos, high); if (SCM_UNBNDP(tmpv)) free(temp); return SCM_UNSPECIFIED; } else SCM_WRONG_TYPE_ARG (1, vec); } #undef FUNC_NAME _______________________________________________ Guile-user mailing list Guile-user@gnu.org http://lists.gnu.org/mailman/listinfo/guile-user