Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

#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.