From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Nala Ginrut Newsgroups: gmane.lisp.guile.devel Subject: Re: [PATCH] Add-native-hashtable-helper-functions Date: Wed, 27 Mar 2013 18:25:01 +0800 Organization: HFG Message-ID: <1364379901.2730.33.camel@Renee-desktop.suse> References: <1364294433.2730.2.camel@Renee-desktop.suse> <874nfxvn4u.fsf@gnu.org> <1364365958.2730.19.camel@Renee-desktop.suse> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1364379912 23257 80.91.229.3 (27 Mar 2013 10:25:12 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 27 Mar 2013 10:25:12 +0000 (UTC) Cc: guile-devel To: Daniel Hartwig Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Wed Mar 27 11:25:38 2013 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1UKnY1-0004ZY-3C for guile-devel@m.gmane.org; Wed, 27 Mar 2013 11:25:37 +0100 Original-Received: from localhost ([::1]:45258 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UKnXc-0002bP-Nd for guile-devel@m.gmane.org; Wed, 27 Mar 2013 06:25:12 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:43217) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UKnXY-0002Zc-BN for guile-devel@gnu.org; Wed, 27 Mar 2013 06:25:10 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UKnXW-0004Ts-EW for guile-devel@gnu.org; Wed, 27 Mar 2013 06:25:08 -0400 Original-Received: from mail-pb0-f47.google.com ([209.85.160.47]:46821) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UKnXW-0004TU-6g for guile-devel@gnu.org; Wed, 27 Mar 2013 06:25:06 -0400 Original-Received: by mail-pb0-f47.google.com with SMTP id rp2so5214409pbb.20 for ; Wed, 27 Mar 2013 03:25:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:message-id:subject:from:to:cc:date:in-reply-to :references:organization:content-type:x-mailer:mime-version :content-transfer-encoding; bh=xve9XPKtsd1QI7Fc4iw4nuacUiGSw7iqYTTingJzYNk=; b=k9R7cVp9R2hLEMZTL2t9/Sp5rUZXGsRjn0Y2kN5PR5HO1H3iFsdqSlmzOr/Utnf76a JxXpRYLiyo8s7MumqYq7yyk0IRJF8BxLOwZxG2gmIazvtASXJ2kwtsFRC6Ni+UOg2bAJ 02YAF5ArbwnBC2CagLquAN+OAL1+9gU9WZC0DaS3DVe279aC0T1XWOMaL4FKlKLUhCV6 sVGMAalqt060NqQW806OwFlj/D1DwfMqE6jaJ/qBhvO1tAD30+rHCJe2BhNLyA/HuS7P cvFYirqqm69tfk2XS6VBJmxB2oStM24PSSGpihmrujCjjVKmjGcYMUFP0OPksv9jMtQN oz9w== X-Received: by 10.68.0.41 with SMTP id 9mr28730625pbb.132.1364379905435; Wed, 27 Mar 2013 03:25:05 -0700 (PDT) Original-Received: from [147.2.147.112] ([61.14.130.226]) by mx.google.com with ESMTPS id ux10sm2302302pab.1.2013.03.27.03.25.03 (version=SSLv3 cipher=RC4-SHA bits=128/128); Wed, 27 Mar 2013 03:25:04 -0700 (PDT) In-Reply-To: X-Mailer: Evolution 3.4.4 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 209.85.160.47 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:16019 Archived-At: hi Daniel! First, I'll appreciate your patience. ;-) On Wed, 2013-03-27 at 16:55 +0800, Daniel Hartwig wrote: > On 27 March 2013 14:32, Nala Ginrut wrote: > > On Wed, 2013-03-27 at 13:10 +0800, Daniel Hartwig wrote: > >> On 27 March 2013 08:47, Nala Ginrut wrote: > >> > > >> > 在 2013-3-27 AM5:59，"Ludovic Courtès" 写道： > >> > > >> > > >> >> > >> >> Nala Ginrut skribis: > >> >> > >> > >> Hi now > >> > >> >> > * hash-items: get the amount of items in the hash table > >> >> > >> >> There’s already ‘hash-count’, recently added. > >> >> > >> > > >> > If I need to check the amount of items > >> > each time in the loop, hash-count will do redundant visit for all items. But > >> > hash-items is efficient. > >> > > >> > >> If you refer back to the thread discussing this, a constant time count > >> of items was rejected in favour of the more general operator, and even > >> that is provided only as a convenience. That a constant time count of > >> items is available is an implementation detail. It is generally > >> undesirably to expose such details. > >> > > > > Well, could you point me out how can I get the amount of items with > > hash-count in constant time? > > No. I offer only the vague notion that if this is critical to a > program or some part, it is time to seriously reexamine the design of > that. > > The concept of “number of items” is not well defined for > dictionaries. Do you currently mean: > > - number of key–value associations; > - number of unique key–value associations; > - number of unique values; > - number of unique keys. > > The answer changes depending on the task at hand. The ability to > compute any of those numbers varies wildly amongst the possible > implementations. As an internal detail of the _current_ > ‘make-hash-table’ in Guile, the first, second, and forth definition > are equivalent and can be determined in constant time. For alist > and vhash, none of those are equivalent. > > In the previous discussion, the motivating example used ‘hash-count’ > to test for a condition in a way that was simultaneously unreliable > and difficult to verify. Refactoring to avoid that would certainly > yield an algorithm without one or the other of those undesirable > traits. Though I only made a solitary and rough attempt at > demonstrating this, the revised design had a better worse-case > complexity and was reliable. > > An other, less “essential” use was completely superficial: > > (if (not (zero? (hash-count (identity #t) t))) > (hash-for-each proc t)) > All right, I found this string in the manual: ---------------------------cut----------------------- To quickly determine the total number of elements, use `(const #t)' for PRED. ---------------------------end----------------------- So we don't need hash-items anymore. ;-P And sorry for bother since it's too new that I don't familiar with it. Since it's in-explicit for such a function, how about add: (define (hash-items ht) (hash-count (const #t) ht)) > which, except for any time spent counting, is equivalent to: > > (hash-for-each proc t) > > > IMO, return the count of inner record is most explicit way. > > > >> The two fundamental queries on dictionary types are: extract the value > >> associated with a given key; and iterate over all key–value pairs. > >> Algorithms where hash-count is a critical operation (e.g. run inside a > >> loop) are poorly designed, and not something to be encouraged by > >> providing constant-time guarantees on that in the API. A > >> well-designed API encourages sound algorithm design by the interfaces > >> it _omits_ just as much those it includes. Here the goal is to expose > >> an interface to the abstract data type, not any particular > >> implementation. (Yes, some details are naturally leaked e.g. alist > >> structure, but this is not a justification to leak even more.) > >> > > > > Yes I won't against assoc & iterate are the most common operations. > > But as an user who writing programs with Guile, people can't just use > > the most common operations. They need more helpful things to alleviate > > the workload. Though we can write all things with most common > > operations, that's terrible for a practical programming. > > That just like to say, I gave you all the bricks and cement, build > > whatever you want, but don't ask for anything extra can be built with > > bricks and cement. > > For these particular procedures, I would put it more like: > > we do not supply those because all they do is shoot your feet. > > > > > And even our aim is to provide a clean and elegant language > > implementation, but if it's too clean and elegant, it's only for > > appreciation, not using. > > > > I'm not forcing to add my hash-items or hash-size, but I have to call > > for any implementation for these two things, and I wish they add into > > the core. > > Alas, not just _any_ implementation can provide these. By coincidence, > _one_ of Guile's can, but do not be fooled: this is not useful > information for an application to have. If your application needs (?) > this to perform well, or to function at all, there is a much better > way to achieve the same result. Guaranteed. > > Likewise for ‘hash-keys’. > > Perhaps you like to point out some code where you feel this is > essential? > Well, I can't say hash-keys is very common though I used it. I suggest add it just because I found Racket has it. That makes me guess it's common for others. And for hash-size, I know a way to detect it with hash-count, since our native hash-table size grows according to a given "steps table". I suggest it because I thought users can't get this info unless guile core export it. > Regards