¿Hay un nombre para este algoritmo?

Question

Disculpas por la pregunta no descriptiva; si puedes pensar en una mejor, soy todo oídos.

Estoy escribiendo algunos Perl para implementar un algoritmo y el código que tengo huele a pescado. Como no tengo experiencia en CS, no tengo mucho conocimiento de los algoritmos estándar en mi bolsillo trasero, pero parece ser algo que podría ser.

permítanme describir lo que estoy haciendo por medio de la metáfora:

• Usted tiene una cinta transportadora de naranjas. Las naranjas te pasan uno por uno. También tiene un suministro ilimitado de cajas planas.
• Para cada naranja, compruébalo. Si está podrido, deséchelo
• Si está bien, colóquelo en una caja. Si no tiene una caja, tome una nueva y contrátela.
• Si la caja tiene 10 naranjas, ciérrela y colóquela sobre una plataforma. No construya uno nuevo.
• Repetir hasta que no tenga más naranjas
• Si usted tiene una caja construida con algunas naranjas en él, cerrarlo y ponerlo en una paleta

Por lo tanto, tenemos un algoritmo para el procesamiento de artículos en una lista, si cumplen algunos criterios, deben agregarse a una estructura que, cuando cumpla con otros criterios, debe ser "cerrada". Además, una vez que la lista ha sido procesada, si hay una estructura 'abierta', también debe 'cerrarse'.

Ingenuamente, supongo que el algoritmo consiste en un ciclo que actúa sobre la lista, con un condicional para ver si el elemento de lista pertenece a la estructura y un condicional para ver si la estructura debe 'cerrarse'. Fuera del ciclo, habría una condición más para cerrar cualquier estructura pendiente.

lo tanto, aquí están mis preguntas:

1. ¿Es esta una descripción de un algoritmo conocido? Si es así, ¿tiene un nombre?
2. ¿Existe una manera efectiva de fusionar la actividad de "cerrar la caja" en un solo lugar, en lugar de una vez dentro del ciclo y una vez fuera del ciclo?

Lo etiqueté como 'Perl' porque los enfoques de Perlish son de interés, pero me interesaría saber de otros idiomas que tengan soluciones claras para esto.

Answer 1

Es un buen ajuste con un enfoque funcional - que está interactuando sobre una corriente de naranjas, probando, agrupando y operando en ellas.En Scala, sería algo así como:

val oranges:Stream[Oranges] = ... // generate a stream of Oranges 

oranges.filter(_.isNotRotten).grouped(10).foreach{ o => {(new Box).fillBox(o)}} 

(grouped hace lo correcto con la caja parcial al final)

Hay probablemente equivalentes Perl.

Answer 2

Parece un poco complicado para el problema que está describiendo, pero suena teóricamente parecido a las Redes de Petri. comprobar Petri Nets on wikipedia

Una aplicación Perl se puede encontrar here

espero que esto le ayudará,

Jerome Wagner

Answer 3

No creo que haya un nombre para este algoritmo. Para una implementación directa, necesitará dos pruebas: una para detectar un cuadro completo mientras está en el ciclo de procesamiento y una después del ciclo para detectar un cuadro parcialmente lleno. La lógica de "cerrar la caja" se puede convertir en una subrutina para evitar duplicarla. Un enfoque funcional podría proporcionar una forma de evitar eso:

use List::MoreUtils qw(part natatime); 

my ($good, $bad) = part { $_->is_rotten() } @oranges; 

$_->dispose() foreach @$bad; 

my $it = natatime 10, @$good; 
while (my @batch = $it->()) { 
    my $box = Box->new(); 
    $box->add(@batch); 
    $box->close(); 
    $box->stack(); 
} 

Answer 4

¿Hay una manera eficaz de unirse la actividad 'de cerrar la caja' en un solo lugar, en lugar de una vez dentro del bucle y una vez fuera del bucle?

Sí. Simplemente agregue "... o no hay más naranjas" a la función "¿la estructura debe cerrarse?". La forma más sencilla de hacer esto es un do/while constructo (técnicamente hablando no es un bucle en Perl, aunque parece que uno):

my $current_container; 
my $more_objects; 
do { 
    my $object = get_next_object(); # Easiest implementation returns undef if no more 
    $more_objects = more_objects($object) # Easiest to implement as "defined $object" 
    if (!$more_objects || can_not_pack_more($current_container) { 
     close_container($current_container); 
     $current_container = open_container() if $more_objects; 
    } 
    pack($object, $current_container) if $more_objects; 
} while ($more_objects); 

en mi humilde opinión, esto en realidad no se gana nada si el close_container() es encapsulado en un método: no hay un gran costo de calidad técnica o de código para llamarlo tanto dentro como fuera del ciclo. En realidad, estoy firmemente convencido de que una solución complicada como lo presentado anteriormente es peor calidad del código sabia que un simple:

my $current_container; 
while (my $more_objects = more_objects(my $object = get_next_object())) { 
    if (can_not_pack_more($current_container)) { # false on undef 
     close_container($current_container); 
    } 
    $current_container = open_container_if_closed($current_container); # if defined 
    pack($object, $current_container); 
} 
close_container($current_container); 

Answer 5

Al mirar los algoritmos, la corriente principal de los CS tienden a manejar mismas situaciones complejas , o emplee muy enfoques complejos (consulte NP-Complete por ejemplo). Además, los algoritmos tienden a centrarse en la optimización. ¿Cómo puede este sistema ser más eficiente? ¿Cómo puedo usar menos pasos en este programa de producción? ¿Cuál es la cantidad más grande de foos que puedo caber en mi barra? etc.

Un ejemplo de un enfoque complejo en mi opinión es de tipo rápido porque la recursión es bastante genial. Sé que es estándar, pero realmente me gusta. Si te gustan los algoritmos, entonces echa un vistazo al Simplex Algorithm - ha sido muy influyente.

Un ejemplo de una situación compleja sería si tiene naranjas que entran, se clasifican en 5 pilas de naranjas, luego se van a 5 lugares diferentes para pelar, luego todas vuelven con otra ruta de naranjas hasta un total de 10 naranjas pilas, luego cada naranja se cortó individualmente, y en caja en grupos de exactamente 2 libras.

Volver a su ejemplo. Su ejemplo es una versión simplificada de flow network. En lugar de tener tantos caminos laterales y opciones, solo hay una ruta con una capacidad de una naranja a la vez. De los algoritmos de red de flujo, el Ford-Fulkerson algorithm es probablemente el más influyente.

Por lo tanto, probablemente pueda ajustar uno de estos algoritmos en el ejemplo presentado, pero sería a través de un proceso de simplificación. Básicamente no hay suficiente complejidad aquí para necesitar alguna optimización. Y no hay riesgo de que se ejecute en una complejidad de tiempo ineficiente, por lo que no es necesario ejecutar el "enfoque perfecto".

El enfoque detallado aquí va a estar bien, y la respuesta aceptada anteriormente hace un buen trabajo sugiriendo una solución funcional real para el problema definido. Solo quería agregar mis 2 centavos con respecto a los algoritmos.