Prev: Emacs Lisp's print, princ, prin1, format, message (tutorial)
Next: Breaking up a long string literal
From: Yongwei Xing on 12 Aug 2010 09:51
On Aug 12, 8:17 pm, p...(a)informatimago.com (Pascal J. Bourguignon)
wrote:
> Yongwei Xing <jdxyw2...(a)gmail.com> writes:
> > Hi all
>
> > I am reading the SICP recently. I have a question about the stream in
> > Chapter 3.
>
> > There is an example about the infinite stream like integers. When I
> > use the stream-ref to get the 100th,200th,500th and 3000th value of
> > this integers stream, everything is OK. When I try to get the 5000th
> > value of this integers, it threw a Stack Overflow error.
>
> > So, what's wrong with it? If there is any methond to make it a really
> > infinite stream?
> > When I try to run the code like it
> > (loop for i from 1 to 1000000 do (print (stream-ref integers i)))
> > it would stop when i is about 5000. Is there any way to solve this
> > problem?
>
> I assume you're using this definition of stream-ref:
>
>     (defun stream-ref (s n)
>       (if (= n 0)
>         (stream-car s)
>         (stream-ref (stream-cdr s) (- n 1))))
>
> Unfortunately, while this is a tail-recursive function, Common Lisp
> doesn't enforce tail-calls optimization.
>
> Notably, if you're using clisp, the interpreter doesn't have it.  You
> have to compile functions in clisp to get some level of tail recursive
> call optiomization.  Other implementations may more often implement TCO..
>
> In any case, you can rewrite this function in an iterative way instead
> of recursive.
> Read again section "1.2  Procedures and the Processes They Generate"
>
>     (defun stream-ref (s n)
>       (loop
>          :for i :from n :downto 0
>          :for c = s :then (stream-cdr c)
>          :finally (return (stream-car c))))
>
> --
> __Pascal Bourguignon__                    http://www.informatimago.com/

I have a question about the efficiency of the stream-ref. If i have an
infinite stream, I need get the items from 10000th to 20000th. Each
time I get a item, the stream-ref need go about 10000 steps. The total
steps is more than 100000000 steps. Can I say stream is not so
efficiency ?
From: Pascal J. Bourguignon on 12 Aug 2010 10:16
Yongwei Xing <jdxyw2004(a)gmail.com> writes:

> On Aug 12, 8:17�pm, p...(a)informatimago.com (Pascal J. Bourguignon)
> wrote:
>> Yongwei Xing <jdxyw2...(a)gmail.com> writes:
>> > Hi all
>>
>> > I am reading the SICP recently. I have a question about the stream in
>> > Chapter 3.
>>
>> > There is an example about the infinite stream like integers. When I
>> > use the stream-ref to get the 100th,200th,500th and 3000th value of
>> > this integers stream, everything is OK. When I try to get the 5000th
>> > value of this integers, it threw a Stack Overflow error.
>>
>> > So, what's wrong with it? If there is any methond to make it a really
>> > infinite stream?
>> > When I try to run the code like it
>> > (loop for i from 1 to 1000000 do (print (stream-ref integers i)))
>> > it would stop when i is about 5000. Is there any way to solve this
>> > problem?
>>
>> I assume you're using this definition of stream-ref:
>>
>> � � (defun stream-ref (s n)
>> � � � (if (= n 0)
>> � � � � (stream-car s)
>> � � � � (stream-ref (stream-cdr s) (- n 1))))
>>
>> Unfortunately, while this is a tail-recursive function, Common Lisp
>> doesn't enforce tail-calls optimization.
>>
>> Notably, if you're using clisp, the interpreter doesn't have it. �You
>> have to compile functions in clisp to get some level of tail recursive
>> call optiomization. �Other implementations may more often implement TCO.
>>
>> In any case, you can rewrite this function in an iterative way instead
>> of recursive.
>> Read again section "1.2 �Procedures and the Processes They Generate"
>>
>> � � (defun stream-ref (s n)
>> � � � (loop
>> � � � � �:for i :from n :downto 0
>> � � � � �:for c = s :then (stream-cdr c)
>> � � � � �:finally (return (stream-car c))))
>>
>> --
>> __Pascal Bourguignon__ � � � � � � � � � �http://www.informatimago.com/
>
> I have a question about the efficiency of the stream-ref. If i have an
> infinite stream, I need get the items from 10000th to 20000th. Each
> time I get a item, the stream-ref need go about 10000 steps. The total
> steps is more than 100000000 steps. Can I say stream is not so
> efficiency ?

