Scala: изменяемый по сравнению с неизменной объектной производительностью - OutOfMemoryError

Ну, это действительно зависит от того, какой тип карты вы используете. Вероятно HashMap . Теперь такие изменяемые структуры повышают производительность за счет предварительного выделения памяти, которую они ожидают использовать. Вы присоединяетесь к одному миллиону карт, поэтому финальная карта обязательно будет несколько большой. Давайте посмотрим, как эти пары "ключ-значение" добавляются:

protected def addEntry(e: Entry) { 
  val h = index(elemHashCode(e.key)) 
  e.next = table(h).asInstanceOf[Entry] 
  table(h) = e 
  tableSize = tableSize + 1 
  if (tableSize > threshold) 
    resize(2 * table.length) 
} 

См. 2 * в строке resize ? Изменяемый HashMap увеличивается, удваиваясь каждый раз, когда заканчивается место, в то время как неизменяемый является довольно консервативным в использовании памяти (хотя существующие ключи обычно занимают в два раза больше места при обновлении).

Теперь, поскольку для других проблем с производительностью вы создаете список ключей и значений в первых двух версиях. Это означает, что перед тем как присоединиться к картам, у вас уже есть каждый Tuple2 (пары ключ / значение) в памяти дважды! Плюс накладные расходы List , которые невелики, но мы говорим о более чем одном миллионе элементов, умноженных на накладные расходы.

Вы можете использовать проекцию, которая позволяет избежать этого. К сожалению, проекция основана на Stream , что не очень надежно для наших целей в Scala 2.7.x. Тем не менее, попробуйте следующее:

for (m <- listOfMaps.projection; kv <- m) yield kv

Поток не вычисляет значение, пока оно не понадобится. Сборщик мусора также должен собирать неиспользуемые элементы, если вы не сохраняете ссылку на заголовок Stream , что, по-видимому, имеет место в вашем алгоритме.

EDIT

Дополняя, понимание for / yield принимает одну или несколько коллекций и возвращает новую коллекцию. Так часто, как это имеет смысл, возвращаемая коллекция имеет тот же тип, что и исходная коллекция. Так, например, в следующем коде for-computing создает новый список, который затем сохраняется внутри l2 . Новый список создается не val l2 = , а для понимания.

val l = List(1,2,3)
val l2 = for (e <- l) yield e*2

Теперь давайте посмотрим на код, используемый в первых двух алгоритмах (за вычетом изменяемого ] ключевое слово):

(Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) 

Оператор foldLeft , здесь записанный с его синонимом /: , будет вызываться для объекта, возвращенного функцией for-computing. Помните, что : в конце оператора меняет порядок объекта и параметров.

Теперь давайте рассмотрим, что это за объект, для которого вызывается foldLeft . Первый генератор в этом понимании - m <- listOfMaps . Мы знаем, что listOfMaps - это коллекция типа List [X], где X здесь не имеет значения. Результатом понимания в List всегда является другой List . Другие генераторы не имеют отношения.

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

( на самом деле, это даже хуже, потому что каждый генератор создает новую коллекцию; коллекции, созданные вторым генератором, имеют размер каждого элемента ] listOfMaps хотя, и сразу же выбрасываются после использования )

Следующий вопрос - фактически первый, но его было легче перевернуть - как помогает использование проекции .

] Когда вы вызываете проекцию в List , она возвращает новый объект типа Stream (в Scala 2.7.x). Сначала вы можете подумать, что это только ухудшит положение, потому что теперь у вас будет три копии List вместо одной. Но поток предварительно не вычисляется. Это ленивое вычисление .

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

Также, map , flatMap и фильтр из Все потоки возвращают новый поток , что означает, что вы можете связать их все вместе, не создавая единой копии списка , который их создал. Поскольку выражения for с yield используют именно эти функции, использование Stream внутри предотвращает ненужные копии данных.

Теперь предположим, что вы написали что-то вроде этого:

val kvs = for (m <- listOfMaps.projection; kv <-m) yield kv
(Map[A,B]() /: kvs) { ... }

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

Теперь рассмотрим исходную форму ::

(Map[A,B]() /: (for (m <- listOfMaps.projection; kv <-m) yield kv)) 

В этом случае поток используется одновременно с его вычислением. Давайте вкратце посмотрим, как определяется foldLeft для Stream :

override final def foldLeft[B](z: B)(f: (B, A) => B): B = { 
  if (isEmpty) z 
  else tail.foldLeft(f(z, head))(f) 
} 

Если Stream пуст, просто верните аккумулятор. В противном случае вычислите новый аккумулятор ( f (z, head) ), а затем передайте его и функцию в хвост потока Stream .

Один раз f (z, head) выполнено, но не останется ссылки на head . Или, другими словами, ничто в программе не будет указывать на заголовок потока , а это означает, что сборщик мусора может его собрать, освобождая память.

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

Наконец, возникает вопрос, почему третий алгоритм не извлекает из этого выгоду. Ну, третий алгоритм не использует yield , поэтому никаких копий каких-либо данных не делается. В этом случае использование проекции только добавляет косвенный слой.

поэтому никаких копий каких-либо данных не делается. В этом случае использование проекции только добавляет косвенный слой.

поэтому никаких копий каких-либо данных не делается. В этом случае использование проекции добавляет только косвенный слой.