Home / Questions / 30447
Accepted
ChemaCortes
Asked: 2020-10-29 12:26:26 +0800 CST 2020-10-29 12:26:26 +0800 CST

Get all the elements of a list that minimize a function

  • 772

Let's say we have a "measure" function with the signature:

def medida(x: A): Double

And we want to obtain the elements of a set that minimize the measure function. minApplying the or methods minByI can obtain the first element that minimizes the function; but I'm interested in getting all the minimal elements.

One way to solve it would be to go through all the elements again to filter the ones with the minimum size, something like this:

val conjunto: Set[A] = ...
val minimo: Double = conjunto.map(medida).min
val resultado: Set[A] = conjunto.filter(medida(_) == minimo)

But you would be calculating the measure function twice for each element, which is something you want to avoid.

You could do a mapping to calculate the measure only once:

val conjunto: Set[A] = ...
val mapeo: Map[A, Double] = conjunto.map(x => x -> medida(x)).toMap
val minimo: Double = mapeo.values.min
val resultado: Set[A] = mapeo.keySet.filter(mapeo(_) == minimo)

Other than that it looks more complicated, I would loop through the entire array twice, which in my case is quite a large array.

I was thinking of solving the problem dynamically ( using state variables) or using some greedy algorithm . Without going so far, in the end I have come up with a solution that I will add as an answer.

The question: Is there a better way to get all the minimal elements of an array, that is both functional and efficient?

Edit 2016-11-29 (from @willena's answer

Application the idea of ​​using foldLeft:

val resultado: Set[A] = conjunto.foldLeft((Set[Double](), Double.PositiveInfinity) {
  case ((conj, minimo), x) =>
    val m = medida(x)
    if (m < minimo) (Set(x), m)
    else if (m == minimo) (conj + x, minimo)
    else (conj, minimo)
}._1
algoritmos

2 Answers

  1. Best Answer

    You can loop through your set of values ​​while accumulating the values ​​you're interested in using the foldLeft. With this approach you get the following advantages:

    • The set is traversed only once.
    • Values ​​you are not interested in are discarded instantly.
    • It does not create a result set as large as the original.

    It would be something like this:

    val miConjunto = List(3, 5, 8, 8, 6, 6, 4, 3, 2, 9)

def funcionCostosa(n: Int) = n % 3

miConjunto.foldLeft((List[Int](), Int.MaxValue)) { case ((lista, mejorResultado), candidato) =>
  funcionCostosa(candidato) match {
    case res if res < mejorResultado =>
      (List(candidato), res)
    case res if res == mejorResultado =>
      (candidato :: lista, mejorResultado)
    case _ =>
      (lista, mejorResultado)
  }
}

    The result of foldLeftis (List(9, 3, 6, 6, 3, 9), 0).

    A possible improvement to the above code is to parameterize the compare function of the result and the initial result to compare with.

    • 2

  2. The solution I can think of is to group the elements of the array based on the measurement result:

    val conjunto: Set[A] = ...
val medidas: Map[Double, Set[A]] = conjunto.groupBy(medida)
val resultado: Set[A] = medidas(medidas.keys.min)

    I have not done tests to verify its efficiency.

    • 0