end chapter exercise's doubts...

Discussion of Common Lisp

end chapter exercise's doubts...

Postby megera » Sun Nov 04, 2012 1:05 pm

HI
the exercise says:
"""Define iterative and recursive versions of a function that takes an object x and vector v, and returns a list of all the objects that immediately precede x in v:
> (precedes #\a "abracadabra")
(#\c #\d #\r) """
ok, my solution (iterative mode):

Code: Select all
(defun precedes(car vec)
      (let((lista nil))
        (dotimes (i (length  vec))
          (if (and (equal (aref vec i) car)(> i 0))
             (setf lista (cons (aref vec (- (position car vec :start i) 1)) lista))))
        lista))

online book solution:
Code: Select all
(defun presedes (x v)
            (let (acc (v (concatenate 'vector v))) ;; on book ther's  v1 instead v...;)
               (dotimes (i (length v))
                  (if (and (eql x (svref v i)) (< 0 i))
                   (push (svref v (- i 1)) acc)))
              (remove-duplicates acc)))

First:
probably my solution runs slower then correct solution, isn't it?? becouse my solution sets 'list' for each iteration and lacks "remove-duplicates " that parse the vector...
then, is my solution more inefficient than correct solution? then is always preferable works with latter?
thanks in advance
megera
 
Posts: 30
Joined: Wed Oct 10, 2012 1:34 pm

Re: end chapter exercise's doubts...

Postby Paul » Sun Nov 04, 2012 3:21 pm

No. Yours pointlessly calls POSITION to find something you've already located, but otherwise they're the same (except for REMOVE-DUPLICATES). (PUSH x y) == (SETQ y (CONS x y))
Paul
 
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: end chapter exercise's doubts...

Postby wvxvw » Mon Nov 05, 2012 1:56 am

If you are concerned with efficiency, then the solution in the book probably isn't the most efficient either...

Code: Select all
(defun precedes (element vector)
  (let ((hash (make-hash-table)))
    (do ((i (1- (length vector)) (1- i))
         compare-to result backref)
        ((= i 0) result)
      (setf compare-to (aref vector (1- i)))
      (when (and (eql element (aref vector i))
                 (not (gethash compare-to hash)))
        (setf (gethash compare-to hash) t)
        (if result
            (setf (cdr backref) (list compare-to)
                  backref (cdr backref))
            (setf result (list compare-to)
                  backref result))))))

While the code is longer, it will do it in general faster + it will return the preceding elements in the same order they appeared in the source vector (sans repetitions).
For some reason the exercises which use lists for the purpose they aren't good for are very trendy in Lisp :/ This is certainly a task that benefits from using a hash-map.
wvxvw
 
Posts: 125
Joined: Sat Mar 26, 2011 6:23 am

Re: end chapter exercise's doubts...

Postby stackman » Mon Nov 05, 2012 5:17 am

You can use pushnew instead of push if you don't want duplicates in the result.
stackman
 
Posts: 28
Joined: Sat Oct 06, 2012 5:44 am

Re: end chapter exercise's doubts...

Postby megera » Mon Nov 05, 2012 5:37 am

HI Paul , wvxvw and stackman ...thanks for your support and suggestions!! ;)

Now I have some questions for wvxvw about his syntax's code that are new for me :roll:

First:
---- the third, fourth and fifth expressions in the fisrt “do”’s argument : compare-to result backref will be evaluated and returned as the value of the do loop when iteration terminates, as happens in dolist ??right? then so far it's ok..but:

Second:
--- is it possible call variables or expression before declare it? Also in an iterations or conditionals?
What seems strange to me is that it’s possible ,for example, initiate a conditional with a variable or expression that will be defined afterwards!!!:
for example in your code :
> (if result… setf result (list compare-to)….)
result is also used as expression of second argument in "do"....... :roll:
honestly now I'm a little confused about this behavior....can you briefly explain me that???
thanks again!!!
megera
 
Posts: 30
Joined: Wed Oct 10, 2012 1:34 pm

Re: end chapter exercise's doubts...

Postby Goheeca » Mon Nov 05, 2012 6:40 am

If you look at the definition of do, you can see that the result is actually defined/declared (I don't know the exact terminology) by the do:
Code: Select all
((i (1- (length vector)) (1- i)) compare-to result backref)

And returned from the do is:
Code: Select all
((= i 0) result)

the first part is a condition and the rest is an implicit progn.
cl-2dsyntax is my attempt to create a Python-like reader. My mirror of CLHS (and the dark themed version).
User avatar
Goheeca
 
Posts: 198
Joined: Thu May 10, 2012 12:54 pm

Re: end chapter exercise's doubts...

Postby wvxvw » Mon Nov 05, 2012 11:58 am

> is it possible call variables or expression before declare it?

Perhaps, confusing terminology here. Usually, when you say "call", you intend to call something which is callable. In the context of CL that would be either functions or macros. So, if you are asking if it is possible to call a function before it is declared, then answer would be that, you can, sort of, but not directly. For example:
Code: Select all
(foo) ;; error
(defun foo ())

will fail, because foo symbol is not bound to any function, i.e. it's (symbol-function 'foo) is nil.
But you can declare a function that calls a function, which is not defined yet:
Code: Select all
(defun bar () (foo)) ;; warning here, but this is a legitimate code
(defun foo () (print "foo"))
(bar) ;; prints "foo"

And of course you can do it like this, to make it more fail-safe:
Code: Select all
(defun bar () (when (fboundp 'foo) (funcall 'foo)) ;; no warning here
(defun foo () (print "foo"))
(bar) ;; prints "foo"


There's really no way I could think of calling an expression before declaring it... I mean, once you have an expression, you have already declared it.
wvxvw
 
Posts: 125
Joined: Sat Mar 26, 2011 6:23 am

Re: end chapter exercise's doubts...

Postby megera » Mon Nov 05, 2012 1:18 pm

Hi and thanks very much guys for good explanations!!! ;)
eventually I continue to make the same mistake!! uffff :x : I forget that it’s possible initialize a variable without value, then take nil to default…

like compare-to result backref in wvxvw's code ..
thanks again!!!
megera
 
Posts: 30
Joined: Wed Oct 10, 2012 1:34 pm


Return to Common Lisp

Who is online

Users browsing this forum: psbot [Picsearch] and 2 guests

cron