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: Sort on vectors slow Date: Thu, 14 Oct 2004 14:28:31 +0200 Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Message-ID: <1097756911.5279.3531.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 1097757209 27390 80.91.229.6 (14 Oct 2004 12:33:29 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Thu, 14 Oct 2004 12:33:29 +0000 (UTC) Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Thu Oct 14 14:33:18 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 1CI4nG-0001oY-00 for ; Thu, 14 Oct 2004 14:33:18 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.33) id 1CI4uL-00008V-JH for guile-user@m.gmane.org; Thu, 14 Oct 2004 08:40:37 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.33) id 1CI4uE-000064-CR for guile-user@gnu.org; Thu, 14 Oct 2004 08:40:30 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.33) id 1CI4uC-000052-KG for guile-user@gnu.org; Thu, 14 Oct 2004 08:40:28 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.33) id 1CI4uC-0008WU-Ah for guile-user@gnu.org; Thu, 14 Oct 2004 08:40:28 -0400 Original-Received: from [195.47.247.21] (helo=csmtp.b-one.net) by monty-python.gnu.org with esmtp (Exim 4.34) id 1CI4mv-0006EP-3j for guile-user@gnu.org; Thu, 14 Oct 2004 08:32:57 -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 6C58AFBA52; Thu, 14 Oct 2004 14:32:56 +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:3567 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:3567 I noticed that the default sort routine on vectors is very slow. I'm using the restricted-vector-sort! and compared with a merge sort on vectors instead, the speed difference is tremendous. In this example foo is a vector with 100000 elements (an often occuring size for me currently), here with random numbers. Machine is a 2.2 GHz P4. Observe that the restricted-vector-qsort I'm using takes inclusive endpos according to the doc (I've mentioned this on guile-devel). (begin (define vlen 1000000) (define foo (make-vector vlen 9999999)) (array-map! foo random foo) (define bar (copy-vector bar)) ) (verbose 2) (restricted-vector-qsort! foo < 0 (1- vlen)) ;;; 249150 msec (71790 msec in gc) (array-copy! bar foo) (restricted-vector-msort! foo < 0 (1- vlen)) ;;; 1060 msec (300 msec in gc) I'm not sure if this huge difference makes sense, or if it indicates a problem with quicksort, which I took from libc earlier (1998). I've found in some text though that time complexity of quicksort is O(N^2) in worst case, only O(N log N) in average, and merge sort is O(N log N) in all cases. An advantage is that merge sort is stable also, which quicksort isn't. Anyone knowing anything about memory usage for the two algorithms? /Roland 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. 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, len; 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); len = 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 (len * sizeof(SCM)); else if (SCM_VECTORP(tmpv) && (SCM_VECTOR_LENGTH(tmpv) >= vlen)) { temp = SCM_WRITABLE_VELTS(tmpv); } else SCM_WRONG_TYPE_ARG (1, vec); scm_merge_vector_step (vec, temp, cmp, less, spos, len); 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