From: Mark Chang
Subject: How to find the first n items in a list?
Date: 
Message-ID: <1992Sep28.175845.14395@bcrka451.bnr.ca>
 Can any experts suggest the most efficient way to
 find the first n items in a long list? I am mostly 
 concerned with the speed. 
 
 For example, I have a long list, '(0 1 2 ..... 9999)
 and I want the first 1000 items as a list, '(0 1 ... 1000).
 
 I can think of some ways, but none very efficient.
 What is the "standard" way to do this? 
 
 Thanks in advance for your help.

 ________________________________________________________
| Mark H. Chang     (······@bnr.ca)                      |
| (613) 763-7688    Bell-Northern Research               |
|                   Ottawa, Ontario                      |
|________________________________________________________|
                                                         

From: Sandra Loosemore
Subject: Re: How to find the first n items in a list?
Date: 
Message-ID: <1992Sep29.001551.23312@cs.yale.edu>
······@bcrka440.bnr.ca (Mark Chang) writes:

    Can any experts suggest the most efficient way to
    find the first n items in a long list?

Ummm, use SUBSEQ?  I'd expect that to be implemented in a way that's
reasonably efficient.

-Sandra
From: Kent M Pitman
Subject: How to find the first n items in a list?
Date: 
Message-ID: <19920928203939.6.KMP@PLANTAIN.SCRC.Symbolics.COM>
    Date: Mon, 28 Sep 1992 13:58 EDT
    From: Mark Chang <······@bcrka440.bnr.ca>

    For example, I have a long list, '(0 1 2 ..... 9999)
    and I want the first 1000 items as a list, '(0 1 ... 1000).
 
There are several ways to do this.

Efficiency will somewhat depend on whose implementation you're using
since different implementations make different operations fast.

It also depends on what assumptions you are making about how the list is
terminated.  e.g., in both of the following, I'm assuming the list might 
be dotted.

The most common technique which you are most likely to be overlooking is
consing the list up backward and nreversing it.

(DEFUN FIRSTN (LIST N)
  (IF (OR (ATOM LIST) (< N 1))
      LIST
      (DO ((NEW-LIST '() (CONS (CAR L) NEW-LIST))
	   (L LIST (CDR L))
	   (I 0 (1+ I)))
	  ((= I N) (NREVERSE NEW-LIST))
	(WHEN (ATOM L) (RETURN (NRECONC NEW-LIST L))))))

It is possible with a little extra work to do it one-pass forward, but
the disadvantage is that in a multi-processing environment, there may be
intermediate consing in another process the list may get scattered.  Also,
in a cdr-coded implementation, the resulting list will not be cdr-coded.
In fact, in the following, if you do (LIST (CAR LIST)) instead of
(CONS (CAR LIST) NIL) you'll get really bad performance in a cdr-coded
implementation.

(DEFUN FIRSTN (LIST N)
  (IF (OR (ATOM LIST) (< N 1))
      LIST
      (LET ((NEW-LIST (CONS (CAR LIST) NIL)))
	(DO ((I 1 (1+ I))
	     (L (CDR LIST) (CDR L))
	     (TAIL NEW-LIST (CDR TAIL)))
	    ((= I N) NEW-LIST)
	  (COND ((ATOM L)
		 (SETF (CDR TAIL) L)
		 (RETURN NEW-LIST))
		(T
		 (SETF (CDR TAIL) (CONS (CAR L) NIL))))))))

Another technique that relies on your having a good GC and/or a belief
that the N is going to be below the number of elements in the list most of
the time (so you don't throw things away much) is to make the list first 
and then copy elements into it. e.g.,

(DEFUN FIRSTN (LIST N)
  (IF (OR (ATOM LIST) (< N 1))
      LIST
      (LET ((NEW-LIST (MAKE-LIST N)))
	(DO ((L LIST (CDR L))
	     (NL NEW-LIST (CDR NL))
	     (TAIL NIL NL)
	     (I 0 (1+ I)))
	    ((= I N) NEW-LIST)
	  (COND ((ATOM L)
		 (SETF (CDR TAIL) L)
		 (RETURN NEW-LIST))
		(T
		 (SETF (CAR NL) (CAR L))))))))

Here are some test cases that should work for all of these.

(FIRSTN '(A B C D) 2) => (A B)
(FIRSTN '(A B C D) 20) => (A B C D)
(FIRSTN '(A B C . D) 3) => (A B C)
(FIRSTN '(A B C . D) 5) => (A B C . D)
(FIRSTN 'A 3) => A

And, actually, the following should not have really terrible performance.
It doesn't work for dotted or circular lists, though, and it forces the
entire list just to compute its length.  You could write a custom version
of LENGTH that timed out after value N, though, to make back the speed on
that.

(defun firstn (list n) 
  (let ((len (length list)))
    (butlast list (max (min len (- len n)) 0))))

The advantage here is that BUTLAST is probably specially coded to be optimal
at the copying part for the given implementation.
From: Rick Busdiecker
Subject: Re: How to find the first n items in a list?
Date: 
Message-ID: <RFB.92Sep28210127@H.cs.cmu.edu>
In article <····················@PLANTAIN.SCRC.Symbolics.COM> ···@stony-brook.scrc.symbolics.com (Kent M Pitman) writes:

       Date: Mon, 28 Sep 1992 13:58 EDT
       From: Mark Chang <······@bcrka440.bnr.ca>

       For example, I have a long list, '(0 1 2 ..... 9999)
       and I want the first 1000 items as a list, '(0 1 ... 1000).

   . . .

   It also depends on what assumptions you are making about how the list is
   terminated.  e.g., in both of the following, I'm assuming the list might 
   be dotted.

If you can assume that N is less than or equal to the length of
the list, you could use:

(defun firstn (list n)
  (subseq list 0 n))

and rely on the implementation to implement SUBSEQ efficiently.  For
some implementations, such as Allegro (Extended Common Lisp 2.0.10),
the restriction on N is not necessary.

   You could write a custom version of LENGTH that timed out after
   value N . . .

This would also apply here, for example:

(defun firstn (list n)
  (if (list-length-less-than list n)
      (subseq list 0 n)
      list))

-- 
Rick Busdiecker <····@cs.cmu.edu>
``Beware of programmers carrying screwdrivers''
				- Unknown
From: Tushar Saxena
Subject: Re: How to find the first n items in a list?
Date: 
Message-ID: <1992Sep28.222634.1405@cs.albany.edu>
In article <······················@bcrka451.bnr.ca> ······@bnr.ca writes:
> For example, I have a long list, '(0 1 2 ..... 9999)
> and I want the first 1000 items as a list, '(0 1 ... 1000).
> 
> I can think of some ways, but none very efficient.
> What is the "standard" way to do this? 

How about this. Make that list a stream and then use the continuation methods
to get the first n elements without evaluating the whole list. This is sketchy
but I am positive that this can be done in Scheme. I will try on lisp but
methinks it should be possible in lisp too!


ttfn
	-Tush.

--------------------------------------------------------------------------------
And any fool knows a dog needs a home, A shelter from pigs on the wing.
        -Roger Waters
--------------------------------------------------------------------------------
email : ······@cs.albany.edu                        Computer Science Department
Phone : 518-442-3388				    SUNY Albany
Tushar Saxena					    Albany NY 12222 (USA)
--------------------------------------------------------------------------------