[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Chicken-users] Alist versus Hash-table
From: |
Peter Bex |
Subject: |
Re: [Chicken-users] Alist versus Hash-table |
Date: |
Tue, 12 Nov 2013 15:41:51 +0100 |
User-agent: |
Mutt/1.4.2.3i |
On Tue, Nov 12, 2013 at 09:24:23AM -0500, John Cowan wrote:
> Peter Bex scripsit:
>
> > alist-update will take O(n) to locate the key just like alist-update!,
> > but when it finds the entry, it will need to build a new list with
> > the entry replaced at the same position. That means it's O(n) to update
> > (for new keys it's O(1), they can just be consed onto the front).
> > In total, that's O(2n). The major extra time you see can not be
> > explained due to that, but the output of time gives a clear hint.
>
> Why was alist-update introduced, anyway? It is more efficient
> to use either alist-update! or alist-cons (from SRFI 1) in any situation
> I can think of. I note that neither SRFI 1 nor the alist-lib egg has it.
Simple: for those who prefer functional updates, but don't want their
lists to keep growing endlessly. Also, in some cases duplciate entries
really mean something different (for example in alist->uri query attribute
mappings and such). You could argue that means they're not true alists,
but it sometimes is convenient to treat them as such.
Cheers,
Peter
--
http://www.more-magic.net
- [Chicken-users] Alist versus Hash-table, Loïc Faure-Lacroix, 2013/11/12
- Re: [Chicken-users] Alist versus Hash-table, Christian Kellermann, 2013/11/12
- Re: [Chicken-users] Alist versus Hash-table, Jörg F. Wittenberger, 2013/11/12
- Re: [Chicken-users] Alist versus Hash-table, Peter Bex, 2013/11/12
- Re: [Chicken-users] Alist versus Hash-table, Loïc Faure-Lacroix, 2013/11/12
- Re: [Chicken-users] Alist versus Hash-table, John Cowan, 2013/11/12
- Re: [Chicken-users] Alist versus Hash-table,
Peter Bex <=
- Re: [Chicken-users] Alist versus Hash-table, John Cowan, 2013/11/12
- Re: [Chicken-users] Alist versus Hash-table, Peter Bex, 2013/11/12
- Re: [Chicken-users] Alist versus Hash-table, Loïc Faure-Lacroix, 2013/11/12
- Re: [Chicken-users] Alist versus Hash-table, John Cowan, 2013/11/12
- Re: [Chicken-users] Alist versus Hash-table, Peter Bex, 2013/11/13