neighbor deletion; param ordering; < & <=; fresh lists; cell recycling
shivers@xxxxxx
(21 Jul 2002 03:44 UTC)
|
Re: neighbor deletion; param ordering; < & <=; fresh lists; cell recycling David Feuer (21 Jul 2002 05:48 UTC)
|
cell recycling; reference implementation; param ordering; fresh lists
shivers@xxxxxx
(21 Jul 2002 17:17 UTC)
|
Re: cell recycling; reference implementation; param ordering; fresh lists
Francisco Solsona
(22 Jul 2002 15:14 UTC)
|
***I'm still wondering where the reference implementation is.*** On Sat, 20 Jul 2002 xxxxxx@cc.gatech.edu wrote: > Good question -- it ain't sorting. But it's something you typically do with > sorted data. I considered punting these. But writing them well takes a little > work (especially the iterative destructive list version), and part of the > library game, for me, is that I make an effort and write a thing well, once, > and then everyone can use it. Count it under "manipulation of sorted data," > just like vector binary search. I think you should make it a separate SRFI. It does seem a bit too small for that, but it really doesn't make sense to me to have it in the sorting library. > I think the ordering op should go first. > > Me, too. But the compatibility win outweighs my preference here. > > Also, <= seems much more intuitive than <. > > Me, too. But it busts compatibility with just about *everything* out there, > lisp and Scheme. I don't think it's worth it. Qaere: Do you provide functions with the same _names_ as existing implementations, or just the same interfaces? If the names are not the same, compatibility seems to me to be not such a big deal, as the functions will have to be redefined anyway. It's not much harder to say (define (cl-sort-list list <) (sort-list (lambda (x y) (not (< y x))) list)) than (define (cl-sort-list sort-list) Not quite as easy, but not a big deal if you're going to have compatability definitions anyway. Unless I'm missing some effect this has on the rest of the SRFI... Another little thought: You could provide _both_, with the different versions marked by asterisks or something. That could be a bit confusing though, and even lead to a bit of bloat. > I note that the non-mutating vector sorts are guaranteed to copy the > vector. It would seem potentially very useful to give some indication of > whether the new vector is in fact different from the old vector, to allow > programmers to optimize for generational collectors. > > Heh? The new vector is *guaranteed* to be different from the old vector. > You alter one, the other is unchanged. Guaranteed. What I was thinking was that in functional-style code, if you sort an array, and if the array was in fact already sorted, you get a little win by using the old array rather than the new one (and letting the new one get trashed almost immediately in the first generation) rather than having 2 identical arrays sitting around wasting memory, and missing the opportunity for a first-generation collection. But I'm no expert at GC, so this may not actually be significant. Of course you can always check if the array is sorted first, but that would take more time. > If you really, really need to know that the returned list is fresh, that it > contains no cons cells in common with the input list, you are in a > side-effecting world. Otherwise you would not care about cons-cell identity, > right? So copy the list and then use SORT-LIST!. It would probably run faster > and certainly allocate less "trash" memory than a purely functional sort. > So we might as well let this one slide. I was thinking of this in the "side-effecting world". I was guessing (without any serious thought on the topic) that it could be faster (at least on some implementations) to do a total-copy sort than a copy-then-sort. Don't have a clue if this is really the case. > so there are not going to be any new cells in the answer. Let me add a little > bit of language to the spec to spell this out more (which is mostly taken > from the later appearance of LIST-MERGE!): Alright. You may be able to get away with something really simple like: "The maximum amount of live memory between the call to list-merge! and its completion may be no more than a constant amount more than the amount of live memory immediately before the call to list-merge!". > These procedures use SET-CDR!s to rearrange the cells of the lists into > the final result. As such, they do not allocate any extra cons cells -- > they work "in place." Hence, any cons cell appearing in the result must > have originally appeared in an input. I think that's OK. David