3
\$\begingroup\$

I'm trying to pick Scala up. This is a simple heuristic that checks a similarity value between two sets. I've done this a million times in Java or Python. The function works, but I'm certain I am not doing this "the Scala way".

val a : List[Int] = List(1,1,2,2,3)
val b : List[Int] = List(1,2,3,4,5)

def calculateBags(a: List[Int], b: List[Int]): Double = {
    val a_counts = a.groupBy(x=>x).map(y=> y._1->y._2.size)
    val b_counts = b.groupBy(x=>x).map(y=> y._1->y._2.size)
    var count = 0
    a_counts.foreach{ x=>
        var k = x._1
        var t = x._2
        if (b_counts.contains(k)) {
            count+= Math.min(t,b_counts(k))
        }
    }
    (count.toDouble)/(a.size+b.size)
}
\$\endgroup\$
4
\$\begingroup\$

Idiomatic Scala Style

When defining a val, var, or a function use camelCase.

    // :)
    val aCounts = ... 

    // :(
    val a_counts = ...

When using an infix operator add a space on both sides of it.

    // :)
    x => x 
    i -> j
    foo * boo

    // :(
    x=>x
    i->j
    foo*boo

Code

Here is your code with all of the changes I would make included (explanation follows):

    import Math.min

    def calculateBags(a: List[Int], b: List[Int]): Double = {
        val countsByElem =
            (xs: List[Int]) =>
                xs.groupBy(elem => elem).map { case (e, xss) => e -> xss.length }

        val aCounts = countsByElem(a)
        val bCounts = countsByElem(b)

        def addMin(count: Int, x: (Int, Int)): Int = {
            val (k, t) = x
            val v = bCounts getOrElse(k, 0)
            count + min(v, t)
        }

        val len = (a.length + b.length).toDouble

        (0 /: aCounts)(addMin) / len
    }
  • The first thing I did was define a function literal, countsByElem. I mostly did this to show you that such expressions are possible and sometimes very useful. The advantage in this case is that instead of duplicating the same logic in multiple places, we just define a function and call it as necessary. If we then need to make a change to the logic we can do so in one place. Another advantage is that a future reader of your code can instantly tell aCounts and bCounts are calculated with the same set of operations (though with different lists). A disadvantage is that defining this function literal adds more lines of code to your function overall. But we will make up for that later :)

  • Next, I've defined a function which for lack of a better name I've called addMin. The parameters have the same names as you used in your original code: count is the accumulator and x is the ith element of aCounts. The notable features of this function are:

    • In the first line we unpack the tuple value x with some syntactic sugar
    • The next line (starting val v = ...) attempts to retrieve a value from the bCounts map based on the key k. If there is no value associated with k in bCounts the integer value 0 is returned instead.
  • Lastly we utilize a foldLeft which in the code is designated by the /:. It is a bit hard to concisely explain the set of fold methods that Scala offers. But a nice tutorial on them can be found here. Brief explanation: we pass each element in aCounts along with an accumulator to addMin. If we were to 'unroll' some arbitrary fold-left it might look something like this:

    // Scala-esque psuedocode to explain a fold ...
    val foldResult = {
        val res0 = func(0,    xs(0))
        val res1 = func(res0, xs(1))
        val res2 = func(res1, xs(2))
        // ...
        func(penultimateResult, xs.last)
    }
    

Anyway, hope this helps!

\$\endgroup\$
2
  • \$\begingroup\$ Very helpful thanks. I'll give it a try and come back later! \$\endgroup\$
    – steve
    Jan 6 '15 at 10:44
  • \$\begingroup\$ I know how to modify the question code to make it work with sets of Strings. However, what would you change in the answer code? Thx \$\endgroup\$ May 10 '17 at 0:34
4
\$\begingroup\$

Here is a more compact version that more fully utilizes the Collections API and Generics:

def calculateBags[T](as: Seq[T], bs: Seq[T]): Double = as.intersect(bs).size / as.union(bs).size.toDouble
  • Note the use of Seq instead of List, as it is a supertype trait that accomplishes the same objective

  • Also note the use of generics instead of explicit types, which requires both collections to be of the same type. Alternatively, we could have used the following if we wanted to enable comparisons of disparate types.

    def calculateBags(as: Seq[AnyVal], bs: Seq[AnyVal])

  • Lastly, (stats nit, not Scala related) I would calculate jaccardSimilarity as 0.6 for collections (1,1,2,2,3) and (1,2,3,4,5), not 0.3, as calculateBags does, which is accomplished by adding the distinct function following intersect and union respectively:

    def jaccardSimilarty[T](xs: Seq[T], ys: Seq[T]) = xs.intersect(ys).distinct.size / xs.union(ys).distinct.size.toDouble

\$\endgroup\$
3
\$\begingroup\$

Starting with some minor style point...

In Scala code it is traditional to name lists xs, ys, as, bs and their contents x, y, a, b and so on. So the first 3 lines of your function would, in that common style, look like

