vl-sort help

[zph]

Good day!

Below is an excerpt of code:

(princ "\n qList1: ")(princ qList)
(setq qList (vl-sort qList (function (lambda (x y) (< (car x) (car y))))))
(princ "\n qList2: ")(princ qList)

And below is the what is returned:

 qList1: ((NEW-TEST-VAL-D . 0) (NEW-TEST-VAL-D . 0) (NEW-TEST-VAL-C . 0) (NEW-TEST-VAL-B . 0) (NEW-TEST-VAL-A . 0))
 qList2: ((NEW-TEST-VAL-A . 0) (NEW-TEST-VAL-B . 0) (NEW-TEST-VAL-C . 0) (NEW-TEST-VAL-D . 0) (NEW-TEST-VAL-D . 0))

Why doesn't this instance of vl-sort remove the duplicate dotted pair (highlighted red)?  What am I missing?

Thanks!

~Z

[john.uhden]

How is that any different from

(vl-sort l f)

?

[marko_ribar]

Hi John,

my function doesn't remove duplicates as vl-sort... And BTW. I've changed the code as previously one posted had lacks - could go into infinite loop... Notice that you must specify correct function as argument which will sort at least one element among others in order to make it do what should correctly... Of course it doesn't matter if function is defined as anonymous lambda or just symbol, but it should be correct one - look into commented 2 lines at the end of the code...

