Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Andy Sonnenburg]

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" <address@hidden> 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