def calculateBags(as: List[Int], bs: List[Int]): Double = {
    val a_counts = as.groupBy(a => a).map(a => a._1 -> a._2.size)
    val b_counts = bs.groupBy(b => b).map(b => b._1 -> b._2.size)

Also note that

  1. I used the same variable name in both groupBy and map. Those are two separate closures so can reuse the same single-item name.
  2. I placed spaces around the operators. Scala can be dense enough (and also permits non-alphanumeric characters in variable and function names) without more density.

With regard to idiomatic, more functional-style Scala

  1. You are doing the same thing to both a_counts and b_counts. Duplication that could be eliminated.
  2. You have a loop updating a mutable variable. A for...yield block would be one more idiomatic (and functional) way to do this.
  3. If one of your lists has values not present in the other, you are wasting effort totalling counts of those values.

(Your k and t variables are mutable vars rather than immutable vals, to no purpose, but I shan't be keeping them. But never use a var unless you really have to. Go immutable by default.)

One way to address point one is in a for...yield block. This code

for (xs <- List(as, bs)) yield ( xs.groupBy( x => x ).map(y=> y._1->y._2.size) )

Returns a list of two maps. If sorted by size, the map with fewer keys will be first in the list. This done, point 2 (loop updating mutable variable) could be made more idiomatic with another for...yield block. Putting these together, one way of addressing my points is this:

def calculateBags(as: List[Int], bs: List[Int]): Double = {
    val ms = (for (xs <- List(as, bs)) yield ( xs.groupBy( x => x ).map(y=> y._1->y._2.size))) sortBy ( _.size )

    val counts = for (m <- ms(1) if ms(0) contains m._1) yield Math.min(m._2, ms(0)(m._1))

    counts.sum.toDouble / (as.size + bs.size)
}   

I would like to draw particular attention to the second for...yield block. By adding a filter to the list expression, I have no need for your inner if block. I also have no need of mutable state; I simply generate a list of counts and add that up.

However, while this is definitely more idiomatic Scala and does a little to reduce unnecessary work, it really does nothing to address point 3.

One way to do this would be

  1. Take the smaller of the input lists and create a map of values and their number in the list, as in your code or mine.
  2. Filter the larger list to remove any items which are not keys in the map generated in step 1.
  3. Create a map from the larger list.
  4. Iterate through one map comparing its counts with those in the other map
  5. Proceed from here...

One way to do step 1 is this:

val (xs, ys) = if (as.size <= bs.size) (as, bs) else (bs, as)

where xs is obviously the smaller list (if both are not the same size)

But if you filter the larger list and then create a map, you are traversing that list twice, so not saving much work. one way to only traverse the larger list once would be to fall back to mutability, something like

var y_counts: scala.collectionsMap[Int, Int] = Map()
for (y <- ys if x_counts contains y) {
    y_counts.update(y, if (y_counts contains y) {y_counts(y) + 1} else 1)
}

Note the way the if...else block is placed, rather than

if (y_counts contains y) { 
    y_counts.update(y, y_counts(y) + 1)
} else {
    y_counts.update(y, 1)
}

There are also ways to do this with immutable state (which would always be my preference if it can be made to perform well). One is to forget step 2 (filtering the list) and do step 3 (creating the second map) by folding over the larger list and using an immutable map as an accumulator. That may be a more advanced topic for you and I will leave it for now.

EDIT: Ok, so I decided to give an efficient, functional-style example of folding.

def calculateBags(as: List[Int], bs: List[Int]): Double = {
  val (xs, ys) = if (as.size <= bs.size) (as, bs) else (bs, as)

  val xCounts = xs.groupBy(x => x).map(x => x._1 -> x._2.size) 

  val mins = ys.foldLeft(Map(): Map[Int, Int]) {(ms, y) =>
    lazy val yCount: Int = ms.getOrElse(y,0)
    if (xCounts.contains(y) && xCounts(y) > yCount) {
      ms.updated(y, yCount + 1)
    } else {
      ms
    } 
  }

  mins.valuesIterator.sum.toDouble / (as.size + bs.size)
}   

Salient points:

  • I make a map of the counts in the shorter list
  • I fold over the longer list, building a map of the minimums. This means I only traverse the second list once.
  • The fold is given an empty map as a seed value. As we traverse the list, this will build up a map of minimum counts.
  • In each iteration of the fold, if the current item in the longer list is not in the shorter map, we do nothing more and simply return the accumulator unchanged (it will be used in the next iteration).
  • We also do nothing (passing on the accumulator unchanged) if the accumulator's count of how many y we have seen in ys has risen to equal the count of y in xs (that is, we have reached the minimum count of y in both lists and can ignore any more of y in ys).
  • Otherwise, we return an updated version of the accumulator (increasing by 1 the count of y seen in ys).
  • I make yCount a lazy val because the code needs the value of ms.getOrElse(y, 0) twice (so I don't want to call getOrElse twice) but if y is not a key in xCounts then we don't need to look it up at all. Lazy vals are only evaluated when asked for.
  • Once mins has all the minimum counts in it, I add them up. However, I use valuesIterator.sum rather than values.sum because the latter would traverse the entire map, turning it into a list, then traverse the list again. The iterator is lazier, only moving to the next key in the map when the next value in the iterator is requested.

So that is how to use folds and iterators to process collections efficiently, traversing them as few times as possible. And how to do that without mutable state.

Note: I did it entirely with immutable state to show it can be done. However, using one mutable variable inside a function, where nothing else can see it, is not a functional sin. Updating immutable maps (that is, returning a new copy* can be just as fast as using a mutable map, depending on the usage pattern. Really, you should test both options with a range of inputs to compare. The (slightly) mutable version can be done simply by using a mutable map and the update method - very small change to the code.

\$\endgroup\$
3
  • \$\begingroup\$ Very helpful as well thanks. Point 3 isn't an issue in this case but thanks for solving the problem as it gives me insights into how to do it for other times :-) \$\endgroup\$
    – steve
    Jan 6 '15 at 10:46
  • 1
    \$\begingroup\$ In terms of performance I was considering not only wasted CPU cycles but also RAM. If you fully generate a counts map for the second list, you generate a map which might contain twice as many integers (keys and counts) as in the list. And you traverse the list, then traverse the map. Wasteful when you can traverse the list just once and only build a map as big as you need. \$\endgroup\$
    – itsbruce
    Jan 6 '15 at 11:54
  • \$\begingroup\$ So I added an example of that ;) \$\endgroup\$
    – itsbruce
    Jan 6 '15 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.