Перекрытие стека в связанном списке Scala

Question

Используя scala, я добавил около 100000 узлов в связанный список.Когда я использую функцию length, например mylist.length.Я получаю ошибку 'java.lang.StackOverflowError', мой список слишком большой для обработки?В списке только строковые объекты.

Answer 1

Похоже, что реализация библиотеки не является хвостовой рекурсивной override def length: Int = if (isEmpty) 0 else next.length + 1.Похоже, это то, что можно обсудить в списке рассылки, чтобы проверить, нужно ли открывать билет расширения.

Вы можете вычислить длину следующим образом:

def length[T](l:LinkedList[T], acc:Int=0): Int =
  if (l.isEmpty) acc else length(l.tail, acc + 1)

Answer 2

В Scala вычисление длины List является операцией порядка n, поэтому вам следует избегать ее. Вы можете подумать о переключении на массив, так как это операция с постоянным временем.

Answer 3

Можете ли вы подтвердить, что вам действительно нужно использовать метод length? Похоже, вы не используете правильный тип коллекции для вашего варианта использования (трудно сказать без какой-либо дополнительной информации). Списки оптимизированы для отображения с использованием сгибов или хвостовой рекурсивной функции.

Несмотря на это, это абсолютно упущение, которое можно легко исправить в стандартной библиотеке с помощью хвостовой рекурсивной функции. Надеюсь, мы сможем успеть за 2.9.0.

Answer 4

Вы можете попробовать увеличить размер стека / кучи, доступный для JVM.

scala JAVA_OPTS="-Xmx512M -Xms16M -Xss16M" MyClass.scala

Где

-Xss<size>  maximum native stack size for any thread
-Xms<size>  set initial Java heap size
-Xmx<size>  set maximum Java heap size

Этот вопрос содержит дополнительную информацию.

См. Также Этот документ Scala .