Suppose there is a hash table *sessions* each entry
of which is an array. Is the following form right way
to sort all such arrays ?
(loop for ss being the hash-value of *sessions*
do (setq ss (sort ss :key #'session-start)
Before this form being executed each entry in hash table
already contains filled array. So there are no cases when
hash value could be nil.
WITH-HASH-TABLE-ITERATOR returns so called "generator macro".
If the latter returns three values could the last one be used
as accessor ? I doubt this. Is it true to say that only way
to change the value (not the contents) of a hash entry is to
use setf on gethash ?
--
Vladimir Zolotykh
In article <·················@eurocom.od.ua>,
Vladimir Zolotykh <······@eurocom.od.ua> wrote:
>Suppose there is a hash table *sessions* each entry
>of which is an array. Is the following form right way
>to sort all such arrays ?
>
>(loop for ss being the hash-value of *sessions*
> do (setq ss (sort ss :key #'session-start)
You don't need the SETQ, since it's being executed for side-effect, not
value. But any decent compiler will optimize away the SETQ, since the
variable is never accessed before being reset by the next iteration.
It wouldn't work if the values were lists, because SORT doesn't guarantee
that the same cons will be the head of the resulting list (which is why you
typically need the SETQ in other contexts), but in the case of an array it
sorts the contents in place and should work.
>Before this form being executed each entry in hash table
>already contains filled array. So there are no cases when
>hash value could be nil.
And even if they were, it would be OK, since (sort nil) => NIL.
>WITH-HASH-TABLE-ITERATOR returns so called "generator macro".
>If the latter returns three values could the last one be used
>as accessor ? I doubt this. Is it true to say that only way
No, the last value is the current contents of the hash table entry.
E.g. in the above hash table, the third value would be an array.
>to change the value (not the contents) of a hash entry is to
>use setf on gethash ?
Yes.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin wrote:
> It wouldn't work if the values were lists, because SORT doesn't guarantee
> that the same cons will be the head of the resulting list (which is why you
> typically need the SETQ in other contexts), but in the case of an array it
> sorts the contents in place and should work.
No, SORT does not guarantee that sorting an array reuses the array.
That may be how it's implemented, but it is not required to be
implemented that way. From the CLHS:
"If sequence is a vector, the result might or might not be simple,
and might or might not be identical to sequence."
Paul
Barry Margolin
> It wouldn't work if the values were lists, because SORT doesn't guarantee
> that the same cons will be the head of the resulting list (which is why you
> typically need the SETQ in other contexts), but in the case of an array it
> sorts the contents in place and should work.
Paul Dietz
> No, SORT does not guarantee that sorting an array reuses the array.
> That may be how it's implemented, but it is not required to be
> implemented that way. From the CLHS:
>
> "If sequence is a vector, the result might or might not be simple,
> and might or might not be identical to sequence."
That quote doesn't support your claim.
[CLHS 17.3 The Sequences Dictionary] on sort:
The sorting operation can be destructive in all cases. In the case of
a vector argument, this is accomplished by permuting the elements in
place. In the case of a list, the list is destructively reordered in
the same manner as for nreverse.
So the Standard indeed guarantees that a vector is sorted 'in place'.
--
"I believe in the horse. The automobile is a passing phenomenon."
-- Kaiser Wilhelm II. (1859-1941)
From: Tim Bradshaw
Subject: Re: WITH-HASH-TABLE-ITERATOR and (SETF GETHASH)
Date:
Message-ID: <ey3vg4tzxd7.fsf@cley.com>
* Wolfhard Bu wrote:
> [CLHS 17.3 The Sequences Dictionary] on sort:
> The sorting operation can be destructive in all cases. In the case of
> a vector argument, this is accomplished by permuting the elements in
> place. In the case of a list, the list is destructively reordered in
> the same manner as for nreverse.
*Can* be destructive does not to me imply `must be' destructive, or in
particular does not imply that whatever is returned is the identical
object. I'd be kind of surprised by an implementation which didn't
return an identical object when sorting a vector, but it seems to me
that that is allowed by the spec.
--tim
In article <···············@cley.com>, Tim Bradshaw <···@cley.com> wrote:
>* Wolfhard Bu wrote:
>
>> [CLHS 17.3 The Sequences Dictionary] on sort:
>> The sorting operation can be destructive in all cases. In the case of
>> a vector argument, this is accomplished by permuting the elements in
>> place. In the case of a list, the list is destructively reordered in
>> the same manner as for nreverse.
>
>*Can* be destructive does not to me imply `must be' destructive, or in
>particular does not imply that whatever is returned is the identical
>object. I'd be kind of surprised by an implementation which didn't
>return an identical object when sorting a vector, but it seems to me
>that that is allowed by the spec.
Looks like you're right. Can't think of why we did it that way, though.
Are there good sorting algorithms that work better if you don't sort in
place? Maybe we just wanted to leave it open in case there were.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin <······@genuity.net> wrote in message news:<·················@paloalto-snr1.gtei.net>...
[why sorting vectors is not required to be destructive]
> Are there good sorting algorithms that work better if you don't sort in
> place? Maybe we just wanted to leave it open in case there were.
At the very least, sorting literals destructively might
run into problems.
Another case I can think of is sorting a vector that is
very fragmented in virtual memory, but that's very
far-fetched.
In terms of algorithms, an obvious answer is mergesort,
but I guess there is a clever way of doing it in place.
---Vassil.
In article <····························@posting.google.com>,
Vassil Nikolov <··········@poboxes.com> wrote:
>Barry Margolin <······@genuity.net> wrote in message
>news:<·················@paloalto-snr1.gtei.net>...
>[why sorting vectors is not required to be destructive]
>> Are there good sorting algorithms that work better if you don't sort in
>> place? Maybe we just wanted to leave it open in case there were.
>
>At the very least, sorting literals destructively might
>run into problems.
That means that you're not permitted to pass a literal to SORT in the first
place, since it's allowed to be destructive.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin <······@genuity.net> writes:
> In article <····························@posting.google.com>,
> Vassil Nikolov <··········@poboxes.com> wrote:
[...]
> >At the very least, sorting literals destructively might
> >run into problems.
>
> That means that you're not permitted to pass a literal to SORT in the first
> place, since it's allowed to be destructive.
Yes, of course; I realized too late I wrote that poorly. Let me
write a better version.
Let's consider a situation where destructive modification of a literal
does fail. If the implementation is mandated to sort vectors in
place, then sorting a literal will be forced to fail in such a
situation. When sorting is allowed to copy, however, then it is at
least possible to produce an implementation which avoids that failure.
I think that it is good not to mandate destructive behavior, as it is
not mandated for NREVERSE, for example. This makes `quasi-functional'
implementations thinkable (where destructive operations behave as
their non-destructive counterparts as much as possible); it is another
question, of course, whether they are justifiable.
And obviously the number of worms in this can is greater than one:
(1) I don't know if it would have been a good idea to have SORT and
NSORT separately.
(2) I also don't know how willing the hypothetical implementor would
be to copy vectors (what is the right way to copy a displaced
vector?).
(I use `mandate X' in the sense `specify that X must be done' which I
hope doesn't sound too unnatural to the native ear.)
---Vassil.
In article <···············@panix1.panix.com>,
Vassil Nikolov <··········@poboxes.com> wrote:
>Barry Margolin <······@genuity.net> writes:
>
>> In article <····························@posting.google.com>,
>> Vassil Nikolov <··········@poboxes.com> wrote:
>[...]
>> >At the very least, sorting literals destructively might
>> >run into problems.
>>
>> That means that you're not permitted to pass a literal to SORT in the first
>> place, since it's allowed to be destructive.
>
>Yes, of course; I realized too late I wrote that poorly. Let me
>write a better version.
>
>Let's consider a situation where destructive modification of a literal
>does fail. If the implementation is mandated to sort vectors in
>place, then sorting a literal will be forced to fail in such a
>situation. When sorting is allowed to copy, however, then it is at
>least possible to produce an implementation which avoids that failure.
But a portable application can't take advantage of that, unless there's a
way to query the implementation to find out whether it copies or not.
BTW, destructive modification of literals is not required to fail. The
standard says that the consequences are undefined. An implementation is
permitted to allow it, but a portable application can't depend on it.
Since you're talking about taking advantage of implementation-dependent
behavior (i.e. whether SORT copies), you could just as easily take
advantage of this.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Tim Bradshaw
Subject: Re: WITH-HASH-TABLE-ITERATOR and (SETF GETHASH)
Date:
Message-ID: <ey3lm5pyqz6.fsf@cley.com>
* Barry Margolin wrote:
> Looks like you're right. Can't think of why we did it that way, though.
> Are there good sorting algorithms that work better if you don't sort in
> place? Maybe we just wanted to leave it open in case there were.
It does seem weird to me. I wondered if it was because it means that
things are kind of consistent - for instance if you sort a list you
need to be interested in what SORT returns (don't you? I presume it is
allowed to leave the former first cons half way down the list or
something and might actually do that quite often), so there might as
well be that restriction for vectors.
I tried to think of some weird VM-efficiency induced reason for not
sorting in place but I don't think I can. I suppose it's *possible*
that if you only do reads from the source array and writes to the
target array then you might get some cache/bandwidth win with some
fancy modern processor (but this seems implausible to me).
--tim
In article <···············@cley.com>, Tim Bradshaw <···@cley.com> wrote:
>* Barry Margolin wrote:
>
>> Looks like you're right. Can't think of why we did it that way, though.
>> Are there good sorting algorithms that work better if you don't sort in
>> place? Maybe we just wanted to leave it open in case there were.
>
>It does seem weird to me. I wondered if it was because it means that
>things are kind of consistent - for instance if you sort a list you
>need to be interested in what SORT returns (don't you? I presume it is
>allowed to leave the former first cons half way down the list or
>something and might actually do that quite often), so there might as
>well be that restriction for vectors.
Yes, it looks like consistency was probably the reason. All of the
destructive sequence functions are similarly unspecific about their
behavior on vectors. I suppose this allows a kind of generic programming:
if you use sequence functions, you should program the same way whether
you're using lists or vectors.
But in retrospect, I think we probably should have required the obvious,
in-place destructions for vectors. Programmers often use arrays because
the performance implications are pretty easy to deduce: element access is
O(1), and deleting element N should be O(length-N) (because it only needs
to copy the elements past it), not O(length) as it would be if it copied
the entire array.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Tim Bradshaw
Subject: Re: WITH-HASH-TABLE-ITERATOR and (SETF GETHASH)
Date:
Message-ID: <ey3wup83bh2.fsf@cley.com>
* Barry Margolin wrote:
> But in retrospect, I think we probably should have required the obvious,
> in-place destructions for vectors. Programmers often use arrays because
> the performance implications are pretty easy to deduce: element access is
> O(1), and deleting element N should be O(length-N) (because it only needs
> to copy the elements past it), not O(length) as it would be if it copied
> the entire array.
Yes, I agree with this - I think it's a glitch in the spec. There are
all sorts of things that that one would like to work like sorting an
array which is displaced to another array, but probably technically
you need to copy back the sorted array (or, actually, test it's EQ and
if not copy it, which is much more efficient assuming an in-place sort
but still painful in terms of code to write).
--tim
·····@gmx.net (Wolfhard Bu�) writes:
> Paul Dietz
>> "If sequence is a vector, the result might or might not be simple,
>> and might or might not be identical to sequence."
>
> That quote doesn't support your claim.
>
> [CLHS 17.3 The Sequences Dictionary] on sort:
> The sorting operation can be destructive in all cases. In the case of
> a vector argument, this is accomplished by permuting the elements in
> place. In the case of a list, the list is destructively reordered in
> the same manner as for nreverse.
>
> So the Standard indeed guarantees that a vector is sorted 'in place'.
I was surprised when I read Barry's original post, and went to look
at CLHS myself.
Paul's quote says "the result [...] might not be identical to
sequence"
Wolfhard's says "The sorting operation can be destructive". It
doesn't say "must be", and in the light of the sentence that Paul
quoted I would be leary of depending on it to be. I would probably
read the rest of that paragraph as describing the manner in which it
is destructive _if_ it is indeed destructive.
-dan
--
http://ww.telent.net/cliki/ - Link farm for free CL-on-Unix resources