这个算法有一个名称吗？

Question

抱歉这个问题描述不清楚，如果您有更好的问题，请告诉我。

我正在编写一些Perl代码来实现一个算法，但我的代码似乎有些问题。由于我没有计算机科学背景，所以我不太了解标准算法，但这似乎是一种可能的算法。

让我用比喻来描述一下我正在做的事情：

• 你有一条橙子传送带，橙子一个接一个地经过你。你还有一个无限供应的平板盒子。
• 对于每个橙子，请检查它。如果腐烂，请处理掉。
• 如果它很好，请将其放在盒子里。如果你没有盒子，请拿一个新的盒子并构造它。
• 如果盒子里有10个橙子，关闭它并将其放在托盘上。不要构造新的盒子。
• 重复此过程，直到没有橙子为止。
• 如果你有一个已经构造的盒子里面装有一些橙子，请封闭它并将其放在托盘上。

所以，我们有一个处理列表中项目的算法，如果它们符合某些条件，它们应该被添加到一个结构中，当它满足某些其他条件时，应该被“关闭”。此外，一旦列表已经被处理完，如果有一个“打开”的结构，也应该被“关闭”。

天真地，我假设算法由循环作用于列表、有一个条件判断是否将列表元素放入结构中和有一个条件判断是否需要“关闭”结构。循环外，还会有一个条件判断来关闭任何未完成的结构。

所以，这里是我的问题：

1. 这是一个众所周知的算法吗？如果是，它有一个名字吗？
2. 是否有一种有效的方法将“关闭盒子”活动合并到一个地方，而不是在循环内部和循环外部各一次？

我将这个标签为“Perl”，因为Perlish方法很有趣，但我也很想听听其他语言对这个问题的巧妙解决方案。

- Dancrumb

---

非常非常清晰地解释了你所要求的内容，给你点赞。 - DGH

从现在开始，这将被称为“Dancrumb过程”。我将开始创建维基页面。 - mob

1. 不。
2. 创建一个名为 close_box() 的函数，并在两个地方调用它。这就是函数的作用，这样做没有任何道德问题 :)

- j_random_hacker

@j_random_hacker：真的，用一个函数可以简化它，但是这确实给粗心的维护人员留下了第二个函数调用被删除或进入错误作用域的机会。我承认你不能避免所有的问题，但我还在想是否有一种方法可以将函数调用放在一个地方。 - Dancrumb

正如它所发生的那样，Perl允许你将continue块附加到循环末尾 - 你可以在里面调用if ($n == 10 || $no_more_oranges) { close_box() }一次。但是，continue是一个很少使用的结构，我猜更容易混淆未来的维护者，而不是调用函数两次。 - j_random_hacker

Answer 1

这个功能性方法非常适合 - 你可以迭代一个橘子流，测试、分组和操作它们。在Scala中，代码可能是这样的：

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

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

(grouped在处理结尾的部分框时做得很好)

可能会有Perl的等效物。

- The Archetypal Paul

---

我还没有真正开始学习Scala...但是new Box.fillBox(o)是否只为组中的第一个项目创建一个新盒子，还是会为每个元素创建一个新盒子？ - Mark Peters

哦，我猜 o 实际上是一堆橙子的集合？如果是这样的话，那就有意义了。 - Mark Peters

对于函数式编程的支持者来说，功能型方法是首选之一！ - Alexandre C.

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

- DVK

---

为了给听众中不了解 Perl 语言的人澄清一条评论：当然，在实际应用中，do/while 循环是一种循环方式，但是 do 块在循环控制词如 next 和 last 方面并不是一个"循环块"。它只是一个由语句修饰符 while 所控制的 do BLOCK。 - hobbs

+1，第二种方法更清晰。close_container() 应该是一个单独的方法，这样它就可以在两个地方调用（即使没有其他原因）。 - j_random_hacker

Answer 3

似乎对于你所描述的问题来说有些过于复杂，但在理论上与Petri网接近。请查看维基百科上的Petri网（链接）。

可以在这里找到一个Perl实现（链接）。

希望这能帮到你，

Jerome Wagner

- Jerome WAGNER

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

- Michael Carman

---

你的实现与描述的不同复杂度。调用 part 将会使（实例化）两个数组，因此它将占用 O(N) 的内存。原始算法是 O(1)。 - Hynek -Pichi- Vychodil

Answer 5

在研究算法时，主流的计算机科学算法往往处理非常复杂的情况，或采用非常复杂的方法（例如查找NP-Complete）。此外，这些算法往往专注于优化。如何使系统更加高效？如何在生产计划中使用更少的步骤？我可以在我的酒吧里放置最多的饮料数量是多少？等等。

我认为复杂方法的一个例子是快速排序，因为递归非常巧妙。我知道这是标准的，但我真的很喜欢它。如果你喜欢算法，那么请看看Simplex Algorithm - 它非常有影响力。

复杂情况的一个例子是，如果你有橙子进去，被分成5堆橙子，然后去5个不同的地方削皮，然后都回来了，形成了另一条橙子路径，总共有10堆橙子，然后每个橙子都被单独切片，并以恰好2磅的重量装箱。

回到你的例子。你的例子是一个简化版的流网络。与其有许多侧面路径和选项，只有一条每次容量为一个橙子的路径。在流网络算法中，Ford-Fulkerson算法可能是最具影响力的。

因此，你可以将其中一个算法适用于所提出的例子，但需要通过简化过程。基本上这里没有足够的复杂性需要任何优化。而且没有运行低效时间复杂度的风险，因此不需要运行“完美的方法”。

你详细描述的方法在这里是可以的，上面接受的答案对定义的问题提出了实际的功能解决方案。我只是想加上我的两分钱关于算法方面的问题。

- Travis J