Re: choose-and-remove! operation taylanbayirli@xxxxxx 12 Sep 2015 05:12 UTC

"Arthur A. Gleckler" <xxxxxx@speechcode.com> writes:

> On Fri, Sep 11, 2015 at 12:00 PM, Taylan Ulrich Bayırlı/Kammer
> <xxxxxx@gmail.com> wrote:
>
>     OK, that's less efficient. I would question how often that
>     difference in efficiency is relevant though. If we absolutely want
>     the efficient push/pop then maybe we should name them
>     hash-table-update/pop! and such.  Or let users define that when
>     they want it and leave it out of the spec.
>
> It's O(1) vs. O(N), which quickly matters, especially when it's
> executed in a loop.

I think I was a bit unclear.

I meant that (pop! (hash-table-ref ht k)) could replace the
hash-table-pop! that's currently in SRFI-125, so the identifier is freed
up for this new hash-table-pop!.

(pop! (hash-table-ref ht k)) is (theoretically) a bit less efficient
than a direct hash-table-pop! (SRFI-125) because the latter can do the
key lookup once and get and set its value in one step whereas the former
would typically expand to the following code, which does a separate ref
and then a set on the hash table:

    (let ((v (hash-table-ref ht k)))
      ((setter hash-table-ref) ht k (cdr v))
      (car v))

If we can live with that, and I think we could, then hash-table-pop! in
SRFI-125 can be freed up.

That being said, I just noticed that (pop! (hash-table-ref ht k)) does
not handle the case where 'k' is not found in 'ht'.  That might need
some more thought.  (The extra 'x' argument to 'pop!' in my previous
mail was just an error.)

Taylan