[mercury-users] efficiency questions

[Ralph Becket]

Robert Colvin, Tuesday,  5 February 2002:
> Hi, I was wondering whether the list operations take, drop, and
> split_list are implemented in constant time, or whether they use the
> usual iterative approach to traverse lists.  I'd like to use lists for
> their simplicity rather than move to arrays (I assume
> array__fetch_items/4 is relatively quick), but also need efficiency
> (this is for theoretical work, not an actual implementation).  I
> realise one should not rely on the efficiency of an implementation,
> but it would be nice to justify the use of lists.

Since lists are defined as 

:- type list(T) ---> [] ; [T | list(T)].

there is no way to find the nth member of a list in better than O(n)
time - you have to traverse each cons cell in turn.

take(N, Xs) has to traverse and duplicate the first N members of Xs;
drop(N, Xs) has to traverse the first N members of Xs;
split_list(N, Xs) has to traverse and duplicate the first N members of Xs.

Hence all these operations are necessarily O(n) for lists.

array__fetch_items(A, I, J) is also O(n) where N = J - I, since it has
to construct a list of N items.

The right thing to do if you want O(1) subarrays would be to add a
wrapper type around array/1, something like this:

:- type myarray(T) --->
    myarray(
        array       :: array(T),    % Source array.
        offset      :: int,         % Offset of element 0 in array.
        length      :: int          % Length of the subrange.
    ).

You can then write things like the following (I've omitted any sanity
checking)

:- func myarray(list(T)) = myarray(T).
myarray(Xs) = myarray(array(Xs), 0, length(Xs)).

:- func take(myarray(T), int) = myarray(T).
take(myarray(A, O, L), N) = myarray(A, O, N).

:- func drop(myarray(T), int) = myarray(T).
drop(myarray(A, O, L), N) = myarray(A, O + N, L - N).

:- func subrange(myarray(T), int, int) = myarray(T).
subrange(myarray(A, O, L), I, N) = myarray(A, O + I, N).

etc.

[split is just a combination of take/2 and drop/2.]

Of course, you'd have to supply the appropriate mode declarations to
handle arrays as unique objects.

My advice would be to write your code using an ADT supporting the
operations you need, implement it using lists to start off with, and
then move to arrays once the need for greater efficiency has been
established.

- Ralph
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------