public inbox for gsl-discuss@sourceware.org
 help / color / mirror / Atom feed
From: Patrick Alken <patrick.alken@Colorado.EDU>
To: "gsl-discuss@sourceware.org" <gsl-discuss@sourceware.org>
Subject: switched sparse format to binary trees
Date: Mon, 28 Apr 2014 01:32:00 -0000	[thread overview]
Message-ID: <535DAFC0.8090402@colorado.edu> (raw)

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

             reply	other threads:[~2014-04-28  1:32 UTC|newest]

Thread overview: 16+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2014-04-28  1:32 Patrick Alken [this message]
2014-04-28 22:35 ` Gerard Jungman
2014-04-29  1:13   ` Patrick Alken
2014-04-29  8:40     ` Frank Reininghaus
2014-04-29 19:15       ` Gerard Jungman
2014-04-29 19:52         ` Patrick Alken
2014-04-29 22:07           ` Gerard Jungman
2014-05-01 18:46             ` Patrick Alken
2014-05-01 23:21               ` Gerard Jungman
2014-05-02  1:48                 ` GSL containers (switched sparse format to binary trees) Gerard Jungman
2014-05-02  1:56                   ` Gerard Jungman
2014-05-02  8:29                     ` Rhys Ulerich
2014-05-02  8:33                       ` Rhys Ulerich
2014-05-02  8:52                         ` Rhys Ulerich
2014-05-02 15:02                     ` Patrick Alken
2014-05-13 21:59                       ` Gerard Jungman

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=535DAFC0.8090402@colorado.edu \
    --to=patrick.alken@colorado.edu \
    --cc=gsl-discuss@sourceware.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).