Есть ли название для этого алгоритма?

Ответ 1

Хорошо сочетается с функциональным подходом - вы повторяете поток апельсинов, тестируете, группируете и действуете на них. В Scala это будет что-то вроде:

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

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

(grouped делает правильную вещь с частичным полем в конце)

Вероятно, существуют эквиваленты Perl.

Ответ 2

Существует ли эффективный способ объединения активности "закрытия ящика" в одно место, а не один раз внутри цикла и один раз за пределами цикла?

Да. Просто добавьте "... или больше нет апельсинов" к функции "должна ли быть закрыта структура". Самый простой способ сделать это - построить do/while (технически говоря, это не цикл в Perl, хотя он выглядит как один):

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

ИМХО, это действительно ничего не выиграет, если close_container() инкапсулирован в метод - нет никаких существенных технических или качественных затрат на качество для вызова как внутри, так и вне цикла. На самом деле, я твердо придерживаюсь мнения, что сложное обходное решение, как я изложил выше, - это качество кода ВОСЕМЫ, чем просто:

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

Ответ 3

Похоже, что проблема, которую вы описываете, немного сложна, но она теоретически близка к Петри Нэтсу. проверьте Петри Сети по википедии

Реализация perl может быть найдена здесь

Надеюсь, это поможет вам,

Джером Вагнер

Ответ 4

Я не думаю, что есть имя для этого алгоритма. Для прямой реализации вам понадобятся два теста: один для обнаружения полного поля, в то время как в цикле обработки и один после цикла для обнаружения частично полного поля. Логика "закрытия ящика" может быть превращена в подпрограмму, чтобы избежать ее дублирования. Функциональный подход может обеспечить такой способ:

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

Ответ 5

При взгляде на алгоритмы, основной поток CS, как правило, обрабатывают очень сложные ситуации или используют очень сложные подходы (посмотрите NP-Complete для пример). Более того, алгоритмы имеют тенденцию фокусироваться на оптимизации. Как эта система может быть более эффективной? Как я могу использовать меньше шагов в этом производственном графике? Какое количество фосов, которые я могу поместить в мой бар? и др.

Примером сложного подхода, на мой взгляд, является быстрый вид, потому что рекурсия довольно гениальна. Я знаю, что это стандарт, но мне это очень нравится. Если вам нравятся алгоритмы, ознакомьтесь с Simplex Algorithm - это было очень влиятельным.

Примером сложной ситуации было бы, если бы у вас были апельсины, которые вошли, отсортированы по 5 апельсиновым сваям, затем отправились в 5 разных мест, чтобы очиститься, а затем все вернулись с другим путем апельсинов до 10 оранжевых свай, затем каждый апельсин индивидуально нарезался и помещался в коробки ровно в 2 фунта.

Вернемся к вашему примеру. Ваш пример - упрощенная версия проточной сети. Вместо того, чтобы иметь так много боковых путей и опций, есть только один путь с емкостью по одному апельсину за раз. Из алгоритмов проточной сети алгоритм Ford-Fulkerson, вероятно, самый влиятельный.

Таким образом, вы, вероятно, можете подгонять один из этих алгоритмов в представленный пример, но это будет через процесс упрощения. В принципе, здесь не требуется сложной оптимизации. И нет никакого риска работать при неэффективной временной сложности, поэтому нет необходимости запускать "идеальный подход".

Подход, который вы подробно описали, здесь будет хорошо, и принятый ответ выше делает хорошую работу, предлагая фактическое функциональное решение определенной проблемы. Я просто хотел добавить свои 2 цента в отношении алгоритмов.