(defun sort ( l f / fun out )
  (defun fun ( l f / k kk z )
    (if l
      (progn
        (setq k -1)
        (foreach a l
          (if (null kk)
            (progn
              (setq k (1+ k) z nil)
              (if (vl-every '(lambda ( x ) (apply f (list a x))) (vl-remove nil (mapcar '(lambda ( x ) (if (null z) (setq z 0) (setq z (1+ z))) (if (/= z k) x)) l)))
                (setq out (cons a out) kk k)
              )
            )
          )
        )
        (setq z nil)
        (if kk
          (fun (vl-remove nil (mapcar '(lambda ( x ) (if (null z) (setq z 0) (setq z (1+ z))) (if (/= z kk) x)) l)) f)
        )
      )
    )
    (reverse out)
  )
  (fun l f)
)

;;; (sort '(2 4 1 3 5 1) '<) => nil
;;; (sort '(2 4 1 3 5 1) '<=) => (1 1 2 3 4 5)

;;; (vl-sort '(2 4 1 3 5 1) '<) => (1 2 3 4 5)
;;; (vl-sort '(2 4 1 3 5 1) '<=) => (1 2 3 4 5)

Regards, M.R.

[john.uhden]

Very interesting.  Strings may offer a challenge.

Command: !x ("a" "d" "b" "a" "c" "d")

Command: (sort x '>)
nil

Command: (sort x '<)
nil

Command: (sort x '<=)
("a" "a" "b" "c" "d" "d")

Command: (sort x '>=)
("d" "d" "c" "b" "a" "a")

But if retaining all members of a list, then >= is the same as > anyway.

[john.uhden]

This seems to work (retaining duplicates):

(setq a '(4 5 1 3 2 4 6 5))
(4 5 1 3 2 4 6 5)

Command: (setq indices (vl-sort-i a '>))
(6 7 1 5 0 3 4 2)

Command: (mapcar '(lambda (x)(nth x a)) indices)
(6 5 5 4 4 3 2 1)

or, more compactly:
Command: (mapcar '(lambda (x)(nth x a)) (vl-sort-i a '>))
(6 5 5 4 4 3 2 1)

So...
(defun sort (lst fun)
 (mapcar '(lambda (x)(nth x lst)) (vl-sort-i lst fun))
)

[dbroad]

Or slightly optimized:

(defun sort (lst fun)
  (mapcar (function (lambda(n) (nth n lst))) (vl-sort-i lst fun))
  )

and if you did want to remove duplicates from the list, either

;remove duplicates from a sorted list
(defun nodup(lst)
  (if (null lst) nil
;;change the following test to refine equality using
;;equal with fuzz, eq, or =
    (if (equal (car lst)(cadr lst))
      (nodup (cdr lst))
      (cons (car lst)(nodup (cdr lst))))))

or 

;;efun is a non-quoted equality function.
(defun nodup2 (lst efun)
  (if (null lst) nil
    (if (efun (car lst)(cadr lst))
      (nodup (cdr lst))
      (cons (car lst)(nodup (cdr lst))))))

[_gile]

Isn't it similar to this (reply #11)?

[dbroad]

Yes, if you mean post #12 by you.  I admit that I didn't read through the entire thread before posting.

[john.uhden]

I guess I don't know what you mean by optimized.

Is the function function supposed to be faster than quoting?

My time tests showed that they are equal.

[marko_ribar]

(function) function is only faster inside routine when lisp is compiled...

And this :

Command: (mapcar '(lambda (x)(nth x a)) (vl-sort-i a '>))
(6 5 5 4 4 3 2 1)

Is by my observation somewhat wrong ... 5>5 is never true and also 4>4... Therefore only my sub is correct - both (vl-sort) and (vl-sort-i) are wrong... Simply you can't assume that 5>5 so that you could sort those things, at least in computer terminology... 5>=5 is something else - that's true...

[john.uhden]

That's an interesting way of looking at it.  But like a race, if one 5 is no faster than the other 5, then there is a tie; one of them doesn't just disappear.

Or maybe it is as my brother tried to teach me...

1 + 1 = 3 (for large values of 1)

BTW, thanks for the explanation about function.

[ActivistInvestor]

Your function is no more-correct than vl-sort and vl-sort-i.

A proper sorting function requires items that compare as EQUAL to retain the same relative order after the sort is complete.

In order to do that, a comparison cannot be "true" or "false".  And, in most other "grown-up" programming languages, where proper sorting is implemented, the 'comparer' function must not return a boolean, it must return an integer, where:

  -1    - the first argument is "less than" the second argument.

   0    - the two arguments are equal (and therefore, retain the same relative order).

   1    - the first argument is "greater than" the second argument.

Your claims are just more fertilizer.

---

@marko_ribar wrote:

(function) function is only faster inside routine when lisp is compiled...

And this :

Command: (mapcar '(lambda (x)(nth x a)) (vl-sort-i a '>))
(6 5 5 4 4 3 2 1)

Is by my observation somewhat wrong ... 5>5 is never true and also 4>4... Therefore only my sub is correct - both (vl-sort) and (vl-sort-i) are wrong... Simply you can't assume that 5>5 so that you could sort those things, at least in computer terminology... 5>=5 is something else - that's true...

---

[_gile]

---

@marko_ribar wrote:

(function) function is only faster inside routine when lisp is compiled...

And this :

Command: (mapcar '(lambda (x)(nth x a)) (vl-sort-i a '>))
(6 5 5 4 4 3 2 1)

Is by my observation somewhat wrong ... 5>5 is never true and also 4>4... Therefore only my sub is correct - both (vl-sort) and (vl-sort-i) are wrong... Simply you can't assume that 5>5 so that you could sort those things, at least in computer terminology... 5>=5 is something else - that's true...

---

I do not think it's wrong.

This is how sorting with a some predicate works:

(if (predicate x y)
  (x y)
  (y x)
)

Now, if we replace both x and y by 5,

with >= as predicate the condition is true so you put 5 (x) before 5 (y).

with > as predicate the condition is false so you put 5 (y) before 5 (x).

[john.uhden]

So is it a tie, or should the other 5 be disqualified?

Maybe that is why the confusion as to why vl-sort sometimes removes duplicates and sometimes not.

Both Marko's and my attempts were to retain the duplicates and I think they do that.

[_gile]

I always thought that vl-sort was poorly implemented.
First, the order of the arguments: unlike all the other higher order functions (apply, mapcar, vl-remove-if, ...) here, the list is the first argument, the function the second.
Then there is this thing that makes the "duplicate elements may be eliminated from the list" and this continues to be talked about today.

From the little I know, sorting algorithms may keep or not keep the original order of items considered equal, but by no means remove duplicates.

Although I can understand @ActivistInvestor's explanations about comparison functions that offer three return value options and the use of eq (or equivalent) to evaluate equality, all of this remains unclear from the side of AutoLISP where the comparison functions are predicates that return T or nil.

So, in my opinion, vl-sort should have arguments in reverse order and never eliminate duplicate items.

[john.uhden]

Alrighty then...

(defun sort (fun list)
 (mapcar (function (lambda (n)(nth n list))) (vl-sort-i list fun))
)

The lurkers should note that I used list as an argument, which is okay as long as I don't try to use the list function within the function since arguments are treated as local.  IOW, outside this function the list function remains an AutoCAD defined function, an SUBR.

Command: (sort '> '("fie" "fo" "fum" "fee" "fie" "fo" "fum"))
("fum" "fum" "fo" "fo" "fie" "fie" "fee")

Command: (sort '< '("fie" "fo" "fum" "fee" "fie" "fo" "fum"))
("fee" "fie" "fie" "fo" "fo" "fum" "fum")

[ActivistInvestor]

What if the function argument (or any function it calls) uses the (list) function?

Your sort function serves as a very good example of why dynamic-scoping is so perilous.

---

@john.uhden wrote:

Alrighty then...

(defun sort (fun list)
 (mapcar (function (lambda (n)(nth n list))) (vl-sort-i list fun))
)

The lurkers should note that I used list as an argument, which is okay as long as I don't try to use the list function within the function since arguments are treated as local.  IOW, outside this function the list function remains an AutoCAD defined function, an SUBR.

Command: (sort '> '("fie" "fo" "fum" "fee" "fie" "fo" "fum"))
("fum" "fum" "fo" "fo" "fie" "fie" "fee")

Command: (sort '< '("fie" "fo" "fum" "fee" "fie" "fo" "fum"))
("fee" "fie" "fie" "fo" "fo" "fum" "fum")

---

[hak_vz]

From my experience vl-sort has some serious flaws. I rarely use it for sorting strings, bigger problem is that it usually fails sorting point lists , because some serious issues when dealing with real numbers. At the end you take values from the point list, multiply them by some power of 10 and convert to nearest integer, put them back into the point list and sort them by using integers 🙂 It could be optimized, but final result is at least correct. 

;LeeMac
(defun remove_nth ( lst n / lstn )
    (setq n (1+ n))
    (foreach x lst (if (/= 0 (setq n (1- n)))
    (setq lstn (cons x lstn))))
    (reverse lstn)
)

(defun create_vector (n val / r ) (repeat n (setq r (cons val r))) r)

(defun sort_points (ptlist / s1 s2 i min_n n next sorted next)
    (setq s1 (mapcar 'car ptlist)
          s2 (create_vector (length ptlist) 10000)
          s1 (mapcar '* s1 s2)
          s2 nil
          s1 (mapcar 'fix s1)
          s1 (mapcar 'list s1 ptlist)
          i 0
          min_n 1e15  
          next nil
          sorted (list)
    )
    (while (> (length s1) 0)
        (repeat (length s1)
            (if (< (car (nth i s1)) min_n)
                (setq min_n (car (nth i s1)) n i next (cdr(nth i s1))))
                (setq i (+ i 1))
            )
        (setq s1 (remove_nth s1 n)
              sorted(append sorted next)
              min_n 1e15
              i 0
        )
    )
    sorted
)

---

---

@_gile wrote:

I always thought that vl-sort was poorly implemented.

.....

From the little I know, sorting algorithms may keep or not keep the original order of items considered equal, but by no means remove duplicates.
.....
So, in my opinion, vl-sort should have arguments in reverse order and never eliminate duplicate items.

---

I agree

[dbroad]

Interesting but I've never found a need to convert real numbers to integers in order to sort effectively. This will only sort points in order left to right and offers no other sorting options.  The problem with building in the sorting function into a sorting algorithm is that it makes it inflexible.  Without comments, it is less maintainable.

[john.uhden]

@ActivistInvestor wrote, "What if the function argument (or any function it calls) uses the (list) function?"

You also quoted me... "The lurkers should note that I used list as an argument, which is okay as long as I don't try to use the list function within the function since arguments are treated as local."  But what do you care.  You seem to approve of errors.

[hak_vz]

Unfortunately I've stumbled to that problem with my cross section tool used in terrain modeling. Section lines would regularly be produced with some points out of order. After two days of debugging and replacing vl-sort everything worked as it should. Maybe there were some other causes for such behavior, but this solution produced adequate result.

Well documented code is a must. But... in a situation when you need a tool because project deadline is near,  you don't have a time to properly comment the code. You create your functions with variations (to sort in what ever way you want), test them on various samples and store in your code library. Some day you may optimize it, but sometime better option is "don't fix what ain't broken". If it serves you many years without producing an error you know it's ok. 

Code given above sorts point list by smaller x value. If you change just "<" with" >", it will sort in the other way. If you replace  (mapcar 'car ptlist) with (mapcar 'cadr ptlist) you've got variants for sorting by y......