Selección de subconjunto de tamaño K usando la recursión [cerrada] -- recursion campo con functional-programming campo con scala camp codereview Relacionados El problema

Selecting subset of size k using recursion [closed]


2
vote

problema

Español
cerrado. Esta pregunta es off-topic . Actualmente no está aceptando respuestas.

¿Quieres mejorar esta pregunta? Actualizar la pregunta por lo que es on-topic para el intercambio de pila de revisión de código.

cerrado hace 5 años .

Mejorar esta pregunta

A veces necesito implementar algoritmos recursivos que pasan un determinado estado de una llamada recursiva a otra. Por ejemplo, una selección de subconjuntos codiciosos: tenemos un conjunto de objetos candidatos, y seleccionamos un subconjunto de tamaño k con codicia, uno por uno. La elección depende de los objetos ya seleccionados y algún estado constantemente re-computado. Este estado (y el conjunto de candidatos) se puede descartar, una vez que se completa la selección.

  type O /* Individual objects */ type S /* Intermediate state */  def selectSubset(candidates: Seq[O], k: Int): Seq[O] =     selectRec(candidates, Seq[O](), k, initialState(candidates))._2  def selectRec(candidates: Seq[O], acc: Seq[O], k: Int, state: S): (Seq[O], Seq[O], Int, S) =     if (k > 0 && candidates.nonEmpty) {         val next = selectNext(candidates, acc, state)         selectRec(candidates - next, acc + next, k - 1, computeState(state, next))     } else {          (null, acc, null, null) /* (Early) termination */     }  /* Implemented by library users */ def initialState(candidates: Seq[O]): S  def selectNext(candidates: Seq[O], alreadySelected: Seq[O], state: S): O  def computeState(previousState:S, lastSelected:O): S   
  • es la recursión una buena opción aquí?
  • ¿Hay una alternativa limpia a Tuple como el tipo de retorno de la función recursiva? P.ej. Una clase de caso puede ser más legible. En principio, candidates3 , i , y state se puede fusionar en una sola variable, pero eso tampoco parece limpio.
  • ¿Cómo "expresar" (temprano) terminación con tuplas? No nos importa nada más que acc en este punto, pero 9988776655544337 s Look Ugly.
Original en ingles

Sometimes I need to implement recursive algorithms that pass a certain state from one recursive call to another. For example, a greedy subset selection: we have a set of candidate objects, and we select a subset of size k greedily, one-by-one. The choice depends on the already selected objects and some constantly re-computed state. This state (and the set of candidates) can be discarded, once the selection is complete.

type O /* Individual objects */ type S /* Intermediate state */  def selectSubset(candidates: Seq[O], k: Int): Seq[O] =     selectRec(candidates, Seq[O](), k, initialState(candidates))._2  def selectRec(candidates: Seq[O], acc: Seq[O], k: Int, state: S): (Seq[O], Seq[O], Int, S) =     if (k > 0 && candidates.nonEmpty) {         val next = selectNext(candidates, acc, state)         selectRec(candidates - next, acc + next, k - 1, computeState(state, next))     } else {          (null, acc, null, null) /* (Early) termination */     }  /* Implemented by library users */ def initialState(candidates: Seq[O]): S  def selectNext(candidates: Seq[O], alreadySelected: Seq[O], state: S): O  def computeState(previousState:S, lastSelected:O): S 
  • Is recursion a good choice here?
  • Is there a neat alternative to Tuple as the return type of the recursive function? E.g. a case class might be more readable. In principle, candidates, i, and state can be merged into a single variable, but that also doesn't seem neat.
  • How to "express" (early) termination with tuples? We don't care about anything but acc at this point, but nulls look ugly.
        
         
         

Lista de respuestas

1
 
vote

Su lógica es buena, y la API también es bastante sólida. Hay algunos puntos que podrían usar algún trabajo.

Organización

selectRec se puede mover dentro de selectSubset para simplificar ligeramente la estructura.

También es recursivo de la cola, por lo que también puede agregar la anotación. No puedo recordar si se requiere esto, pero incluso si no lo es, es un buen hábito entrar.

Para la legibilidad, recomendaría revertir el if para que el Liner esté en la cláusula 99887776655443333 en lugar de la cláusula 99887776655443334 . En términos generales, es más fácil realizar un seguimiento de qué parte del código pertenece, cuanto más se acerca a la construcción, especialmente si hay un montón de anidación. Aquí no hace una gran diferencia, pero por supuesto, me cambiaría.

Tipos de retorno y amplificador; Misc

Como se está olvidando de todo, excepto acc Cuando regresemos, podemos simplificar el tipo de retorno a solo Seq[O] .

Voy a asumir que Seq fue, por lo que 9988776655544338 necesita para convertirse candidates.filter(_ == next), acc :+ next .

Como se eliminó el nombre del rasgo de la pregunta, voy a usar selectSubset0 .

Terminación anticipada

Lo que ha marcado como una "terminación temprana" es solo "terminación", es el caso base. Limitar esto a la duración de los candidatos no es realmente terminación temprana. Un efecto similar se puede lograr reemplazando selectSubset1 CONTENIDO CON selectSubset3 .

Si desea que los usuarios de la biblioteca terminen temprano, lo que no es una mala idea, una forma es tener 99887766555443315 devolver selectSubset6 en lugar de solo selectSubset7 .

versión refactorizada

  selectSubset8  

Implementación alternativa

Otra alternativa, que es posiblemente más sencilla, es implementar esto como una clase de caso con argumentos de función. Esta implementación es exactamente equivalente a la versión refactorizada anterior, y es posiblemente más sencilla y más fácil de usar.

  selectSubset9  
 

