Ну, это действительно зависит от того, какой тип карты вы используете. Вероятно 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, что, как кажется, имеет место в вашем алгоритме.
EDIT
В дополнение, понимание for / yield берет одну или несколько коллекций и возвращает новую коллекцию. Как часто это имеет смысл, возвращающая коллекция имеет тот же тип, что и исходная коллекция. Так, например, в следующем коде for-compreatsion создает новый список, который затем сохраняется внутри 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, здесь записанный с его синонимом /:, будет вызываться для объекта, возвращаемого для понимания. Помните, что : в конце оператора инвертирует порядок объекта и параметров.
Теперь давайте рассмотрим, что это за объект, для которого вызывается foldLeft. Первый генератор этого понимания - m <- listOfMaps. Мы знаем, что listOfMaps - это коллекция типа List [X], где X на самом деле не имеет значения. Результат для понимания на List всегда является другим List. Другие генераторы не имеют отношения.
Итак, вы берете это List, получаете все ключи / значения внутри каждого Map, который является компонентом этого List, и создаете новый List со всем этим. Вот почему вы дублируете все, что у вас есть.
( на самом деле, это даже хуже, потому что каждый генератор создает новую коллекцию; коллекции, созданные вторым генератором, имеют размер каждого элемента listOfMaps и сразу же отбрасываются после использования )
Следующий вопрос - фактически первый, но его было проще перевернуть, - как помогает использование projection.
Когда вы вызываете projection для List, он возвращает новый объект типа Stream (в Scala 2.7.x). Сначала вы можете подумать, что это только ухудшит ситуацию, потому что теперь у вас будет три копии List вместо одной. Но 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 для 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 добавляет только слой косвенности.