Short about 'sort'

[Ajschylos]

Hello again,

my progress in Lisp is continuing mainly thanks to your help. Thanks a lot.

Now there is small question.

I want to sort a list of following shape:
((a1 x1 (something1)) (a2 x2 (something2)) ... (an xn (something)))

using predicate (< ai aj) for any i, j.

I did it following way:

Code: Select all

(sort '(--- my list ---) #'(lambda (x y) (< (car x) (car y))))

than I found much shorter way:

Code: Select all

(sort '(--- my list ---) #'< :key 'car)

Natural question arises:
Are these two ways identical (according to 'EVAL of course' , which is 'more functional''?

The answer is important for me, because I still do not know how complicated will be the structure in my project, so probably I would like to write " < " relation myself.

Best regards, A.

[Harleqin]

I believe that the two are identical, two ways to describe the same operation. I think that you can regard the second as a shorthand for the first, and I find it more convenient.

[Ramarren]

The second I think is more idiomatic. Just note that SORT is destructive, and destroying quoted literals is not usually a good idea.

[skypher]

The answer is important for me, because I still do not know how complicated will be the structure in my project, so probably I would like to write " < " relation myself.

Specifying a KEY is absolutely the right thing to do here.

Should you find yourself in need of a custom test later then just switch over to a TEST clause (or add it if the KEY still applies).

[Ajschylos]

Ramarren, I am not sure that I understand You well, as I suppose, sort might destroy the sorted entity, not the relation predicate expressed in lambda form, am I right?

[Ramarren]

Ramarren, I am not sure that I understand You well, as I suppose, sort might destroy the sorted entity, not the relation predicate expressed in lambda form, am I right?

Yes, I was referring to your examples, where you have:

Code: Select all

'(--- my list ---)

Which is literal and constant list, and destroying it might in principle cause memory violation, although I don't think that any implementation actually puts them into read-only memory. But it might cause the program to act unpredictably. I once made such a mistake, though not with sort, but some other destructive function, and was wondering why the function only worked the first time it was called.

[findinglisp]

Natural question arises:
Are these two ways identical (according to 'EVAL of course' , which is 'more functional''?

The answer is important for me, because I still do not know how complicated will be the structure in my project, so probably I would like to write " < " relation myself.

Yes, these are two different ways of doing the same thing. I would choose the second, myself. As people said, it's more idiomatic. In general, it makes it obvious that you're sorting things using #'< as the predicate and that you're comparing the CAR of the items. The LAMBDA performs the same operation but generally includes more syntactic "goop" that tends to obscure the meaning. While it generally shouldn't concern you, there may be slight efficiencies in using the LAMBDA form over the version using :KEY--there are probably a couple of separate FUNCALLs to each of the predicate and the :KEY function in the :KEY version, one of which probably goes away with the LAMBDA where the CAR can be open-coded. In all but an extreme inner-loop, I wouldn't worry about that, though.

[fadrian]

Yes, the second code snippet is more idiomatic. However, if performance is critical, the first may be faster. If performance is an issue, profile both methods in situ and see which one is faster.

[Harleqin]

Yes, the second code snippet is more idiomatic. However, if performance is critical, the first may be faster. If performance is an issue, profile both methods in situ and see which one is faster.

I don't want to advise against profiling, but I see no reason to suspect that the first could be any faster. I would rather expect both to produce almost exactly the same machine instructions.

[findinglisp]

Yes, the second code snippet is more idiomatic. However, if performance is critical, the first may be faster. If performance is an issue, profile both methods in situ and see which one is faster.

I don't want to advise against profiling, but I see no reason to suspect that the first could be any faster. I would rather expect both to produce almost exactly the same machine instructions.

It depends how the compiler optimizes FUNCALLs in this instance. With the CAR separated out into the :KEY parameter, the default behavior will be for SORT to implement two FUNCALLs (one to call the :KEY parameter, and the other to call the LAMBDA with the result). With the larger LAMBDA form and no :KEY form, SORT will FUNCALL the LAMBDA, but then the CAR can be open-coded into the LAMBDA form for a most-efficient call sequence. Every time something goes through FUNCALL, the default behavior is that it's late-bound and very dynamic. That's an efficiency hit. And two efficiency hits is worse than one efficiency hit. When you splat CAR right into the middle of the LAMBDA, the compiler can recognize that it's a primitive function and inline the call completely (it ceases to be a function call at all and just becomes direct machine instructions that implement CAR. It's therefore more efficient. A good compiler might be able to generate fairly equivalent code by proving to itself that they are essentially functionally equivalent and making the call to CAR more efficient, but it takes more work, and you'll be relying on a very good compiler to essentially inline a late-bound, dynamic call site.

As I said, however, I would still use :KEY unless you found that a particular inner loop was a problem to your overall performance, and that through profiling rather than hunch and guesswork. Micro-optimization like this is better left for once the code is done and you have measured it and know that you have a performance problem, and even in that case, you're better off trying to figure out whether you can eliminate the call to SORT completely.