Scala Programming Language
  1. Scala Programming Language
  2. SI-5387

Improve Performance Of dropWhile in TraversableLike

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: Scala 2.9.1
    • Fix Version/s: Scala 2.10.0
    • Component/s: Collections
    • Labels:

      Description

      scala.collection.TraversableLike:

      def dropWhile(p: A => Boolean): Repr = {
        val b = newBuilder
        var go = false
        for (x <- this) {
          if (!p(x)) go = true
          if (go) b += x
        }
        b.result
      }
      

      If the predicate p is an expensive computation than it unnecessarily slows dropWhile down after go is true.

      Suggestion:

      def dropWhile(p: A => Boolean): Repr = {
        val b = newBuilder
        var go = false
        for (x <- this) {
          if (go) b += x
          else { if (!p(x)) go = true }
        }
        b.result
      }
      

        Activity

        Hide
        Christopher Vogt added a comment -

        The suggested fix is broken. It always drops the first element, as go is always false in the first iteration. The following should implement the request correctly (notice the added !go && ):

        def dropWhile(p: A => Boolean): Repr = {
          val b = newBuilder
          var go = false
          for (x <- this) {
            if (!go && !p(x)) go = true
            if (go) b += x
          }
          b.result
        }
        

        Notice that this changes the semantics with regard to side effects of predicate p.

        Show
        Christopher Vogt added a comment - The suggested fix is broken. It always drops the first element, as go is always false in the first iteration. The following should implement the request correctly (notice the added !go && ): def dropWhile(p: A => Boolean): Repr = { val b = newBuilder var go = false for (x <- this) { if (!go && !p(x)) go = true if (go) b += x } b.result } Notice that this changes the semantics with regard to side effects of predicate p.
        Hide
        Peter Schmitz added a comment -

        Right, your suggestion was my first attempt. Tryed to improved, but failed obviously.

        Show
        Peter Schmitz added a comment - Right, your suggestion was my first attempt. Tryed to improved, but failed obviously.
        Hide
        Christopher Vogt added a comment -

        Ok, great . I get another opinion about the change and get back to you.

        Show
        Christopher Vogt added a comment - Ok, great . I get another opinion about the change and get back to you.
        Hide
        Christopher Vogt added a comment -

        I created a pull request https://github.com/scala/scala/pull/113 .

        Show
        Christopher Vogt added a comment - I created a pull request https://github.com/scala/scala/pull/113 .

          People

          • Assignee:
            Christopher Vogt
            Reporter:
            Peter Schmitz
          • Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development