Вызывает ли filterKeys переполнение стека? - PullRequest
Новая
       14

Вызывает ли filterKeys переполнение стека?

6 голосов
/ 31 января 2012

Как я понимаю, метод filterKeys из MapLike создает обертку поверх исходной карты. Таким образом, если я выполню код ниже, m будет цепочкой из 10K упаковщиков и исходной карты. 

var m = Map(1 -> "one", 2 -> "two")
for(1 <- 0 until 10000) {m = m.filterKeys(_%2 == 0)}

Теперь я подумал, что вызов m.contains вызвал переполнение стека, но это не происходит. Не могли бы вы объяснить, что происходит в этом случае?

Ответы [ 3 ]

2 голосов
/ 31 января 2012

Мне удалось вызвать переполнение стека следующим образом (Scala 2.9.1) 

scala> var m = Map(1 -> "one", 2 -> "two")
scala> for (_ <- 0 until 1000000) { m = m.filterKeys(_ % 2 == 0) }
scala> m.contains(1)
huge stack trace

Конечно, вы можете избежать трассировки стека, заставив filterKeys фактически выполнять свою работу вкаждый шаг: 

scala> var m = Map(1 -> "one", 2 -> "two")
scala> for (_ <- 0 until 1000000) { m = Map() ++ m.filterKeys(_ % 2 == 0) }
scala> m.contains(1)
res1: Boolean = false
2 голосов
/ 31 января 2012

Я не смог воспроизвести переполнение стека, но вот что происходит: 

override def filterKeys(p: A => Boolean): Map[A, B] = new DefaultMap[A, B] {
  override def foreach[C](f: ((A, B)) => C): Unit = for (kv <- self) if (p(kv._1)) f(kv)
  def iterator = self.iterator.filter(kv => p(kv._1))
  override def contains(key: A) = self.contains(key) && p(key)
  def get(key: A) = if (!p(key)) None else self.get(key)
}

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

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

1 голос
/ 31 января 2012

Ваш цикл выполняется только 1 раз, если я копирую дословно.Из-за этого вы создаете только одну оболочку, поэтому то, что должно было быть цепочкой из 10000 оболочек, это просто цепочка из 1. Это может быть опечатка, но цикл, 

for(1 <- 0 until 10000) {m = m.filterKeys(_%2 == 0)}

, вероятно, долженбыть 

for(i <- 0 until 10000) {m = m.filterKeys(_%2 == 0)}

Кроме этого, Даниил прав;fitlerKeys производит то, что по сути является оберткой.Это заняло у меня более 10 тысяч итераций, но мне удалось создать StackOverflowError.

...