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

ListBuffer.size is O(n), but ListBuffer.length is O(1) #4933

Closed
scabug opened this issue Aug 20, 2011 · 2 comments
Closed

ListBuffer.size is O(n), but ListBuffer.length is O(1) #4933

scabug opened this issue Aug 20, 2011 · 2 comments
Assignees

Comments

@scabug
Copy link

scabug commented Aug 20, 2011

The length and size methods on ListBuffer differ. The former is overridden in ListBuffer.scala to have an O(1) implementation, but the latter forwards to "underlying", which uses the O(n ) implementation from TraversableOnce.

To reproduce,

def time[A](f: => A): A = {
  val t1 = System.currentTimeMillis
  val ret = f
  val t2 = System.currentTimeMillis
  println("%g secs".format((t2 - t1)/1000.))
  ret
}

val lb = collection.mutable.ListBuffer.tabulate[Int](1000*1000)(identity)

time(for (j <- 0 until 10000) { lb.length })
time(for (j <- 0 until 10000) { lb.size })

I get,

scala> time(for (j <- 0 until 1000) { lb.length })
0.00000 secs

scala> time(for (j <- 0 until 1000) { lb.size })
5.48300 secs

The issue came up on StackOverflow, where Daniel Sobral explained the behavior,
http://stackoverflow.com/questions/7061842/what-is-the-running-time-for-size-on-scalas-listbuffer

It would also be nice to update the ScalaDoc for ListBuffer.length and size with performance characteristics.

@scabug
Copy link
Author

scabug commented Aug 20, 2011

Imported From: https://issues.scala-lang.org/browse/SI-4933?orig=1
Reporter: Kipton Barros (kbarros)
Affected Versions: 2.9.1

@scabug
Copy link
Author

scabug commented Sep 19, 2011

Commit Message Bot (anonymous) said:
(extempore in r25684) ListBuffer.size should be O(1).

Not O(n) like it was. Here's another good candidate for some
mythical performance regression tests. Closes #4933, no review.

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

No branches or pull requests

2 participants