Ответ 1
Ну, это действительно зависит от того, какой фактический тип Карты вы используете. Вероятно, 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
A Stream
не вычисляет значение, пока оно не понадобится. Сборщик мусора должен также собирать неиспользуемые элементы, если вы не держите ссылку на голову Stream
, что, кажется, имеет место в вашем алгоритме.
ИЗМЕНИТЬ
Дополняя, понимание for/yield принимает одну или несколько коллекций и возвращает новую коллекцию. Так часто, как это имеет смысл, возвращаемая коллекция имеет тот же тип, что и исходная коллекция. Так, например, в следующем коде, for-comprehension создает новый список, который затем сохраняется внутри l2
. Это не val l2 =
, который создает новый список, но для понимания.
val l = List(1,2,3)
val l2 = for (e <- l) yield e*2
Теперь посмотрим на код, используемый в первых двух алгоритмах (минус ключевое слово mutable
):
(Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv))
Оператор foldLeft
, написанный с его синонимом /:
, будет вызван на объект, возвращенный для понимания. Помните, что a :
в конце оператора инвертирует порядок объекта и параметры.
Теперь рассмотрим, что это за объект, на который вызывается foldLeft
. Первый генератор в этом понимании - m <- listOfMaps
. Мы знаем, что listOfMaps
представляет собой набор типа List [X], где X здесь не имеет особого значения. Результатом понимания для List
всегда является другое List
. Другие генераторы не имеют значения.
Итак, вы берете этот List
, получаете все ключи/значения внутри каждого Map
, который является компонентом этого List
, и создавайте новый List
со всем этим. Вот почему вы дублируете все, что у вас есть.
(на самом деле это еще хуже, потому что каждый генератор создает новую коллекцию, а коллекции, созданные вторым генератором, - это всего лишь размер каждого элемента listOfMaps
, и они сразу же отбрасываются после использования)
Следующий вопрос - на самом деле, первый, но было проще инвертировать ответ - как помогает использование projection
.
Когда вы вызываете projection
на List
, он возвращает новый объект типа Stream
(на Scala 2.7.x). Сначала вы можете подумать, что это только усугубит ситуацию, потому что теперь у вас будет три копии List
, а не один. Но a Stream
не предварительно вычисляется. Он лениво вычисляется.
Это означает, что результирующий объект Stream
не является копией List
, а скорее функцией, которая может быть использована для вычисления Stream
при необходимости. После вычисления результат будет сохранен таким образом, чтобы его не нужно было вычислять снова.
Кроме того, Map
, flatMap
и filter
для Stream
все возвращают новый Stream
, что означает, что вы можете объединить их все вместе, не создавая единственную копию созданного ими List
, Поскольку для -знания с помощью yield
используют эти самые функции, использование Stream
внутри предотвращает ненужные копии данных.
Теперь предположим, что вы написали что-то вроде этого:
val kvs = for (m <- listOfMaps.projection; kv <-m) yield kv
(Map[A,B]() /: kvs) { ... }
В этом случае вы ничего не набираете. После присвоения Stream
до kvs
данные еще не скопированы. Однако, если вторая строка выполнена, kvs будет вычислять каждый из своих элементов и, следовательно, будет содержать полную копию данных.
Теперь рассмотрим исходную форму::
(Map[A,B]() /: (for (m <- listOfMaps.projection; kv <-m) yield kv))
В этом случае Stream
используется одновременно с вычислением. Давайте кратко рассмотрим, как foldLeft
для a 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)
), а затем передайте его и функцию в tail
Stream
.
Как только f(z, head)
выполнит, однако, не будет никакой ссылки на head
. Или, другими словами, ничто в программе не будет указывать на head
Stream
, а это значит, что сборщик мусора может его собирать, освобождая память.
Конечным результатом является то, что каждый элемент, созданный для понимания, будет существовать только кратко, в то время как вы используете его для вычисления аккумулятора. Вот как вы сохраняете копию всех ваших данных.
Наконец, возникает вопрос, почему третий алгоритм не извлекает из этого выгоду. Ну, третий алгоритм не использует yield
, поэтому копия каких-либо данных не производится. В этом случае использование projection
добавляет только слой косвенности.