#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2004
    Posts
    3
    Rep Power
    0

    Space and time for a few procedures.. (Scheme procedures, that is)


    Hey everyone,
    I apparently had an account here but forgot..? Any way, I wasn't able to make it to class last time and as a result, missed out on some good 'big O' discussion as well.

    I have a scheme midterm next week and I'm hoping someone here can help me understand the concept of time and space, and then maybe break down the procedues and show me what/why the time and space of each is.

    I'll start with 2-3 procedures today:

    (define (accumulate proc init alist)
    (cond ((null? alist) init)
    (else proc (car alist) (accumulate proc init (cdr alist))))))

    (define (insert x alist)
    (cond ((null? alist) (cons x alist))
    ((> x (car alist))
    (cons (car alist) (insert x (cdr alist))))
    (else
    (cons x alist))))

    (define (enumerate start end)
    (cond ((> start end) ())
    (else
    (cons start (enumerate (+ start 1) end)))))


    (define (filter test alist)
    (cond ((null? alist) ())
    ((test (car alist))
    (cons (car alist)
    (filter test (cdr alist))))
    (else
    (filter test (cdr alist)))))


    Okay, so that's 4. Sorry I need to know space and time... and I'll be honest, I haven't tested them in Dr. Scheme yet. I'm trying to figure out what the procedues are even (insert looks easy enough). I need to know how to test them as well. ANY help will be appreciated.. so err, please do so
  2. #2
  3. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2004
    Posts
    3
    Rep Power
    0
    ok, c'mon, a few of you might know Scheme.... well at least 3% or so says the poll
  4. #3
  5. Commie Mutant Traitor
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jun 2004
    Location
    Alpharetta, GA
    Posts
    1,806
    Rep Power
    1570
    I can give you a quick-and-dirty informal analysis, but you'll need to do any formal work yourself. OK, let's start with this one:

    Scheme Code:
     
    (define (accumulate proc init alist)
       (cond ((null? alist) init)
            (else proc (car alist) (accumulate proc init (cdr alist))))))


    Since this is a functional, the actual time and space will depend on the function being applied, but the (accumulate) function itself is a simple linear time - O(n) - operation: it makes exactly one pass over each of the items in alist. Since the function is not tail recursive (it accumulates the results from the later values first, then performs the final operation afterwards), the function is called for each pass, so it is also linear in space.

    Now for (insert):

    Scheme Code:
     
    (define (insert x alist)
       (cond ((null? alist) (cons x alist))
             ((> x (car alist))
                (cons (car alist) (insert x (cdr alist))))
             (else (cons x alist))))


    Here, the function tests each element of a sorted list: if the value of x is greater than the current element (the (car) of alist), then it recurses on the remainder of the list and conses the result to the current element. If it finds an element greater than or equal to x, then it returns the remainder of alist consed to x. If it reaches the end of the list without finding a larger value, it simply returns x. Walking through an example (insert 4 '(1 3 3 4 7)), you would get
    Code:
    (car alist) == 1, 4 > 1,   -> 
      (cons 1 (insert 4 '(3 3 4 7)))
    
    (car (cdr alist)) == 3, 4 > 3 ->
       (cons 1 (cons 3 (insert 4 '(3 4 7))))
    
    (car (cdr (cdr alist))) == 3, 4 > 3  ->
       (cons 1 (cons 3 (cons 3 (insert 4 '(4 7)))))
    
    (car (cdr (cdr (cdr alist)))) == 4,  4== 4 ->
       (cons 1 (cons 3 (cons 3 (cons 4 '(4 7)))))
    As you can see, the algorithm would pass through each element at most once, so again, the upper bound of the time is linear; in the worst case (i.e., x is higher than any current element of alist) will take one pass per list element, plus one for the null element at the end of the list. Since the algorithm is non-tail recursive, and there is one recursive call per element, the space is also linear worst case (actually, it is marginally less than linear, since the list decreases with each pass, but that's not really consequential).

    This should give you some idea of how to at least estimate the efficiency of relatively simple functions like these. Keep in mind that the values for big-O notation are relative efficency; they don't measure the absolute speed of the function (which would depend on the particular implementation), but rather, how the efficency scales with size of the arguments.

    References:
    Wikipedia: Big O Notation
    NIST article: Big O Notation
    Complexity and Big O Notation
    Big-O Notation and Algorithm Analysis

    Comments on this post

    • SimonGreenhill agrees
    • Yegg` agrees
    • netytan agrees
    Last edited by Schol-R-LEA; March 13th, 2006 at 03:47 AM.
    Rev First Speaker Schol-R-LEA;2 JAM LCF ELF KoR KCO BiWM TGIF
    #define KINSEY (rand() % 7) λ Scheme is the Red Pill
    Scheme in Short Understanding the C/C++ Preprocessor
    Taming Python A Highly Opinionated Review of Programming Languages for the Novice, v1.1

    FOR SALE: One ShapeSystem 2300 CMD, extensively modified for human use. Includes s/w for anthro, transgender, sex-appeal enhance, & Gillian Anderson and Jason D. Poit clone forms. Some wear. $4500 obo. tverres@et.ins.gov

IMN logo majestic logo threadwatch logo seochat tools logo