Views vs iterators

Question
21

Is immutableHashMapMemo the same as this function I wrote?

  // The memoize method is inspired by
  //  https://clojuredocs.org/clojure.core/memoize
  // Returning a memoized version of a referentially transparent function. The
  // memoized version of the function keeps a cache of the mapping from arguments
  // to results and, when calls with the same arguments are repeated often, has
  // better performance at the expense of higher memory use.
  def memoize[F, T](f: F => T): F => T = {
    val hash = scala.collection.mutable.Map[F, T]()

    def mem(i: F): T = {
      hash.getOrElse(i, locally {
        val v: T = f(i)
        hash(i) = v
        v
      })
    }

    mem
  }
22

Pretty similar. (But not the same, as the “immutable” name part already suggests. :slight_smile:)

23

It probably would be better to use the getOrElseUpdate method though.

2 Likes
24

Do you mean better to use getOrElseUpdate rather than making an explicit update in the 2nd argument of getOrElse? Why better, because it is more efficient, or more readable, or more idiomatic, or …?

25

Yes.

More readable and idiomatic, yes. It could be more efficient too, since lookup (for insertion) could be reduced to once instead of twice.

1 Like
26

It’s certainly nicer and shorter:

   def memo[A, B](f: A => B): A => B =
      val store = mutable.Map.empty[A, B]
      x => store.getOrElseUpdate(x, f(x))

However, it’s probably equivalent performance-wise, given that the current implementation of getOrElseUpdate seems to be:

  def getOrElseUpdate(key: K, op: => V): V =
    get(key) match {
      case Some(v) => v
      case None => val d = op; this(key) = d; d
    }
1 Like
27

Yes, that’s nicer and shorter, thanks for the free refactoring :slight_smile:

BTW is there an advantage of returning an anonymous function rather than than a local function object?

  def memoize[F, T](f: F => T): F => T = {
    val hash = scala.collection.mutable.Map[F, T]()
    def mem(i: F): T = hash.getOrElseUpdate(i, f(i))

    mem
  }

I often suppose that the compiler is optimization, when in fact perhaps it is not. I.e., I normally implicitly suppose that those two forms compile the same way. And if not, then the jvm optimization will treat them the same way after a bit of warming up.

28

I had it handy because I use it as an example in teaching.

1 Like
29

That’s just the obvious default implementation in the Map trait. If you use Scala 2.13, you will get a HashMap as the underlying implementation for a mutable.Map and this class indeed overwrites the getOrElseUpdate method:

So, getOrElseUpdate indeed shaves off a few cycles by avoiding re-computing the hash, re-looking up the index.

1 Like
30

Good point. I trusted IntelliJ to bring me directly to the relevant code, but it’s not that smart…