How to find students with the best grades in a list?

Question

Suppose, I have a list of Students. Students have fields like name, birth date, grade, etc. How would you find Students with the best grade in Scala?

For example:

List(Student("Mike", "A"), Student("Pete", "B"), Student("Paul", A))"

I want to get

List(Student("Mike", "A"), Student("Paul", A))

Obviously, I can find the max grade ("A" in the list above) and then filter the list

students.filter(_.grade == max_grade)

This solution is O(N) but runs over the list twice. Can you suggest a better solution?

"with the best grades" is vague. What do you want? Top 10? Top 10%? Grade above X? — Kim Stebel, Nov 11 '11 at 12:23
@Kim, whatever gives him the best mark for the assignment that this surely is :) — The Archetypal Paul, Nov 11 '11 at 13:12
My suggestion is to forget this O(N) business, and worrying about how many times you're passing over the List. Unless there are millions of students in your class and the method is time-critical, use the simplest code that does what you want. — Luigi Plinge, Nov 11 '11 at 14:59

score 6 · Accepted Answer · edited May 23 '17 at 12:22

Running over the list twice is probably the best way to do it, but if you insist on a solution that only runs over once, you can use a fold (here works on empty lists):

(List[Student]() /: list){ (best,next) => best match {
  case Nil => next :: Nil
  case x :: rest =>
    if (betterGrade(x,next)) best
    else if (betterGrade(next,x)) next :: Nil
    else next :: best
}}

If you are unfamiliar with folds, they are described in an answer here. They're a general way of accumulating something as you pass over a collection (e.g. list). If you're unfamiliar with matching, you can do the same thing with isEmpty and head. If you want the students in the same order as they appeared in the original list, run .reverse at the end.

score 3 · Answer 2 · answered Nov 11 '11 at 16:39

Using foldLeft you traverse the list of students only once :

scala> students.foldLeft(List.empty[Student]) {
     | case (Nil, student) => student::Nil
     | case (list, student) if (list.head.grade == student.grade) => student::list
     | case (list, student) if (list.head.grade > student.grade) => student::Nil
     | case (list, _) => list
     | }
res17: List[Student] = List(Student(Paul,A), Student(Mike,A))

score 3 · Answer 3 · answered Nov 11 '11 at 16:59

There are already 6 answers, but I still feel compelled to add my take:

case class Lifted(grade: String, students: List[Student]) {
  def mergeBest(other: Lifted) = grade compare other.grade match {
    case  0 => copy(students = other.students ::: students)
    case  1 => other
    case -1 => this
  }
}

This little case class will lift a Student into an object that keeps track of the best grade and a list cell containing the student. It also factors out the logic of the merge: if the new student has

the same grade => merge the new student into the result list, with the shorter one at the front for efficiency - otherwise result won't be O(n)
higher grade => replace current best with the new student
lower grade => keep the current best

The result can then be easily constructed with a reduceLeft:

val result = { 
  list.view.map(s => Lifted(s.grade, List(s)))
    .reduceLeft((l1, l2) => l1.mergeBest(l2))
    .students
}
// result: List[Student] = List(Student(Paul,A), Student(Mike,A))

PS. I'm upvoting your question - based on the sheer number of generated response

Saskia · Answer 4 · 2011-11-11T12:54:47.787

2

You can use filter on the students list.

case class Student(grade: Int)
val students = ...
val minGrade = 5
students filter ( _.grade < minGrade)

Works just fine also for type String

edited Nov 11 '11 at 12:54

answered Nov 11 '11 at 12:49

Saskia

1,046
1
7
23

It doesn't work for String in general. For example `"10" < "2"` is true. – Luigi Plinge Nov 11 '11 at 13:48
@LuigiPlinge Sure, thanks. I had his example in mind, representing grades as single characters. – Saskia Nov 11 '11 at 14:11

score 2 · Answer 5 · edited Jun 20 '20 at 09:12

After sorting, you can use takeWhile to avoid iterating a second time.

case class Student(grade: Int)
val list = List(Student(1), Student(3), Student(2), Student(1), Student(25), Student(0), Student (25))

val sorted = list.sortWith (_.grade > _.grade)
sorted.takeWhile (_.grade == sorted(0).grade)

It still sorts the whole thing, even grades 1, 3, 0 and -1, which we aren't interested in, before taking the whipped cream, but it is short code.

update:

A second approach, which can be performed in parallel, is, to split the list, and take the max of each side, and then only the higher one, if there is - else both:

def takeMax (l: List[Student]) : List [Student] = l.size match {
    case 0 => Nil
    case 1 => l 
    case 2 => if (l(0).grade > l(1).grade) List (l(0)) else 
      if (l(0).grade < l(1).grade) List (l(1)) else List (l(0), l(1))
    case _ => {
      val left = takeMax (l.take (l.size / 2))
      val right= takeMax (l.drop (l.size / 2))
     if (left (0).grade > right(0).grade) left else 
     if (left (0).grade < right(0).grade) right else left ::: right }
}

Of course we like to factor out the student, and the method to compare two of them.

def takeMax [A] (l: List[A], cmp: ((A, A) => Int)) : List [A] = l.size match {
    case 0 | 1 => l 
    case 2     => cmp (l(0), l(1)) match {
      case 0 => l 
      case x => if (x > 0) List (l(0)) else List (l(1))
    }
    case _ => {
      val left = takeMax (l.take (l.size / 2), cmp)
      val right= takeMax (l.drop (l.size / 2), cmp)
      cmp (left (0), right (0)) match {
        case 0 => left ::: right
        case x => if (x > 0) left else right }
     }
}

def cmp (s1: Student, s2: Student) = s1.grade - s2.grade 
takeMax (list, cmp)

+1 for decomposition strategy (though since lists have linear access, it's unlikely to be a performance win; it's still a neat idea). — Rex Kerr, Nov 11 '11 at 16:51

How to find students with the best grades in a list?

5 Answers5

update:

Linked