Your logic is good, and the API is pretty solid as well. There are a few point that could use some work.

Organization

selectRec can be moved inside of selectSubset to simplify the structure slightly.

It's also tail recursive, so you might as well add the annotation. I cannot recall if this is required, but even if it's not, it's a good habit to get into.

For readability, I'd recommend reversing the if so that the one-liner is in the if clause rather than the else clause. Generally speaking, it's easier to keep track of what part of the code it belongs to, the closer it is to the construct - particularly if there is a bunch of nesting. Here it doesn't make a big difference, but as a matter of course I'd swap them.

Return Types & Misc

As you are forgetting everything except acc when we return, we can actually simplify the return type to just Seq[O].

I'm going to assume that Seq was intended, so candidates - next, acc + next needs to become candidates.filter(_ == next), acc :+ next.

As the name of the trait was dropped from the question, I'm going to use GreedySubset.

Early Termination

What you have marked as an "early termination" is just "termination", it's the base case. Limiting this to the length of candidates isn't really early termination. A similar effect could be achieved by replacing k in the selectRec call inside selectSubset with k min candidates.length.

If you want to the library users to terminate early, which is not a bad idea, one way is to have selectNext return Option[O] rather than just O.

Refactored Version

import scala.annotation.tailrec  trait GreedySubset {   type O /* Individual objects */   type S /* Intermediate state */    def selectSubset(candidates: Seq[O], k: Int): Seq[O] = {     @tailrec     def loop(candidates: Seq[O], acc: Seq[O], count: Int, state: S): Seq[O] =       if (candidates.isEmpty || count <= 0) acc       else selectNext(candidates, acc, state) match {         case Some(next) =>           loop(candidates.filterNot(_ == next),             acc :+ next,             count - 1,             computeState(state, next))         case None => acc       }     loop(candidates, Seq[O](), k, initialState(candidates))   }    /* Implemented by library users */   def initialState(candidates: Seq[O]): S    def selectNext(candidates: Seq[O], alreadySelected: Seq[O], state: S): Option[O]    def computeState(previousState:S, lastSelected:O): S } 

Alternate Implementation

Another alternative, which is arguably simpler, is to implement this as a case class with function arguments. This implementation is exactly equivalent to the refactored version above, and is arguably simpler and easier to use.

case class GreedySelector[E,S](   initialState: Seq[E] => S,   selectNext: (Seq[E], Seq[E], S) => Option[E], // First argument is candidates   computeState: (S, E) => S) {    def selectSubset(candidates: Seq[E], k: Int): Seq[E] = {     @tailrec     def loop(candidates: Seq[E], acc: Seq[E], count: Int, state: S): Seq[E] =       if (candidates.isEmpty || count <= 0) acc       else selectNext(candidates, acc, state) match {         case Some(next) =>           loop(candidates.filterNot(_ == next),             acc :+ next,             count - 1,             computeState(state, next))         case None => acc       }     loop(candidates, Seq[E](), k, initialState(candidates))   } } 
 
 

Relacionados problema

2  Un generador de laberinto Scala en estilo funcional  ( A scala maze generator in functional style ) 
Me pregunto si hay más que puedo hacer para incorporar más principios de programación de Scala y funcionales idiomáticos. Sé que el laberinto es silencioso, p...

11  Escáner en Scala  ( Scanner in scala ) 
que quería implementar 'código> 99887766555443333 / Código> en Scala. El objetivo de esta clase es: implementar una interfaz de colección SCALA (probable...

8  Generación de mazmorras en Scala  ( Dungeon generation in scala ) 
Recientemente he comenzado a aprender Scala, y mientras me he encontrado con sus conceptos antes (inmutabilidad, tuplas, funciones de primera clase) No estoy ...

6  Implementación de índice de equilibrio  ( Equilibrium index implementation ) 
He encontrado una solución a la problema de índice de equilibrio con la ayuda de las respuestas fuera aquí : val in = Stream(-7, 1, 5, 2, -4, 3, 0) val ...

3  Árbol de búsqueda binaria de Scala  ( Scala binary search tree ) 
En un intento de profundizar en Scala, decidí hacer un BST usando tantos conceptos interesantes como sea posible para explorar todo lo que Scala tiene para of...

4  "Funcionalizando" este método de caminar de árbol y limpiándolo  ( Functionalizing this tree walking method and cleaning it up ) 
Tengo una clase 99887776655443316 que representa un árbol binario de negativo / positivo. Estoy buscando mejorar mi método OdbcConnection7 y hazlo más fun...

2  Scala Mastermind Solver, que es la más scala-ish  ( Scala mastermind solver which is the most scala ish ) 
Estoy tratando de expresar el Kata TDD clásico de Mastermind en la Scala Idiomática que puedo. Aquí hay una suite de prueba escalada: buf1 y mi implemen...

6  Secuencia de fecha de construcción en Scala  ( Construct date sequence in scala ) 
Quiero tener una secuencia de fecha continua como ['2014-01-01', '2014-01-02', ...] Entonces defino un arroyo para hacer eso. def daySeq(start: Date): St...

6  Una implementación de Scala del método de ajuste Java  ( A scala implementation of the java trim method ) 
Soy un principiante de Scala y mirando el método $_{456}$3655443323 de la API de Java. Noté los efectos secundarios, así que intenté implementar una versión...

3  Definiendo la transposición en una colección de colecciones irregulares  ( Defining transpose on a collection of irregular collections ) 
Me pidieron que presentara mi solicitud de revisión de código en https: //stackoverflow.com/questions/10672046/defining-transpose-on-a-collection-of-irregula...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos