Управление неиспользованными списками в Scala

Question

Скала обладает богатством неизменной структуры.

Мне было интересно, как Scala управляет чрезмерным размещением и освобождением таких объектов. Как это выглядит для существующих списков, когда, например, объединение 1 до List(1,2,3). Как он отслеживает, что определенный List не используется, и позволяет сборщику мусора освободить его?

Я бы сделал это примерно так

class List {
    private Map<Integer,WeakRef<List>> listCache;
    public List(Integer head,List tail) {...}
    public synchronized List prepend(Integer i) {
        if (listCache.get(i) != null) {
            if (listCache.get(i).get() == null) {
                listCache.put(i,new List(i,this));
            }
    }
}

Как это делает Scala? Хорошо ли он справляется с чрезмерным распределением и освобождением? Что это делает с многопоточностью?

Answer 1

Давайте напишем простой List класс:

sealed abstract class MyList[+T] {
  def head: T
  def tail: MyList[T]
  def isEmpty: Boolean
  def prepend[T1 >: T](el: T1): MyList[T1]
}

object EmptyList extends MyList[Nothing] {
  def head: Nothing = throw new java.util.NoSuchElementException("head of an empty list")
  def tail: MyList[Nothing] = throw new UnsupportedOperationException("unsupported operation exception")
  def isEmpty = true
  def prepend[T1 >: Nothing](el: T1): MyList[T1] = new Cons(el, this)

  override def toString = "EmptyList"
}

final class Cons[+T](val head: T, val tail: MyList[T]) extends MyList[T] {
  def isEmpty = false
  def prepend[T1 >: T](el: T1): MyList[T1] = new Cons(el, this)

  override def toString = head + ", " + tail.toString
}

Списки в Scala работают так.Итак, рассмотрим пример, который вы упомянули:

scala> val list = new Cons(1, new Cons(2, new Cons(3, EmptyList)))
list: Cons[Int] = 1, 2, 3, EmptyList

scala> val newList = list.prepend(1)
newList: MyList[Int] = 1, 1, 2, 3, EmptyList

Итак, вопросы:

• Мы искали списки для повторного использования?Нет.
• Мы использовали что-нибудь еще?Да, мы повторно использовали список, в который был вызван prepend.
• Как это будет собирать мусор?Как и любой объект в JVM: когда на него ничего не указывает, он будет собран.

Конечно, если я создам другой список, подобный этому:

val list2 = list.prepend(1)

Тогда newList и list2 будут использовать list, но будут разными списками, даже если они содержат одинаковые элементы.

Вы можете спросить (как это было сделано в комментариях), если этот шаблон повторного использования является практичным,или приносит ли это какие-либо выгоды в реальной жизни, и ответ на этот вопрос заключается в том, что много алгоритмов используют это преимущество.

На самом деле, позвольте мне указать на этот вопрос, в котором якобы «медленный» код был на самом деле быстрее, чем якобы «быстрый» код, а также альтернативы, предложенные в ответах. причина , почему "медленный" код не был чем-то подобным, является именно этим шаблоном повторного использования.

Answer 2

Scala вообще не управляет освобождением этих объектов.Они создаются в куче как обычные объекты JVM, а мусор собирается в JVM, как и любой другой объект Java или Scala.Как отмечают комментарии к вашему вопросу, он не использует списки, созданные в результате предыдущих вызовов List (), - это всегда новый объект.

Чтобы прояснить ситуацию с конкатенацией списков - в этом случае результирующий объект List содержит содержит ссылку на два конца списка, но он по-прежнему не выполняет никакого специального кэшированияранее использованных списков или что-то в этом роде.