From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 4589 invoked by alias); 24 Sep 2002 17:53:48 -0000 Mailing-List: contact gdb-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-owner@sources.redhat.com Received: (qmail 4582 invoked from network); 24 Sep 2002 17:53:47 -0000 Received: from unknown (HELO jackfruit.Stanford.EDU) (171.64.38.136) by sources.redhat.com with SMTP; 24 Sep 2002 17:53:47 -0000 Received: (from carlton@localhost) by jackfruit.Stanford.EDU (8.11.6/8.11.6) id g8OHrg009133; Tue, 24 Sep 2002 10:53:42 -0700 X-Authentication-Warning: jackfruit.Stanford.EDU: carlton set sender to carlton@math.stanford.edu using -f To: Daniel Berlin Cc: Daniel Jacobowitz , Jim Blandy , gdb@sources.redhat.com Subject: Re: suggestion for dictionary representation References: From: David Carlton Date: Tue, 24 Sep 2002 10:53:00 -0000 In-Reply-To: Message-ID: User-Agent: Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.4 (Common Lisp) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-SW-Source: 2002-09/txt/msg00382.txt.bz2 On Tue, 24 Sep 2002 13:42:18 -0400, Daniel Berlin said: > (Who the heck thought it would be smart to have a big Oh and little > Oh, fer instance) :-) > If your average chain lengths go above log n (the number of keys > we'd have to strcmp in the skiplist), which in fact, for large > files, they were, then the skiplist will likely be better, because > it'll perform less comparisons, *and* doesn't have do to the hash > function calculation. I'm not entirely sure I understand your assumptions in this last paragraph; are you assuming the number of buckets will remain constant? I think that, if we're going to use hash tables for global symbols, we'll want to resize the hash tables as necessary. My apologies for not making that clear; that's why I said that hash tables were amortized O(n) rather than just O(n). (But this is, of course, yet another way that the constant factor for hash tables could be larger than one might like.) > I would actually suggest neither hash tables or skiplists, but > ternary search trees. Thanks for the references; I'll give them a look. David Carlton carlton@math.stanford.edu