Using scala I have added about 100000 nodes to a linked list. When I use the function length, for example mylist.length. I get a 'java.lang.StackOverflowError' error, is my list to big to process? The list is only string objects.
Add a comment
|
4 Answers
It appears the library implementation is not tail-recursive override def length: Int = if (isEmpty) 0 else next.length + 1. It seems like this is something that could be discussed on the mailing list to check if an enhancement ticket should be opened.
You can compute the length like this:
def length[T](l:LinkedList[T], acc:Int=0): Int =
if (l.isEmpty) acc else length(l.tail, acc + 1)
2 Comments
Daniel C. Sobral
I'm all for an enhancement ticket. This method can be easily implemented in a non-recursive manner all the way back in
TraversableOnce. I can even implement it in this comment line: def length: Int = { var count = 0; foreach { _ => count += 1 }; count }. Back on LinearSeq, it one can get even better performance by using a private helper method to make the original implementation fully tail recursive. IMHO, both approaches should be taken. Do you open it, or may I?
huynhjl
@Daniel Please open it, as you can provide more suggestions than me, just like you did here.
In Scala, computing the length of a List is an order n operation, therefore you should try to avoid it. You might consider switching to an Array, as that is a constant time operation.
1 Comment
Luigi Plinge
Vector is preferable to ArrayYou could try increasing the stack/heap size available to the JVM.
scala JAVA_OPTS="-Xmx512M -Xms16M -Xss16M" MyClass.scala
Where
-Xss<size> maximum native stack size for any thread
-Xms<size> set initial Java heap size
-Xmx<size> set maximum Java heap size
This question has some more information.
See also this This Scala document.
1 Comment
huynhjl
You mean
JAVA_OPTS="-Xmx512M -Xms16M -Xss16M" scala MyClass.scala? My shell requires for JAVA_OPTS to be before the scala command.Can you confirm that you truly need to use the length method? It sounds like you might not be using the correct collection type for your use-case (hard to tell without any extra information). Lists are optimised to be mapped over using folds or a tail-recursive function.
Despite saying that, this is absolutely an oversight that can easily be fixed in the standard library with a tail-recursive function. Hopefully we can get it in time for 2.9.0.
