Stream.toList() takes O(n^2) instead of O(n) version 4.4

[Clinton Selke]

having a look at the code for Stream.toList()

  public final List<A> toList() {

    List<A> as = List.nil();

    for (Stream<A> x = this; !x.isEmpty(); x = x.tail()._1()) {

      as = as.snoc(x.head());

    }

    return as;

  }

List.snoc() takes O(n), and its being repeated n-times. making it O(n^2).

It might be better to use List.cons() instead of List.snoc() like follows

  public final List<A> toList() {

    List<A> as = List.nil();

    for (Stream<A> x = this; !x.isEmpty(); x = x.tail()._1()) {

      as = as.cons(x.head());

    }

    return as.reverse();

  }

List.cons() takes O(1), and its repeated n-times in the for loop. making it O(n)

List.reverse() also takes O(n)

Overall time complexity O(n).

[Dobes Vandermeer]

List has a class in it called Buffer which I think is intended to provide an efficient snoc operation as well, perhaps that could be used for even better performance.

--
You received this message because you are subscribed to the Google Groups "Functional Java" group.
To unsubscribe from this group and stop receiving emails from it, send an email to functionaljav...@googlegroups.com.
To post to this group, send email to functio...@googlegroups.com.
Visit this group at http://groups.google.com/group/functionaljava.
For more options, visit https://groups.google.com/d/optout.

[Tony Morris]

Yes this implementation should use ListBuffer and do the nasty thing
internally. Code such as this typically exists because of a debugging
episode where the "hand-rolled performance improvement" was moved for
the benefit of "code that is easier to reason about." Unfortunately, it
seems to have slipped in to the library without detection for some time.
Nice spot.

> <mailto:functionaljav...@googlegroups.com>.

> To post to this group, send email to functio...@googlegroups.com

> <mailto:functio...@googlegroups.com>.

> Visit this group at http://groups.google.com/group/functionaljava.
> For more options, visit https://groups.google.com/d/optout.
>

> --
> You received this message because you are subscribed to the Google
> Groups "Functional Java" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to functionaljav...@googlegroups.com

> <mailto:functionaljav...@googlegroups.com>.

> To post to this group, send email to functio...@googlegroups.com

> <mailto:functio...@googlegroups.com>.

[Mark Perry]

I created an issue to address this, see https://github.com/functionaljava/functionaljava/issues/180.

Mark