对于所有>0的元素，从整数数组中等量递减

Question

有x个配送中心，每个配送中心都有y个产品。每天只有相同数量的数量从所有的x分销中心剩余的产品可以发运。计算出所有产品需要多长时间才能发货，因此，对于一个数组[3, 2, 6]，它将运行：

• 3，2，6
• 1，04
• 0 0，3
• 0 0 0

== 3天后装运。

下面是我对Python算法的尝试。

import functools

def get_min_days(dist_centers):
    
    total_inventory = functools.reduce(lambda a,b: a+b, dist_centers)
    days = 0
    while total_inventory > 0:

        tmp = []
        # some number bigger than any inventory expected
        minimum_inventory = float('inf')

        for dist_center in dist_centers:
            if dist_center > 0 and dist_center < minimum_inventory:
                minimum_inventory = dist_center
    
        for dist_center in dist_centers:
            if dist_center > 0:
                tmp.append(dist_center - minimum_inventory)
            else:
                tmp.append(0)
        
        dist_centers = tmp
        total_inventory = functools.reduce(lambda a,b: a+b, dist_centers)
        days += 1
    
    print("days is ",days)

get_min_days([1,2,3])
get_min_days([2,3])
get_min_days([5,10,15])
get_min_days([5,3,15])

Answer 1

最终的结果是莱因德林是正确的，并且有一个更有效的算法来找出天数。但在此期间，在您的方法中应该注意以下几个项目：

• Python没有那么多内建函数。最好能回顾一下这些。第一个跳到我身上的是：
• functools.reduce(lambda a,b: a+b, dist_centers)应该变成sum(dist_centers) (我们可以删除import)。
• 还有一个min函数。不过，min(dist_centers)不能很好地工作，因为它将获得0项。我们可以使用两种方法：(1)在取min之前过滤掉0项，或者(2)在查找min时忽略0项。我将从(2)开始，稍后再讨论(1)。(2)可由：min( d for d in dist_centers if d>0 )完成。
• 我刚才使用的min代码涉及一个“生成器表达式”。还有"list“、"dict”和"set“表达式。一般的想法是，与其创建一个空的东西，然后一次填充一个东西，你可以同时创建和填充这个东西。例如，我们可以使用列表表达式：tmp重新创建dist_centers，而不是使用[ d-minimum_inventory if d>minimum_inventory else 0 for d in dist_centers ]。您可以相当快地读取表达式，它们将真正简化您的代码。
• 非零值被认为是真，所以我们在比较中不需要thing>0，只需要使用thing。
• 除了检查是否应该继续循环之外，我们实际上并不使用total_inventory。但要知道我们是否应该继续循环，唯一需要弄清楚的是，是否有任何一个中心仍有产品可供运输。事实证明，Python为这种情况提供了一个内置的any函数(因为我们只需要一个非零的值，我们就可以说是any(dist_centers))。现在我们不再需要total_inventory变量了。
• 莱因德林提到不打印内的功能。一般的想法是，函数应该集中精力做一件事情，那就是找出天数。这样，如果您想用天数来做其他事情，您可以这样做，而不需要重写函数。(说到打印，print("days is ",days)在" is“和days之间有两个空格，这可能不是有意的。)
• 我增加了一个__name__=='__main__'警卫。一次过的脚本并不是真正必要的，但是对于一般的编程来说，这可以让您知道是将脚本导入到更大的程序中，还是仅仅使用脚本本身。
• 类型提示可以很好地添加到代码中，不会有太大的麻烦，所以让我们将它们添加进来。

这使您的方法看起来如下：

def get_min_days(dist_centers:list[int]) -> int:
    days:int = 0
    while any(dist_centers):
        minimum_inventory = min( d for d in dist_centers if d )
        dist_centers = [ d-minimum_inventory if d>minimum_inventory else 0 for d in dist_centers ]
        days += 1
    return days

if ( __name__ == '__main__' ):
    print("days is",get_min_days([1,2,3]))
    print("days is",get_min_days([2,3]))
    print("days is",get_min_days([5,10,15]))
    print("days is",get_min_days([5,3,15]))

我在前面提到过当0值发生时过滤掉它们的想法。使用非空列表也是Truthy的想法，这让我们拥有：

    while dist_centers:
        minimum_inventory = min(dist_centers)
        dist_centers = [ d-minimum_inventory for d in dist_centers if d>minimum_inventory ]

唯一的危险是，如果一个中心开始生产0产品，那么在这些产品被过滤掉之前，第一天就会失去生产0的机会。如果这是可能的话，那么我们应该从dist_centers=filter(None,dist_centers)开始。这种方法最大的缺点是，我们不能再跟踪一个特定的中心每天产生多少，因为我们不断地改变哪个中心与哪个索引。

我们已经得到了一个7行函数，运行时在分配中心的数量上是二次的。但是，通过以不同的方式思考事物，您可以找到一个具有线性运行时的1行函数。因此，一个可能的答案是“你应该删除所有的东西，写上这一行”。另一方面，我的大部分项目将适用于您所写的任何脚本，所以仍然值得一读(在我看来)。