Sure, (stream-ref s n) is O(n).

If you need a substream, you can write a more efficient function
without using stream-ref.


(defun stream-substream (s from to)
(loop
:for c = s :then (stream-cdr c) ; The order of the :for lines
:for i :from 0 :below from ; is important!
:finally (return (loop
:repeat (- to from)
:for u = c :then (stream-cdr u)
:collect (stream-car u)))))

This (stream-substream s from to) will be O(to) instead of O(to�).


--
__Pascal Bourguignon__ http://www.informatimago.com/
From: Yongwei Xing on 13 Aug 2010 01:06
On Aug 12, 4:16 pm, p...(a)informatimago.com (Pascal J. Bourguignon)
wrote:
> Yongwei Xing <jdxyw2...(a)gmail.com> writes:
> > On Aug 12, 8:17 pm, p...(a)informatimago.com (Pascal J. Bourguignon)
> > wrote:
> >> Yongwei Xing <jdxyw2...(a)gmail.com> writes:
> >> > Hi all
>
> >> > I am reading the SICP recently. I have a question about the stream in
> >> > Chapter 3.
>
> >> > There is an example about the infinite stream like integers. When I
> >> > use the stream-ref to get the 100th,200th,500th and 3000th value of
> >> > this integers stream, everything is OK. When I try to get the 5000th
> >> > value of this integers, it threw a Stack Overflow error.
>
> >> > So, what's wrong with it? If there is any methond to make it a really
> >> > infinite stream?
> >> > When I try to run the code like it
> >> > (loop for i from 1 to 1000000 do (print (stream-ref integers i)))
> >> > it would stop when i is about 5000. Is there any way to solve this
> >> > problem?
>
> >> I assume you're using this definition of stream-ref:
>
> >>     (defun stream-ref (s n)
> >>       (if (= n 0)
> >>         (stream-car s)
> >>         (stream-ref (stream-cdr s) (- n 1))))
>
> >> Unfortunately, while this is a tail-recursive function, Common Lisp
> >> doesn't enforce tail-calls optimization.
>
> >> Notably, if you're using clisp, the interpreter doesn't have it.  You
> >> have to compile functions in clisp to get some level of tail recursive
> >> call optiomization.  Other implementations may more often implement TCO.
>
> >> In any case, you can rewrite this function in an iterative way instead
> >> of recursive.
> >> Read again section "1.2  Procedures and the Processes They Generate"
>
> >>     (defun stream-ref (s n)
> >>       (loop
> >>          :for i :from n :downto 0
> >>          :for c = s :then (stream-cdr c)
> >>          :finally (return (stream-car c))))
>
> >> --
> >> __Pascal Bourguignon__                    http://www.informatimago.com/
>
> > I have a question about the efficiency of the stream-ref. If i have an
> > infinite stream, I need get the items from 10000th to 20000th. Each
> > time I get a item, the stream-ref need go about 10000 steps. The total
> > steps is more than 100000000 steps. Can I say stream is not so
> > efficiency ?
>
> Sure, (stream-ref s n) is O(n).
>
> If you need a substream, you can write a more efficient function
> without using stream-ref.
>
> (defun stream-substream (s from to)
>    (loop
>       :for c = s :then (stream-cdr c) ; The order of the :for lines
>       :for i :from 0 :below from      ; is important!
>       :finally (return (loop
>                           :repeat (- to from)
>                           :for u = c :then (stream-cdr u)
>                           :collect (stream-car u)))))
>
> This (stream-substream s from to) will be O(to) instead of O(to²).
>
> --
> __Pascal Bourguignon__                    http://www.informatimago.com/- Hide quoted text -
>
> - Show quoted text -

