Pregunta ¿Cómo encontrar estudiantes con las mejores calificaciones en una lista?


Supongamos que tengo una lista de Students. Students tener campos como name, birth date, grade, etc. ¿Cómo encontrarías Students Con el mejor grade en Scala?

Por ejemplo:

Lista (Estudiante ("Mike", "A"), Estudiante ("Pete", "B"), Estudiante ("Paul", A)) "

Quiero tener

Lista (Estudiante ("Mike", "A"), Estudiante ("Paul", A))

Obviamente, puedo encontrar el max grade ("A" en la lista anterior) y luego filter la lista

students.filter (_. grade == max_grade)

Esta solución es O(N) pero corre sobre la lista dos veces. ¿Puedes sugerir una mejor solución?


7
2017-11-11 11:42


origen


Respuestas:


Ejecutar la lista dos veces es probablemente la mejor manera de hacerlo, pero si insistir en una solución que solo se ejecuta una vez, puede usar un doblez (aquí funciona en listas vacías):

(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
}}

Si no está familiarizado con los pliegues, se describen en una respuesta aquí. Son una forma general de acumular algo cuando pasas por encima de una colección (por ejemplo, lista). Si no está familiarizado con la coincidencia, puede hacer lo mismo con isEmpty y head. Si desea que los estudiantes estén en el mismo orden en que aparecieron en la lista original, ejecute .reverse al final.


6
2017-11-11 14:16



Al usar foldLeft, recorre la lista de estudiantes solo una vez:

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))

3
2017-11-11 16:39



Ya hay 6 respuestas, pero aún me siento obligado a agregar mi opinión:

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
  }
}

Esta pequeña clase de caso levantará una Student en un objeto que realiza un seguimiento de la mejor nota y una celda de lista que contiene al estudiante. También tiene en cuenta la lógica de la fusión: si el nuevo estudiante tiene

  • el mismo grado => fusiona al nuevo alumno en la lista de resultados, con el más corto en la parte delantera para la eficiencia; de lo contrario, el resultado no será O (n)
  • grado más alto => reemplazar mejor actual con el nuevo estudiante
  • grado inferior => mantener el mejor actual

El resultado puede ser construido fácilmente con un 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))

PD. Estoy votando tu pregunta, en función del gran número de respuestas generadas


3
2017-11-11 16:59



Puedes usar filter en la lista de estudiantes.

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

Funciona bien también para tipo String


2
2017-11-11 12:49



Después de ordenar, puede usar takeWhile para evitar iterar por segunda vez.

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)

Todavía lo arregla todo, incluso los grados 1, 3, 0 y -1, que no nos interesan, antes de tomar la crema batida, pero es un código corto.

actualizar:

Un segundo enfoque, que se puede realizar en paralelo, es dividir la lista, y tomar el máximo de cada lado, y luego solo el más alto, si hay, sino ambos:

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 }
}

Por supuesto, nos gusta restar importancia al alumno y el método para comparar dos de ellos.

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) 

2
2017-11-11 14:44