From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 1029 invoked by alias); 24 Sep 2002 00:34:56 -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 1022 invoked from network); 24 Sep 2002 00:34:55 -0000 Received: from unknown (HELO mail.cdt.org) (206.112.85.61) by sources.redhat.com with SMTP; 24 Sep 2002 00:34:55 -0000 Received: from dberlin.org (pool-138-88-10-56.res.east.verizon.net [138.88.10.56]) by mail.cdt.org (Postfix) with ESMTP id 8E5AB490054; Mon, 23 Sep 2002 20:11:53 -0400 (EDT) Received: from [192.168.0.252] (account dberlin HELO dberlin.org) by dberlin.org (CommuniGate Pro SMTP 4.0b9a) with ESMTP id 241348; Mon, 23 Sep 2002 20:34:51 -0400 Date: Mon, 23 Sep 2002 17:34:00 -0000 Subject: Re: suggestion for dictionary representation Content-Type: text/plain; charset=US-ASCII; format=flowed Mime-Version: 1.0 (Apple Message framework v546) Cc: Daniel Jacobowitz , Jim Blandy , gdb@sources.redhat.com To: David Carlton From: Daniel Berlin In-Reply-To: Message-Id: <6FDBFE18-CF55-11D6-BA45-000393575BCC@dberlin.org> Content-Transfer-Encoding: 7bit X-SW-Source: 2002-09/txt/msg00355.txt.bz2 > I'm also curious about how it would affect the speed of reading in > symbols. Right now, that should be O(n), where n is the number of > global symbols, right? > If we used expandable hash tables, then I > think it would be amortized O(n) and with the constant factor larger. Nope. Our string hash function is O(N) right now (as are most). Hash tables are only O(N) when the hash function is O(1). Now, if you have it only hash the first x characters, you can make your hash table O(N) again, with the x as the constant. Of course, if only hashing the first x characters causes tons of hash conflicts, it's not going to make your hash table very fast. > (But, I think, not larger in a way that would make a difference.) I'm > curious about how often the "amortized" bit would lead to strange > hiccups, but I don't think that's a big deal. > > But for skip lists, wouldn't it be something like O(n log n)? If so, > that's an issue we have to consider. Put it in perspective. for 1 billion symbols, n is 29.89. for 1 million symbols, n is 19.93.