You methond is good for only getting a range of item from a stream.
But I have another queation.

You know, in SICP chapter 3, stream seams very good when you use a
stram as a input for a singal proces device. The output of the first
step would be the second step's input. The output of the second step
would be input of third step. But the output of your function is a
list, not s stream.

If we use the original stream described in the text book, the time
would be O(n²). Do you think it's a disadvantage? Is there any way to
imporve it or modify it?

Best Regards,
From: Leandro Rios on 13 Aug 2010 09:04
Yongwei Xing <jdxyw2004(a)gmail.com> writes:


> On Aug 12, 4:16�pm, p...(a)informatimago.com (Pascal J. Bourguignon)
> wrote:
>> > I have a question about the efficiency of the stream-ref. If i have an
>> > infinite stream, I need get the items from 10000th to 20000th. Each
>> > time I get a item, the stream-ref need go about 10000 steps. The total
>> > steps is more than 100000000 steps. Can I say stream is not so
>> > efficiency ?
>>
>> Sure, (stream-ref s n) is O(n).
>>
>> If you need a substream, you can write a more efficient function
>> without using stream-ref.
>>
>> (defun stream-substream (s from to)
>> � �(loop
>> � � � :for c = s :then (stream-cdr c) ; The order of the :for lines
>> � � � :for i :from 0 :below from � � �; is important!
>> � � � :finally (return (loop
>> � � � � � � � � � � � � � :repeat (- to from)
>> � � � � � � � � � � � � � :for u = c :then (stream-cdr u)
>> � � � � � � � � � � � � � :collect (stream-car u)))))
>>
>> This (stream-substream s from to) will be O(to) instead of O(to�).
>>
>> --
>> __Pascal Bourguignon__ � � � � � � � � �
>>
>> - Show quoted text -
>
> You methond is good for only getting a range of item from a stream.
> But I have another queation.
>
> You know, in SICP chapter 3, stream seams very good when you use a
> stram as a input for a singal proces device. The output of the first
> step would be the second step's input. The output of the second step
> would be input of third step. But the output of your function is a
> list, not s stream.
>
> If we use the original stream described in the text book, the time
> would be O(n�). Do you think it's a disadvantage? Is there any way to
> imporve it or modify it?
>


Yes, you could compose those functions you want to apply to each element
of the stream in series and apply the composed function to the stream via
stream-map, or if the functions aren't composable, use an iterator:

(defun make-stream-iterator (stream)
(let ((lastcdr stream))
(lambda ()
(prog1
(stream-car lastcdr)
(setf lastcdr (stream-cdr lastcdr))))))


CL-USER> (defparameter *iter* (make-stream-iterator (stream-infinite 0)))
*ITER*
CL-USER> (funcall *iter*)
0
CL-USER> (funcall *iter*)
1
CL-USER> (funcall *iter*)
2
CL-USER> (funcall *iter*)
3

Leandro


From: Pascal J. Bourguignon on 13 Aug 2010 12:35
Yongwei Xing <jdxyw2004(a)gmail.com> writes:

