Getting the first n elements from a list

Discussion in 'Cadence' started by Suresh Jeevanandam, Aug 19, 2004.

  1. Hi all,
    Is there a skill function to get the first n elements of a list.

    Thanks in advance,
     
    Suresh Jeevanandam, Aug 19, 2004
    #1
  2. I could come up with this. Your suggestion to make it more efficient is
    most welcome.

    procedure( nElements(theList, n)
    let( (x)
    x = nil
    for(i 1 n
    x = tconc(x car(theList))
    theList = cdr(theList)
    )
    car(x)
    );let
    );procedure

    regards,
    Suresh
     
    Suresh Jeevanandam, Aug 19, 2004
    #2
  3. Suresh,

    If you don't mind it being destructive, you can use:

    procedure(nElements(theList n)
    rplacd(nthcdr(sub1(n) theList) nil)
    theList
    )

    You could use a little trick to destructively modify it, copy, and then
    modify back again:

    procedure(nElements(theList n)
    let((tail tailcdr)
    tail=nthcdr(sub1(n) theList)
    tailcdr=cdr(tail)
    rplacd(tail nil)
    prog1(
    copy(theList)
    rplacd(tail tailcdr)
    )
    )
    )

    However, I don't think this is any more efficient than what you're doing. It
    may even be a little less efficient because it traverses the list once in the
    nthcdr, and again in the copy (just the first n elements).

    The function below may be a little more efficient, because you're
    using a built-in loop (forall) to do the loop traversal:

    procedure(nElements(theList n)
    let((new)
    forall(elem theList n-->0 && (new=tconc(new elem)))
    car(new)
    )
    )

    Note - in your code, there's no need to initialise x to nil, since that is the
    default value for anything in a let().

    Probably I'd do some profiling to be certain... just wanted to give a few
    options for the benefit of you and the audience ;-)

    Finally, why are you getting the first n elements in a list? Are you approaching
    the bigger problem in the right way?

    Andrew.
     
    Andrew Beckett, Aug 19, 2004
    #3
  4. Andrew Beckett wrote:
    [....]
    Andrew,
    I think the code snippet above would be the most efficient:
    Reasons:
    1)Locating the tail is done using 'nthcdr'. Mine uses for loop which
    would be less efficient.

    2) Copy is done by the standard copy function. Mine does copying by calling
    n times, which would be less efficient.

    thanks,
    Suresh

    ----
    A little experiment on this,

    procedure(lrange(num)
    ;return a list of numbers from 1 to num
    let((rlist)
    rlist = nil
    while(num > 0
    rlist = cons(num rlist)
    num = num-1
    )
    rlist
    ))

    a = lrange(100000)

    procedure( nElements(theList, n)
    let( (x)
    x = nil
    for(i 1 n
    x = tconc(x car(theList))
    theList = cdr(theList)
    )
    car(x)
    );let
    );procedure

    procedure(nElements2(theList n)
    let((tail tailcdr)
    tail=nthcdr(sub1(n) theList)
    tailcdr=cdr(tail)
    rplacd(tail nil)
    prog1(
    copy(theList)
    rplacd(tail tailcdr)
    )
    )
    )



    x = measureTime(nElements(a 50000))
    y = measureTime(nElements2(a 50000))
     
    Suresh Jeevanandam, Aug 20, 2004
    #4
Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.