#34 append is needlessly inefficient

closed-fixed
nobody
None
5
2011-09-24
2011-08-29
Doug Currie
No

Presently append copies each argument (but the last) once for each argument, i.e., O(n-squared).

A small change would cons much less, exactly once for each cons required in the result...

static pointer revappend(scheme *sc, pointer term, pointer list) {
/* (append (reverse list) term) */
pointer p = list, result = term;
while (is_pair(p)) {
result = cons(sc, car(p), result);
p = cdr(p);
}
if (p == sc->NIL) {
return result;
}
return sc->F; /* signal an error */
}

case OP_APPEND: /* append */
x = sc->NIL;
y = sc->args;
if (y == x) {
s_return(sc,x);
}
while (cdr(y) != sc->NIL) {
x = revappend(sc, x, car(y));
y = cdr(y);
if (x == sc->F) {
Error_0(sc,"non-list argument to append");
}
}
s_return(sc, reverse_in_place(sc, car(y), x));

Discussion

  • Kevin Cozens

    Kevin Cozens - 2011-09-08

    Yes, append could be optimized. The code you have proposed still appears to have a different O(n-squared) situation. It calls revappend() in a loop and that function includes a loop. I think there is a way to make the code much more efficient by making use of knowing how the lists are stored internally. This could make append in to an O(n) operation and eliminate the need to reverse any list during the operation.

     
  • Doug Currie

    Doug Currie - 2011-09-08

    The code I proposed does one and only one cons for each new cons cell required by the scheme definition of append. It reverses the final result just once. So, it is O(N) in the number of cons cells in the result list.

    There are nested loops, the outer loop for the arguments to append, and the inner loop for the cons cells of those arguments. It doesn't get any better than that.

     
  • Kevin Cozens

    Kevin Cozens - 2011-09-19

    Other than formatting, the only change to the above code is to use car instead of cdr in the while loop under OP_APPEND.

     
  • Doug Currie

    Doug Currie - 2011-09-20

    Kevin, why would you want to use car instead of cdr? I use cdr to avoid copying the last argument, as required by the Scheme standard. If you use car this will break, and the function will return incorrect results if provided a null argument.

     
  • Kevin Cozens

    Kevin Cozens - 2011-09-24
    • status: open --> closed-fixed
     
  • Kevin Cozens

    Kevin Cozens - 2011-09-24

    If you have a loop that uses car(y) you would expect to check that car(y) is valid. It seems to work for all situations but not for (append '() 'a). I dno't have time to dig in to why it makes a difference. I have added a comment to the source code stating that the use of cdr() was not a typo and giving the test case that would break if car() was used.

    Suggested change commited as revision 88.

     

Log in to post a comment.