> On Aug 12, 4:16�pm, p...(a)informatimago.com (Pascal J. Bourguignon)
> wrote:
>> Yongwei Xing <jdxyw2...(a)gmail.com> writes:
>> > On Aug 12, 8:17�pm, p...(a)informatimago.com (Pascal J. Bourguignon)
>> > wrote:
>> >> Yongwei Xing <jdxyw2...(a)gmail.com> writes:
>> >> > Hi all
>>
>> >> > I am reading the SICP recently. I have a question about the stream in
>> >> > Chapter 3.
>>
>> >> > There is an example about the infinite stream like integers. When I
>> >> > use the stream-ref to get the 100th,200th,500th and 3000th value of
>> >> > this integers stream, everything is OK. When I try to get the 5000th
>> >> > value of this integers, it threw a Stack Overflow error.
>>
>> >> > So, what's wrong with it? If there is any methond to make it a really
>> >> > infinite stream?
>> >> > When I try to run the code like it
>> >> > (loop for i from 1 to 1000000 do (print (stream-ref integers i)))
>> >> > it would stop when i is about 5000. Is there any way to solve this
>> >> > problem?
>>
>> >> I assume you're using this definition of stream-ref:
>>
>> >> � � (defun stream-ref (s n)
>> >> � � � (if (= n 0)
>> >> � � � � (stream-car s)
>> >> � � � � (stream-ref (stream-cdr s) (- n 1))))
>>
>> >> Unfortunately, while this is a tail-recursive function, Common Lisp
>> >> doesn't enforce tail-calls optimization.
>>
>> >> Notably, if you're using clisp, the interpreter doesn't have it. �You
>> >> have to compile functions in clisp to get some level of tail recursive
>> >> call optiomization. �Other implementations may more often implement TCO.
>>
>> >> In any case, you can rewrite this function in an iterative way instead
>> >> of recursive.
>> >> Read again section "1.2 �Procedures and the Processes They Generate"
>>
>> >> � � (defun stream-ref (s n)
>> >> � � � (loop
>> >> � � � � �:for i :from n :downto 0
>> >> � � � � �:for c = s :then (stream-cdr c)
>> >> � � � � �:finally (return (stream-car c))))
>>
>> >> --
>> >> __Pascal Bourguignon__ � � � � � � � � � �http://www.informatimago.com/
>>
>> > I have a question about the efficiency of the stream-ref. If i have an
>> > infinite stream, I need get the items from 10000th to 20000th. Each
>> > time I get a item, the stream-ref need go about 10000 steps. The total
>> > steps is more than 100000000 steps. Can I say stream is not so
>> > efficiency ?
>>
>> Sure, (stream-ref s n) is O(n).
>>
>> If you need a substream, you can write a more efficient function
>> without using stream-ref.
>>
>> (defun stream-substream (s from to)
>> � �(loop
>> � � � :for c = s :then (stream-cdr c) ; The order of the :for lines
>> � � � :for i :from 0 :below from � � �; is important!
>> � � � :finally (return (loop
>> � � � � � � � � � � � � � :repeat (- to from)
>> � � � � � � � � � � � � � :for u = c :then (stream-cdr u)
>> � � � � � � � � � � � � � :collect (stream-car u)))))
>>
>> This (stream-substream s from to) will be O(to) instead of O(to�).
>>
>> --
>> __Pascal Bourguignon__ � � � � � � � � � �http://www.informatimago.com/- Hide quoted text -
>>
>> - Show quoted text -
>
> You methond is good for only getting a range of item from a stream.
> But I have another queation.
>
> You know, in SICP chapter 3, stream seams very good when you use a
> stram as a input for a singal proces device. The output of the first
> step would be the second step's input. The output of the second step
> would be input of third step. But the output of your function is a
> list, not s stream.
>
> If we use the original stream described in the text book, the time
> would be O(n�). Do you think it's a disadvantage? Is there any way to
> imporve it or modify it?

You're asking perfectly good question.

Too bad you don't try to answer them yourself...

Indeed, we could write stream-substream so it returns a stream, and
therefore doesn't need to instanciate the (- to from) element list.



(defun stream-prefix (s size)
(if (zerop size)
the-empty-stream
(cons-stream (stream-car s)
(stream-prefix (stream-cdr s) (1- size)))))

(defun stream-substream (s from to)
(loop
:for c = s :then (stream-cdr c) ; The order of the :for lines
:for i :from 0 :below from ; is important!
:finally (return (stream-prefix c (- to from)))))

(defun stream->list (s)
(loop
:until (stream-null? s)
:collect (stream-car s)
:do (setf s (stream-cdr s))))

(stream->list (stream-substream (stream-enumerate-interval 0 100000) 100 110))
;; --> (100 101 102 103 104 105 106 107 108 109)


--
__Pascal Bourguignon__ http://www.informatimago.com/
First  |  Prev  | 
Pages: 1 2
Prev: Emacs Lisp's print, princ, prin1, format, message (tutorial)
Next: Breaking up a long string literal