Adding element to a sorted list

Discussion of Common Lisp
Post Reply
ykm
Posts: 5
Joined: Tue Sep 18, 2012 11:52 pm

Adding element to a sorted list

Post by ykm » Wed Oct 17, 2012 11:49 am

Hi,
I am trying to develop a function which does as mentioned in the subject line i.e adding an element to a list while maintaining the sort order. The following is what I have managed:

Code: Select all

(defun sort-push(lst n &key (test #'<) (key #'identity))
   (labels ((rec (lst n acc)
	      (if (null lst)
		  (reverse (cons n acc))
		  (if (funcall test (funcall key n) (funcall key (car lst)))
		      (append (reverse (cons n acc)) lst)
		      (rec (cdr lst) n (cons (car lst) acc))))))
     (rec lst n ())))

(sort-push '((1 . 2) (5 . 6))  (3 . 4) :key #'cdr)
((1 . 2) (3 . 4) (5 . 6))
This function is resulting into what is being expected. However, it appears something isn't right about it. Can you point out the drawbacks of this function? Its taking a long time to push an element into a huge list of cons. Also, please point out if this functionality has been already implemented into the current list implementations.

Regards,
ykm.

Konfusius
Posts: 62
Joined: Fri Jun 10, 2011 6:38 am

Re: Adding element to a sorted list

Post by Konfusius » Wed Oct 17, 2012 1:04 pm

Code: Select all

(defun sorted-push (lst n &key (test #'<) (key #'identity))
  (if (null lst)
	(cons n nil)
	(if (funcall test (funcall key n) (funcall key (car lst)))
	  (cons n lst)
	  (cons (car lst) (sorted-push (cdr lst) n :test test :key key)))))

(sorted-push '((1 . 2) (5 . 6)) '(3 . 4) :key #'cdr)

Goheeca
Posts: 271
Joined: Thu May 10, 2012 12:54 pm
Contact:

Re: Adding element to a sorted list

Post by Goheeca » Wed Oct 17, 2012 1:04 pm

Your function is O(N) if I'm not mistaken. I've created this:

Code: Select all

(defun sort-push (lst n &key (test #'<) (key #'identity))
  (let ((mid (floor (/ (length lst) 2))))
    (flet ((split (lst where) (values (subseq lst 0 where) (subseq lst where)))
           (comp (a b) (funcall test (funcall key a) (funcall key b))))
      (cond ((null lst) (list n))
            ((comp n (nth mid lst)) (multiple-value-bind (left right) (split lst mid)
                                      (append (sort-push left n :test test :key key) right)))
            ((= 1 (length lst)) (list (nth mid lst) n))
            (t (multiple-value-bind (left right) (split lst mid)
                 (append left (sort-push right n :test test :key key))))))))
it's a draft, thus it can be improved probably (especially the (= 1 (length lst)) part). It has O(log N).
cl-2dsyntax is my attempt to create a Python-like reader. My mirror of CLHS (and the dark themed version). Temporary mirrors of aferomentioned: CLHS and a dark version.

Goheeca
Posts: 271
Joined: Thu May 10, 2012 12:54 pm
Contact:

Re: Adding element to a sorted list

Post by Goheeca » Wed Oct 17, 2012 1:30 pm

But it's not good for lists because of the inefficiency of subseq on lists, for vectors (the function must be adapted) it would be reasonable.
cl-2dsyntax is my attempt to create a Python-like reader. My mirror of CLHS (and the dark themed version). Temporary mirrors of aferomentioned: CLHS and a dark version.

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Adding element to a sorted list

Post by edgar-rft » Wed Oct 17, 2012 1:34 pm

Why not just simply writing:

Code: Select all

(defun sort-push (lst n &key (test #'<) key)
  (sort (cons n lst) test :key key))
The built-in SORT is probably faster than traversing the list.

- edgar

sylwester
Posts: 133
Joined: Mon Jul 11, 2011 2:53 pm

Re: Adding element to a sorted list

Post by sylwester » Wed Oct 17, 2012 3:47 pm

Konfusius's is the fastes judging by my test which adds 1000 random numbers to an empty list.
WIth a litte change to the tail recusive version it matches it:

Code: Select all

(defun sort-push-iter(lst n &key (test #'<) (key #'identity))
   (labels ((rec (lst n acc)
         (if (null lst)
        (nreverse (cons n acc))
        (if (funcall test (funcall key n) (funcall key (car lst)))
            (nconc (nreverse (cons n acc)) lst)
            (rec (cdr lst) n (cons (car lst) acc))))))
     (rec lst n ())))
Using built in sort was the worst with my tests, but I liked the idea.
In the spirit of Goheeca's idea and my test with random numbers I guess you get the best result if instead of maintaining a list actually maintained a binary tree and when finished inserting converted it to a sorted list :)
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p

ykm
Posts: 5
Joined: Tue Sep 18, 2012 11:52 pm

Re: Adding element to a sorted list

Post by ykm » Wed Oct 17, 2012 11:54 pm

Hi,
Thanks to all of you for your responses. One thing I forgot to mention in the original question is that I am using this function in a loop and using the built-in sort after adding each element(as I needed the sorted list for the next iteration as well) sounded inefficient to me.

Gohecca: Yes, indeed, its complexity if O(n), with the worst case requiring computations until the length of the list. Though, it appears in your code, you have incorporated quick sort into it. Will look into that.

Edgar: I had used it, but it wasn't upto the mark hence the function.

Regards,
ykm.

Goheeca
Posts: 271
Joined: Thu May 10, 2012 12:54 pm
Contact:

Re: Adding element to a sorted list

Post by Goheeca » Thu Oct 18, 2012 6:45 am

It's not a quicksort but the binary search thorough it's not good on linked lists.
cl-2dsyntax is my attempt to create a Python-like reader. My mirror of CLHS (and the dark themed version). Temporary mirrors of aferomentioned: CLHS and a dark version.

sylwester
Posts: 133
Joined: Mon Jul 11, 2011 2:53 pm

Re: Adding element to a sorted list

Post by sylwester » Thu Oct 18, 2012 2:59 pm

ykm wrote:Hi,
Thanks to all of you for your responses. One thing I forgot to mention in the original question is that I am using this function in a loop and using the built-in sort after adding each element(as I needed the sorted list for the next iteration as well) sounded inefficient to me.
So you add to a list, then sort it because you need to use the list in each iteration. How do you use the sorted list/ WHat do you access?
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p

Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Adding element to a sorted list

Post by Paul » Fri Oct 19, 2012 6:15 am

Goheeca wrote:it's a draft, thus it can be improved probably (especially the (= 1 (length lst)) part). It has O(log N).
FWIW, for (= 1 (length list)) do (null (cdr list)) -- or reverse that and the T clause and drop the NULL.

Does this thing have to be nondestructive? I want to write something like

Code: Select all

(defun insert-in-ordered-list (n list &key (test #'<) (key #'identity))
  (loop with val = (funcall key n) for p = nil then x as x on list
     while (funcall test (funcall key (car x)) val)
     finally (return (if p
			 (progn (setf (cdr p) (cons n (cdr p))) list)
			 (cons n list)))))
(Note: I put the arguments in the right order)

Post Reply