Scala MaxBy's Tuple

Question

I have a Seq of Tuples, which represents a word count: (count, word)

For Example:

(5, "Hello")
(3, "World")

My Goal is to find the word with the highest count. In a case of a tie between 2 words, I'll pick the word, which appears first in the Dictionary (aka Alphabetical order).

val wordCounts = Seq(
  (10, "World"),
  (5, "Something"),
  (10, "Hello")
)

val commonWord = wordCounts.maxBy(_._1)
print(commonWord)

Now, this code segment will return (10, "World"), because this is the first tuple that have the maximum count.

I could use .sortBy and then .head, but I want to be more efficient.

My question is there any way to change the Ordering of the maxBy, in order to achieve the desired outcome.

Note: I prefer not to use .sortBy, because it's O(n*log(n)) and not O(n). I know that I can use .reduce, but I want to check if I can adjust .maxBy?

Scala Version 2.13

uralian · Accepted Answer · 2020-10-19 14:53:05Z

4

Functions like max, min, maxBy and minBy use implicit Ordering that defines the comparison between two items. There's a default implementation of Ordering for Tuple2, however the problem is it will apply the same comparison to both elements – while in your case you need to use greater than for _._1 and less than for _._2. However you can easily solve this by inverting the first element, so this does the trick:

wordCounts.minBy(x => (-x._1, x._2))

answered Oct 19, 2020 at 14:53

uralian

783 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Marth · Accepted Answer · 2020-10-19 14:56:26Z

2

You can create your own Ordering by using orElse() to combine two Orderings together:

// can't use .orElseBy() because of the .reverse, so this is a bit verbose
val countThenAlphaOrdering =
  Ordering.by[(Int, String), Int](_._1)
          .orElse(Ordering.by[(Int, String), String](_._2).reverse)

Or you can use Ordering.Tuple2 in this case:

val countThenAlphaOrdering = Ordering.Tuple2(Ordering[Int], Ordering[String].reverse)

Then

val wordCounts = Seq(
  (10, "World"),
  (5, "Something"),
  (10, "Hello"),
)

wordCounts.max(countThenAlphaOrdering)  // (10,Hello): (Int, String)

edited Oct 19, 2020 at 14:56

answered Oct 19, 2020 at 14:51

Marth

24.9k3 gold badges68 silver badges76 bronze badges

1 Comment

Bar Bokovza Over a year ago

Works properly, and much more easier to maintain.

Lumintorious · Accepted Answer · 2020-10-19 14:58:31Z

implicit val WordSorter: Ordering[(Int, String)] = new Ordering[(Int, String)]{
    override def compare(
      x: (Int, String), 
      y: (Int, String)
    ) = {
      val iComp = implicitly[Ordering[Int]].compare(x._1, y._1)
      if iComp == 0
        -implicitly[Ordering[String]].compare(x._2, y._2)
      else
        iComp
    }
  }
  
  val seq = Seq(
    (10, "World"),
    (5, "Something"),
    (10, "Hello")
  )

  def main(args: Array[String]): Unit = println(seq.max)

You can create your own Ordering[(Int, String)] implicit whose compare method returns the comparison of the numbers in the tuples if its not zero and the comparison of the strings negatively if the int comparison is zero. Using implicitly defined Ordering[Int] and Ordering[String] for modularity if you want to change the behaviour later on. If you don't want to use those, you can just replace implicitly[Orderint[Int]].compare(x._1, y._1) with x._1.compareTo(y._1) and so on.

Collectives™ on Stack Overflow

Scala MaxBy's Tuple

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related