From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 10897 invoked by alias); 28 Apr 2014 01:32:56 -0000 Mailing-List: contact gsl-discuss-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gsl-discuss-owner@sourceware.org Received: (qmail 10872 invoked by uid 89); 28 Apr 2014 01:32:52 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 X-HELO: ipmx5.colorado.edu Received: from ipmx5.colorado.edu (HELO ipmx5.colorado.edu) (128.138.128.235) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 28 Apr 2014 01:32:50 +0000 From: Patrick Alken Received: from 174-29-218-253.hlrn.qwest.net (HELO [192.168.0.226]) ([174.29.218.253]) by smtp.colorado.edu with ESMTP/TLS/DHE-RSA-AES128-SHA; 27 Apr 2014 19:32:48 -0600 Message-ID: <535DAFC0.8090402@colorado.edu> Date: Mon, 28 Apr 2014 01:32:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0 MIME-Version: 1.0 To: "gsl-discuss@sourceware.org" Subject: switched sparse format to binary trees Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-SW-Source: 2014-q2/txt/msg00013.txt.bz2 I received a bug report from someone who found that the gsl_spmatrix_set() function did not properly detect duplicate elements (ie it could set the same (i,j) matrix element to more than 1 value). This was related to the linear array scheme I had originally implemented, which made it very infefficient to find duplicates (ie: a linear search was required each time). So I've changed the storage scheme for the triplet representation to a binary tree (specifically the AVL balanced binary tree). I took code from the GNU libavl library for the tree manipulation stuff. This actually makes a huge speed improvement in duplicate detection and element retrieval for large sparse matrices. There may however be a performance hit since a new tree node must be allocated each time an element is added to the matrix. But I believe the tradeoff is worth it. Anyone using gsl_spmatrix in their code will need to recompile since the binary format of that struct has changed. Patrick