From owner-freebsd-hackers@FreeBSD.ORG Fri Apr 23 15:41:33 2010 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 723AC106566B for ; Fri, 23 Apr 2010 15:41:33 +0000 (UTC) (envelope-from joerg@britannica.bec.de) Received: from www.sonnenberger.org (www.sonnenberger.org [92.79.50.50]) by mx1.freebsd.org (Postfix) with ESMTP id 334D78FC08 for ; Fri, 23 Apr 2010 15:41:32 +0000 (UTC) Received: from britannica.bec.de (www.sonnenberger.org [192.168.1.10]) by www.sonnenberger.org (Postfix) with ESMTP id 4777466665 for ; Fri, 23 Apr 2010 17:41:32 +0200 (CEST) Received: by britannica.bec.de (Postfix, from userid 1000) id 08B4815C6C; Fri, 23 Apr 2010 17:40:12 +0200 (CEST) Date: Fri, 23 Apr 2010 17:40:12 +0200 From: Joerg Sonnenberger To: freebsd-hackers@freebsd.org Message-ID: <20100423154012.GA10560@britannica.bec.de> Mail-Followup-To: freebsd-hackers@freebsd.org References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) Subject: Re: c question X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 23 Apr 2010 15:41:33 -0000 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. Joerg