From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Daniel Hartwig Newsgroups: gmane.lisp.guile.devel Subject: Re: [PATCH] Add-native-hashtable-helper-functions Date: Wed, 27 Mar 2013 16:55:52 +0800 Message-ID: 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: quoted-printable X-Trace: ger.gmane.org 1364374563 3591 80.91.229.3 (27 Mar 2013 08:56:03 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 27 Mar 2013 08:56:03 +0000 (UTC) Cc: guile-devel To: Nala Ginrut Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Wed Mar 27 09:56:29 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 1UKm9e-000645-M4 for guile-devel@m.gmane.org; Wed, 27 Mar 2013 09:56:22 +0100 Original-Received: from localhost ([::1]:34620 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UKm9G-00087s-NK for guile-devel@m.gmane.org; Wed, 27 Mar 2013 04:55:58 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:51596) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UKm9D-00087T-94 for guile-devel@gnu.org; Wed, 27 Mar 2013 04:55:56 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UKm9B-0004oe-Fm for guile-devel@gnu.org; Wed, 27 Mar 2013 04:55:55 -0400 Original-Received: from mail-ie0-x231.google.com ([2607:f8b0:4001:c03::231]:34028) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UKm9B-0004o8-A7 for guile-devel@gnu.org; Wed, 27 Mar 2013 04:55:53 -0400 Original-Received: by mail-ie0-f177.google.com with SMTP id tp5so5397776ieb.8 for ; Wed, 27 Mar 2013 01:55:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:in-reply-to:references:date:message-id :subject:from:to:cc:content-type:content-transfer-encoding; bh=UNsZDWfgFIdu2XWl7+FMiGUjB2oGlrBt0B17FFr0gl4=; b=Hd4RJdDk2XG8IEFx3KKW97o1SmCwxaSw7sDMpdAfPCjvDgdFxunMlvp7OuQT2p+1Of S2YVRmkUZd1AU+HWuccflI0BdU2R9gRYbZlZOg6GS0VHySuQh4MemlLmKJyL+pZ5atcV CzyGNihTpklF2K90i9WRRJNxU0l+lvwTbtPE6kau0PSnQ+QGrWQMCWZpNGBrI05U7bV7 EMNJdSmEcwyfzulG0udEFQpVlGuA6epvOmtL44CNXnlEqGRYRu1kdXsfJYnTFXg6gn4m +/VZY1zHhRVk7+23K0EwgzeMp2TAykuopoabSIOsy7MYaj53XwDTgUmsnspt8P2UkCgn hI3Q== X-Received: by 10.42.70.74 with SMTP id e10mr2832390icj.38.1364374552576; Wed, 27 Mar 2013 01:55:52 -0700 (PDT) Original-Received: by 10.64.26.168 with HTTP; Wed, 27 Mar 2013 01:55:52 -0700 (PDT) In-Reply-To: <1364365958.2730.19.camel@Renee-desktop.suse> X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:4001:c03::231 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:16017 Archived-At: 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: >> > >> > =E5=9C=A8 2013-3-27 AM5:59=EF=BC=8C"Ludovic Court=C3=A8s" =E5=86=99=E9=81=93=EF=BC=9A >> > >> > >> >> >> >> Nala Ginrut skribis: >> >> >> >> Hi now >> >> >> > * hash-items: get the amount of items in the hash table >> >> >> >> There=E2=80=99s already =E2=80=98hash-count=E2=80=99, recently added. >> >> >> > >> > If I need to check the amount of items >> > each time in the loop, hash-count will do redundant visit for all item= s. 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 =E2=80=9Cnumber of items=E2=80=9D is not well defined for dictionaries. Do you currently mean: - number of key=E2=80=93value associations; - number of unique key=E2=80=93value 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_ =E2=80=98make-hash-table=E2=80=99 in Guile, the first, second, and forth de= finition 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 =E2=80=98hash-count= =E2=80=99 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 =E2=80=9Cessential=E2=80=9D use was completely superficial: (if (not (zero? (hash-count (identity #t) t))) (hash-for-each proc t)) 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=E2=80=93value pair= s. >> 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 =E2=80=98hash-keys=E2=80=99. Perhaps you like to point out some code where you feel this is essential? Regards