Measuring the Performance of a Datastructure

The purpose of this laboratory is to examine and compare two implementations of an abstract data structure for a stack. The first implementation uses functions to implement a constructor, predicates and accessors for stacks. The second uses an object oriented approach to implement stacks. You are to formulate an hypothesis about which implementation will give higher performance, gather performance data, analyze these two implementations and write a brief report.

The Experiment

The file data.struct.ijs contains the following definitions which provide a conventional (non-object oriented) implementation of an abstract data structure for stacks.

stack_tag =: box 'stack'
the_empty_stack =: box stack_tag

make_stack =: monad def 'the_empty_stack'

stackp =: monad def 'stack_tag match first open y.'

empty_stackp =: monad def 'the_empty_stack match y.'

push_stack =: monad define
('item' ; 'obj') =. y.
if. not stackp box obj
  do. error 'wrong type second input to push_stack' ; obj
  else. box obj append box item
end.
)

top_stack =: monad define
if. not stackp y.
  do. error 'wrong type input to top_stack' ; y.
  else. open last open y.
end.
)

pop_stack =: monad define
if. not stackp y.
  do. error 'wrong type input to pop_stack' ; y.
  else. box drop_last open y.
end.
)

size_stack =: monad define
if. not stackp y.
  do. error 'wrong type input to size_stack' ; y.
  else. _1 + tally open y.
end.
)

print_stack =: monad define
if. not stackp y.
    do. error 'wrong type input to print_stack' ; y.
  elseif. 0 = size_stack y.
    do. 'end of stack'
  elseif. 1
    do. display top_stack y.
        print_stack pop_stack y.
end.
)

NB. The stack object template

NB. The stack object template

data =: ''

stack =: monad define
('method' ; 'value') =. 2 take y.
if. method match 'type'
    do. 'stack'
  elseif. method match 'emptyp'
    do. 0 = tally data
  elseif. method match 'push'
    do. for_effect_only data =: (box value) , data
  elseif. method match 'top'
    do. if. 0 = tally data
          do. 'top:  stack is empty'
          else. open first data
        end.
  elseif. method match 'pop'
    do. if. 0 = tally data
          do. 'pop:  stack is empty'
          else. for_effect_only data =: rest data
        end.
  elseif. method match 'size'
    do. tally data
  elseif. method match 'print'
    do. if. 0 = tally data
          do. 'print: stack is empty'
          else. for_effect_only display 'top of stack'
            s =. data
            while. 0 < tally s
              do. for_effect_only display open first s
                  s =. rest s
            end.
        end.
  elseif. 1
    do. root_object method ; value
end.
)

Next, you should enter the J programming environment by entering the unix commands:

$ cd cs2322j
$ j

Then you should load the stack software by entering the J expression:

   ld 'data.struct.ijs'

when you are ready to begin working on this lab problem.

   s =: make_stack ''

Makes an empty stack named s. The expression:

   100 time 'push_stack 1 2 3 ; s'

   100 time 's =: push_stack 1 2 3 ; s'

   make_s_ 'stack.object.ijs'

Do the timing estimate for pushing the same value on the object oriented stack.

   100 time 'stack_s_ ''push'' ; 1 2 3'

Some questions to consider are:

Do the performance of the stack operations depend on how big the stack?

Do the performance of the stack operations depend on how large an item is pushed on the stack?

Gather data on the execution time performance of the traditional implementation and the object oriented implementation. Compare these results and draw conclusions. Try to explain performance differences. Was your hypothesis verified or incorrect. Write a brief report outlining your results.