How to find students with the best grades on the list?

Question

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

For example:

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

I want to receive

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

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

  students.filter (_. grade == max_grade) 

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

Answer 1

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

 (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 not familiar with folds, they are described in the answer here . They are a common way to accumulate something when you pass a collection (like a list). If you are not familiar with the match, you can do the same with isEmpty and head . If you want students to be in the same order as the original list, run .reverse at the end.

Answer 2

With foldLeft, you only see the students list 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)) 

Answer 3

There are already 6 answers, but I am still forced to add my suggestion:

 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 class of small cases will raise Student to an object that tracks the best class and the cell in the list where the student is located. It also explains the merge logic: if a new student has

• same class => combine a new student in the list of results, and a shorter one for efficiency - otherwise the result will not be O (n)
• higher grade => best replaced with a new student
• lower class => save the best time

The result can be easily built using 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 raise your question - based on the net number of generated answers

Answer 4

You can use filter in the student list.

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

Also works well for type String

Answer 5

After sorting, you can use takeWhile to avoid repeating the 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) 

He still sorts everything, even grades 1, 3, 0 and -1, which we are not interested in before taking whipped cream, but this is a short code.

update:

The second approach, which can be performed in parallel, is to split the list and take the maximum of each side, and then only the higher, if any else else:

 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 would like to separate the student and the method of comparing the 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)