Date: Fri, 23 Apr 2010 20:21:25 +0200 From: Pieter de Goeje <pieter@degoeje.nl> To: freebsd-hackers@freebsd.org Cc: Leinier Cruz Salfran <salfrancl.listas@gmail.com>, Joerg Sonnenberger <joerg@britannica.bec.de> Subject: Re: c question Message-ID: <201004232021.26160.pieter@degoeje.nl> In-Reply-To: <20100423154012.GA10560@britannica.bec.de> References: <l2ga2585ef1004090709u821fc979i226a3125d9da8251@mail.gmail.com> <i2za0777e081004230818y9008c7b7yc574298df85933dc@mail.gmail.com> <20100423154012.GA10560@britannica.bec.de>
next in thread | previous in thread | raw e-mail | index | archive | help
On Friday 23 April 2010 17:40:12 Joerg Sonnenberger wrote: > On Fri, Apr 23, 2010 at 06:18:46PM +0300, Eitan Adler wrote: > > > - use a matrix is faster than use a linked list? > > > > For what? > > For insertion and deletion no - linked list is faster. For sequential > > access they are the same speed (forgetting look-ahead caching). For > > random access matrix is faster. > > Actually -- it depends. Removing the tail and inserting at tail is > amortised constant time for arrays if done using the double-on-full > trick. In that case, array can be the faster datastructure too. Random deletes can be made O(1) if you don't care about the order of the elements in an array. - Pieter
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201004232021.26160.pieter>