This page is part of the web mail archives of SRFI 44 from before July 7th, 2015. The new archives for SRFI 44 contain all messages, not just those from before July 7th, 2015.
bear wrote:
>>> (*-get-n dict num)
>>> (*-get-n-deleting! dict num)
> scgmille@xxxxxxxxxxxxxxxxxx wrote:
>> Trivially defined with enumeration.
> And with the same problem. On a lot of dictionaries, if I go in
> knowing I want the first N elements, I can get them at one swell foop
> and not waste time traversing the structure again and again for each
> one.
Enumeration isn't quite that bad. The smart way to do it is to traverse
the collection only once, with a filter function that halts the
enumeration as soon as it gets what it needs. Pseudocode:
(cfold f (cons n '()) dict)
where n is the number to fetch and f is
(lambda (nr datum)
(let [(n (car nr)) (result (cdr nr))]
(cond [(= n 0)
(<halt enumeration and return (reverse l)>)]
[(<match filter>)
(cons (1- n) (cons datum result))]
[else nr])))
This will return the elements in O(N) time, which isn't horrible.
However, it's also far from the best possible way to do it. For a
typical tree-based dictionary, you can do it in O((lg N) + K) time:
Finding the first element takes O(lg N), and traversing the structure to
get all K elements takes O(K) time.
There's a big difference between those performance characteristics.
Unless K is very large (close to N), it's effectively O(lg N) for the
"native" approach vs O(N) for the filtering enumeration.
That's how it works for element fetching, anyway. For consecutive
deletions, it's a bit more complicated. Unless the enumeration is
stable, consecutive deletions are O(N-squared), because you need to
enumerate the whole thing once for each iteration. A sophisticated
native function may still be able to do it in O(lg N) time.
This is why I complained that the SRFI didn't take performance into
consideration. Sure, it's a bad idea to attempt construction-time
optimizations too early in the design process. However, these are not
construction-time optimization. They're significant algorithm choices,
and they make a huge difference. In the worst case, it degrades
performance from O(lg N) to O(N-squared).
That kind of major algorithmic degradation *is* an appropriate
consideration for a design doc.
Tangent: In the example above, I used the traditional argument
convention for higher-order functions: (proc f seed collections ...).
One of the thing that annoys me about SRFI-44 is that it abandons good
conventions like these. Collection-fold permits an arbitrary number of
seeds but only one collection. That gives you something useless (if you
want multiple seeds, use a list like I did) while taking away something
useful (folding multiple collections).
Tangent off the tangent: Why the heck did SRFI-1 define the folding
function to accept the seed argument *last*? There's only one seed but
many lists, which naturally suggests a (f seed . data) signature for
folding functions that can work on any number of lists. Instead, it
specifies (f datum0 datum1 ... seed). Why?!
> Failure to provide a name for this function practically demands an
> implementation that sucks, which will then be applied to all
> dictionaries, whether the implementation of this function for that
> dictionary had to suck or not.
OK, I guess it's your turn to be hostile!
> My API allows efficient implementations. The one proposed in the SRFI
> does not. Because of that, they are not even remotely similar. Yes,
> you could use the SRFI API to provide whacking slow versions of most
> of the functionality. But every coder who has to live with them is
> going to hate them, either because they will waste CPU time that does
> not have to be wasted, or because redefining R5RS functions won't play
> nice with the existing code and module system, or both.
I generally agree, but with one reservation: While there are good
reasons for the PLT module system to work that way, it's still more
cumbersome than it needs to be. I've been discussing this on the PLT
mailing list, and I hope to develop some methods to ease the pain a bit.
I still think gratuitous incompatibilities are a bad idea, but it
shouldn't be so hard to use well-designed extensions to existing
bindings.
--
Bradd W. Szonye
http://www.szonye.com/bradd