Esiste un nome per questo algoritmo?

Question

Scuse per la domanda non descrittiva; se riesci a pensarne uno migliore, sono tutto orecchie.

Sto scrivendo un po 'di Perl per implementare un algoritmo e il codice che ho odore di pesce. Dal momento che non ho uno sfondo di CS, non ho molta conoscenza degli algoritmi standard nella mia tasca posteriore, ma questo sembra qualcosa che potrebbe essere.

Lasciatemi descrivere quello che sto facendo per mezzo di metafora:

• Si dispone di un nastro trasportatore di arance. Le arance ti passano una ad una. Hai anche una scorta illimitata di scatole piatte.
• Per ogni arancione, controllarlo. Se è marcio, smaltilo
• Se è buono, mettilo in una scatola. Se non hai una scatola, prendine una nuova e costruiscila.
• Se la scatola contiene 10 arance, chiuderla e metterla su un pallet. Non costruirne uno nuovo.
• Ripetere fino a quando non si hanno più arance
• Se si dispone di una scatola costruita con alcune arance in esso, chiuderlo e metterlo su un pallet

Quindi, abbiamo un algoritmo per la lavorazione di articoli in una lista, se soddisfano alcuni criteri, dovrebbero essere aggiunti a una struttura che, quando soddisfa alcuni altri criteri, dovrebbe essere "chiusa". Inoltre, una volta che l'elenco è stato elaborato, se esiste una struttura "aperta", dovrebbe essere "chiuso".

Ingenuamente, presumo che l'algoritmo sia costituito da un ciclo che agisce sulla lista, con un condizionale per vedere se l'elemento della lista appartiene alla struttura e un condizionale per vedere se la struttura deve essere 'chiusa'. Al di fuori del ciclo, ci sarebbe un altro condizionale per chiudere tutte le strutture in sospeso.

Così, qui sono le mie domande:

1. Si tratta di una descrizione di un algoritmo ben noto? Se sì, ha un nome?
2. Esiste un modo efficace per fondere l'attività "chiusura della scatola" in un singolo luogo, anziché una volta all'interno del ciclo e una volta all'esterno del ciclo?

L'ho etichettato come "Perl" perché gli approcci Perlish sono interessanti, ma sarei interessato a conoscere qualsiasi altro linguaggio che abbia soluzioni chiare a questo.

Answer 1

E 'una bella forma con un approccio funzionale - si sta iterazione di un torrente di Arance, testare, raggruppare e operare su di esse.In Scala, sarebbe qualcosa di simile:

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

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

(grouped fa la cosa giusta con la scatola parziale alla fine)

C'è probabilmente equivalenti Perl.

Answer 2

Sembra un po 'troppo complicato per il problema che si sta descrivendo, ma suona teoricamente vicino alle reti di Petri. controllare Petri Nets on wikipedia

Un'implementazione perl può essere trovato here

Spero che questo vi aiuterà,

Jerome Wagner

Answer 3

Non penso che ci sia un nome per questo algoritmo. Per un'implementazione diretta sono necessari due test: uno per rilevare una casella completa mentre si trova nel ciclo di elaborazione e una dopo il ciclo per rilevare una casella parzialmente piena. La logica di "chiusura della scatola" può essere trasformata in una subroutine per evitare di duplicarla. Un approccio funzionale potrebbe fornire un modo per aggirare questo:

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

C'è un modo efficace per unirsi alla 'chiudendo il testo' attività in un unico luogo, al contrario di una volta all'interno del ciclo e una volta fuori del ciclo?

Sì. Aggiungi semplicemente "... o non ci sono più arance" alla funzione "la struttura deve essere chiusa". Il modo più semplice per farlo è un fai/mentre costrutto (tecnicamente parlando non è un ciclo in Perl, anche se sembra 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); 

IMHO, questo in realtà non si vince nulla se il close_container() è incapsulato in un metodo: non ci sono costi tecnici o di codice importanti per chiamarlo sia all'interno che all'esterno del ciclo. In realtà, io sono fortemente del parere che una soluzione contorta come ho presentato sopra è peggiore la qualità del codice saggio che un semplice:

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

Se si esaminano gli algoritmi, i principali quelli CS tendono a gestire molto situazioni complesse oppure impiegare molto approcci complessi (cercare NP-Complete per esempio). Inoltre, gli algoritmi tendono a concentrarsi sull'ottimizzazione. Come può questo sistema essere più efficiente? Come posso utilizzare meno passaggi in questo programma di produzione? Qual è la quantità maggiore di cose che posso inserire nel mio bar? ecc.

Un esempio di un approccio complesso secondo me è un ordinamento rapido perché la ricorsione è piuttosto geniale. So che è standard, ma mi piace davvero. Se ti piacciono gli algoritmi, controlla il Simplex Algorithm - è stato molto influente.

Un esempio di situazione complessa sarebbe se aveste arance che entrano, vengono smistate in 5 pile arancioni, poi sono state spostate in 5 diversi posti da sbucciare, poi tutte sono tornate con un altro percorso di arance per un totale di 10 arance pile, poi ogni arancia era affettata singolarmente e confezionata in gruppi di esattamente 2 libbre.

Torna al tuo esempio. Il tuo esempio è una versione semplificata di flow network. Invece di avere così tanti percorsi e opzioni laterali, esiste un solo percorso con una capacità di un'arancia alla volta. Degli algoritmi della rete di flusso, lo Ford-Fulkerson algorithm è probabilmente il più influente.

Quindi, è possibile adattare uno di questi algoritmi nell'esempio proposto, ma sarebbe attraverso un processo di semplificazione. Fondamentalmente qui non c'è abbastanza complessità da richiedere alcuna ottimizzazione. E non c'è il rischio di correre a una complessità temporale inefficiente, quindi non c'è bisogno di eseguire "l'approccio perfetto".

L'approccio che hai dettagliato andrà bene qui, e la risposta accettata sopra fa un buon lavoro che suggerisce una soluzione funzionale effettiva al problema definito. Volevo solo aggiungere i miei 2 cent per quanto riguarda gli algoritmi.