From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Andy Sonnenburg Newsgroups: gmane.emacs.devel Subject: Re: Binary Search Tree and Treap Functions bst-assq and treap-put Date: Sun, 4 Dec 2016 07:14:26 -0500 Message-ID: References: NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=94eb2c09538ecd28dc0542d41ce5 X-Trace: blaine.gmane.org 1480853679 6673 195.159.176.226 (4 Dec 2016 12:14:39 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 4 Dec 2016 12:14:39 +0000 (UTC) Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Dec 04 13:14:35 2016 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cDVge-0000ZY-94 for ged-emacs-devel@m.gmane.org; Sun, 04 Dec 2016 13:14:32 +0100 Original-Received: from localhost ([::1]:34116 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cDVgh-00071w-VL for ged-emacs-devel@m.gmane.org; Sun, 04 Dec 2016 07:14:35 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:52287) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cDVgb-00071c-Je for emacs-devel@gnu.org; Sun, 04 Dec 2016 07:14:30 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cDVga-0002oj-MJ for emacs-devel@gnu.org; Sun, 04 Dec 2016 07:14:29 -0500 Original-Received: from mail-qk0-x22f.google.com ([2607:f8b0:400d:c09::22f]:34878) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1cDVga-0002oT-Ex for emacs-devel@gnu.org; Sun, 04 Dec 2016 07:14:28 -0500 Original-Received: by mail-qk0-x22f.google.com with SMTP id n204so321761685qke.2 for ; Sun, 04 Dec 2016 04:14:28 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=0oZUD1Dwv6GiHXOI3g2Nr+4yzPYcrbOheKfaUZctDL8=; b=xcDCgypqSpeoE7ZXck0wm/oChZ3xFR5Ouf9quB+frF8UZ8AoZeJXmtrq8tPlPRFhGP 48Vacdfky3ePjO90tokJPjKWcuuDISCW5FzkxeCvHVy3Mt+GVbV3jDPQrnLtAGmQN3tJ UISXIko1lsVwYmFNYsWLrTo19D6xGNG6+e60NHZXdxj2qInaknzKSseeWKpoVO1IxmhJ 8fVmMfsGehU5S2V4ROZdq3hIGrcPjhKvQAHayqjrDCqkdzw/F7AV/D1FlkuyrxuYl5ry LUOO5PAucY8Pdci4GAPFzIg9Z9fJiaWN0HF6qA81a9bj9MM9NzCFY74atE4JbiEBZtXk 7ckw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=0oZUD1Dwv6GiHXOI3g2Nr+4yzPYcrbOheKfaUZctDL8=; b=B/HNhnw8BD/ERG4LZSyJ3tNr17uCpn9Nk9QVInZ6GTyq2OVH+1ecAT+qviti/mqN8p 1MrKde2Y3F6275+lSgzsq+p63GcLxXH4fj0d9pWZSMzaaT932QiN1FNM/z45n42jb9K3 N8nGaaRNuxaxEXgRSHesx2KNv/9F6mb+0zg9UDumUDp8+d3APXmaI1gVOng4Dx7EdNSX 52jboMY2k5LHlLkF9pSDNSWf3tzq3XHigOnIt2PsBLt50CInJY99MMhGDUZVOEAvAmb1 JLxa9feVLeoni4wz52s5svE09dJLkiNOqWkDDtrhiHcGHskWp9IIdH+ETKM+Wwlx38pg zDaA== X-Gm-Message-State: AKaTC00QTXaV1jbVKxvu4yY6qBlZ4Cf2j5BnfeurXik0Hxv5Ij2IOqkxBXuIucX7tQZ3tQGARIfmmXNFLL4LJw== X-Received: by 10.55.39.195 with SMTP id n186mr45280399qkn.103.1480853667258; Sun, 04 Dec 2016 04:14:27 -0800 (PST) Original-Received: by 10.12.171.81 with HTTP; Sun, 4 Dec 2016 04:14:26 -0800 (PST) Original-Received: by 10.12.171.81 with HTTP; Sun, 4 Dec 2016 04:14:26 -0800 (PST) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2607:f8b0:400d:c09::22f X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:210014 Archived-At: --94eb2c09538ecd28dc0542d41ce5 Content-Type: text/plain; charset=UTF-8 That's too bad (I mean, its good for performance, but unfortunate one of the use cases doesn't exist). However, the treap functions may still be of general use. Let me know if there is any interest. They are documented and tested. They fill a gap between alists (persistent, linear lookup) and hash tables (ephemeral, constant lookup) by being persistent while providing average case logarithmic lookup. On Dec 3, 2016 11:34 PM, "Stefan Monnier" wrote: > now. I intend to use these functions to make lexically-scoped variable > lookup average case O(log(n)) instead of the current O(n). AFAIK it's O(1) currently (for byte-compiled code only, but performance of non-byte-compiled code should be of no importance). Stefan --94eb2c09538ecd28dc0542d41ce5 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

That's too bad (I mean, its good for performance, but un= fortunate one of the use cases doesn't exist).=C2=A0 However, the treap= functions may still be of general use.=C2=A0 Let me know if there is any i= nterest.=C2=A0 They are documented and tested.=C2=A0 They fill a gap betwee= n alists (persistent, linear lookup) and hash tables (ephemeral, constant l= ookup) by being persistent while providing average case logarithmic lookup.=


On Dec 3, 2016 11= :34 PM, "Stefan Monnier" <monnier@iro.umontreal.ca> wrote:
> now.=C2=A0 I intend t= o use these functions to make lexically-scoped variable
> lookup average case O(log(n)) instead of the current O(n).

AFAIK it's O(1) currently (for byte-compiled code only, but perfo= rmance
of non-byte-compiled code should be of no importance).


=C2=A0 =C2=A0 =C2=A0 =C2=A0 Stefan



--94eb2c09538ecd28dc0542d41ce5--