Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve Performance Of dropWhile in TraversableLike #5387

Closed
scabug opened this issue Jan 18, 2012 · 5 comments
Closed

Improve Performance Of dropWhile in TraversableLike #5387

scabug opened this issue Jan 18, 2012 · 5 comments
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented Jan 18, 2012

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
}
@scabug
Copy link
Author

scabug commented Jan 18, 2012

Imported From: https://issues.scala-lang.org/browse/SI-5387?orig=1
Reporter: Peter Schmitz (peterschmitz)
Affected Versions: 2.9.1

@scabug
Copy link
Author

scabug commented Jan 18, 2012

@cvogt said:
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.

@scabug
Copy link
Author

scabug commented Jan 18, 2012

Peter Schmitz (peterschmitz) said:
Right, your suggestion was my first attempt. Tryed to improved, but failed obviously.

@scabug
Copy link
Author

scabug commented Jan 18, 2012

@cvogt said:
Ok, great :). I get another opinion about the change and get back to you.

@scabug
Copy link
Author

scabug commented Jan 19, 2012

@cvogt said:
I created a pull request scala/scala#113 .

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants