在列表理解中使用next

Question

我正在尝试做一些非常简单的事情，我可能已经把它复杂化了：

这就是问题所在：

假设你生活在一个受控制的经济体中，镇上有一个面包师，他每天烤一定数量的面包。镇上的人排队买一条面包（你只能买一条）

排队的人比能买到的面包还多。队列中的每个人都会收到一张他们在队列中的号码的罚单，以防止插队，但他们每天的顺序都是相同的（保持简单）。面包每天在不同的时间准备好，有些排队的人需要上班，如果面包在上班前还没有准备好，他们就离开队列，下一个排队的人代替他们。但他们仍然有他们原来的排队票。原始列表中的值是队列中的人员必须离开工作前的小时数

我想知道在面包师用完面包之前，每天给他的最后一张票上的号码是多少

我可以让我现有的代码为相对较少的人工作，但如果有数百万人，很多天（计划经济体计划未来5年），你就明白了

def BakerQueue(loaves, people, bake_time):
    got_some_bread = []
    for b in bake_time:
        counter = 0
        for p in range(len(people)):
            if people[p] >= b:
                counter += 1
                if counter == loaves:
                    got_some_bread.append(p + 1)
                    counter = 0
                    break
                elif p == len(people) - 1:
                    got_some_bread.append(0)
                    break
            elif counter < loaves and p == len(people) - 1:
                got_some_bread.append(0)
                counter = 0
    return got_some_bread

您可以使用它来运行代码：在本例中，列表中有3、18个人，一周中的每一天都有不同的烘焙时间，因此在第一天，票证1、2、3获得面包，在第二天，票证2、3、4获得面包，在第三天，票证7、9和15获得面包。我只关心每天谁得到最后一块面包，这就是函数返回的内容

BakerQueue(3, [1, 4, 4, 3, 1, 2, 6, 1, 9, 4, 4, 3, 1, 2, 6, 9, 4, 5, 8],[1, 2, 5, 4, 5, 4, 7])

这将如预期的那样返回

[3, 4, 15, 7, 15, 7, 19]

本质上，我希望对列表的索引级别进行优先级排序，并弹出任何大于另一个值的值

我有一个列表：my_list = [1, 4, 4, 3, 1, 2, 6]，我想保持它的索引优先级，所以我将索引和值都枚举到一个新列表中：

my_list_of_tuples = [(i, j) for i, j in enumerate(my_list)]

这给了我：[(0, 1), (1, 4), (2, 4), (3, 3), (4, 1), (5, 2), (6, 6)]

然后我将其转换为一个堆

heapq.heapify(my_list_of_tuples)

现在，我想检查堆顶部的值是否大于我要迭代的单独列表中的迭代常量。如果是，我想从堆中弹出它heapq.heappop(my_list_of_tuples)

我想这样做的代码如下，但它不起作用，所以可能不起作用，但我如何访问堆顶部的值，我想写这样的东西：

    counter = 0
    while counter <= static_constant:
        if next([v[1] for v in my_list_of_tuples]) < iterated_constant:
            heapq.heappop(my_list_of_tuples)
        else:
            counter += 1

希望能得到一些关于如何处理列表理解生成器的帮助。多谢各位

Answer 1

我想我理解你的问题

问题描述

给定：

• num_items-可用项目的数量
• targets-潜在目标的列表，每个目标都有一个值
• threshold-截止限值

任务：

• 选择targets的第一个num_items元素，其值大于或等于threshold
• 从targets（从1开始）返回最后选择的元素的数组索引，如果没有足够的目标可用，则返回0。（奇怪的决定，我会选择从0开始的索引，如果没有找到，则返回len(targets)，但很好）
• 优化速度targets和num_items每次都是相同的，threshold是唯一更改的值

---

范例

num_items = 3
targets = [5,3,4,1,3,3,7,4]
threshold = 4

选择的目标将是位于[0,2,6]位置的目标，其值为[5,4,7]，因为这些是高于或等于threshold的第一个3值。我们只搜索最后一个的索引，在本例中是6

---

接近

你最初的想法是迭代所有的人，如果阈值很低，速度会很快，但是如果阈值较高，速度会很慢，因为我们需要迭代所有的人，直到找到一个候选人

我重写了您最初的想法，对所有这些想法进行了迭代，因为我无法理解您的代码：

def choose_first_n(num_items, targets, threshold):
    for target_id, target in enumerate(targets):
        if target >= threshold:
            num_items -= 1
            if num_items == 0:
                return target_id + 1
    return 0

def baker_queue(num_loaves_per_day, people_max_waiting_time, required_baking_times):
    results = []
    for today_baking_time in required_baking_times:
        results.append(choose_first_n(num_loaves_per_day, people_max_waiting_time, today_baking_time))
    return results

print(baker_queue(3,
                  [1, 4, 4, 3, 1, 2, 6, 1, 9, 4, 4, 3, 1, 2, 6, 9, 4, 5, 8],
                  [1, 2, 5, 4, 5, 4, 7]))
# Returns: [3, 4, 15, 7, 15, 7, 19], as in the original code.
# Also, please provide expected return values in future, like I did here.

使用堆是一个有趣的想法，但我认为我们并没有从中受益。堆只有在项目移除/插入时才会非常快，而我们不会这样做。我们只是重复它们

我能想到的最快的方法是将threshold列表预处理为更有效的内容，就像创建最后一项的“索引”一样

演示： 我们使用前面的代码，并根据阈值查看结果：

def choose_first_n(num_items, targets, threshold):
    for target_id, target in enumerate(targets):
        if target >= threshold:
            num_items -= 1
            if num_items == 0:
                return target_id + 1
    return 0

targets = [1, 4, 4, 3, 1, 2, 6, 1, 9, 4, 4, 3, 1, 2, 6, 9, 4, 5, 8]
num_items = 3

for threshold in range (10):
    result = choose_first_n(num_items, targets, threshold)
    print(f"Threshold: {threshold}, Result: {result}")

Threshold: 0, Result: 3
Threshold: 1, Result: 3
Threshold: 2, Result: 4
Threshold: 3, Result: 4
Threshold: 4, Result: 7
Threshold: 5, Result: 15
Threshold: 6, Result: 15
Threshold: 7, Result: 19
Threshold: 8, Result: 19
Threshold: 9, Result: 0

您可以看到，如果阈值升高，结果也会升高。阈值与结果之间呈线性稳定增长关系

如果我们可以计算结果变化的值，我们可以通过分治搜索直接计算结果，这比遍历列表快得多。（O(logn)而不是O(n)，以防您熟悉大O符号）

这里需要注意的一点是，最后一个结果是0，它阻止了该方案。这就是为什么让索引从0开始而不是从1开始是有益的，并且让“error”案例是len(targets)而不是0

预处理

最困难的事情是获得映射的预处理

让我们从另一个角度来看

为了简单起见，假设num_items为3，我们有10个目标。 选定的目标是否在前5个目标范围内

答案是：是的，如果前5个目标中至少有3个高于或等于阈值。换句话说，排名第三的数字是决定因素。如果阈值高于第三大数字，则所选目标将不仅在前5个目标内

因此，对于所有项目，我们需要计算第三大数字。有趣的是，这实际上是堆派上用场的地方；）

实施

import heapq
import bisect

def preprocess(targets, num_items):
    # our heap, will contain the first num_items smallest targets
    largest_targets_heap = []

    # Our first preprocessing result, will contain the
    # third large number between the first item and the current item,
    # for every item.
    third_largest_number_per_target = []

    # Compute the third largest previous value for every target
    for target in targets:
        heapq.heappush(largest_targets_heap, target)
        if len(largest_targets_heap) > num_items:
            heapq.heappop(largest_targets_heap)

        current_third_largest = largest_targets_heap[0]
        third_largest_number_per_target.append(current_third_largest)

    # We now have the third largest number for every target.
    # Now, consolidate that data into a lookup table, to prevent duplication.
    # Therefore, find the first occurrence of every number
    lookup_table_indices = []
    lookup_table_values = []
    current_value = third_largest_number_per_target[num_items - 1]

    # Push the (num_items-1)th value to account for the fact our heap wasn't filled up until the
    # first num_items were processed
    lookup_table_indices.append(num_items - 1)
    lookup_table_values.append(current_value)

    # Fill the rest of the lookup table
    for index, value in enumerate(third_largest_number_per_target):
        if index < num_items - 1:
            continue
        if value != current_value:
            lookup_table_indices.append(index)
            lookup_table_values.append(value)
            current_value = value

    # The lookup table we have, consisting of values, indices, a minimum and a maximum value
    lookup_table = (lookup_table_values, lookup_table_indices, num_items, len(targets))

    return lookup_table

def choose_first_n_preprocessed(lookup_table, threshold):
    (lookup_table_values, lookup_table_indices, min_value, max_value) = lookup_table

    # We need to find the first (value,index) pair in lookup table where value is larger or equal to threshold
    # We do this by using bisect, which is really fast. This is only possible because of our preprocessing.
    position = bisect.bisect_left(lookup_table_values, threshold)

    # If we didn't find a result in the preprocessed table, we return the max value, to indicate that the
    # threshold ist too high.
    if position >= len(lookup_table_indices):
        return max_value

    # Read the result from the table of incides
    value = lookup_table_indices[position]
    return value

def baker_queue(num_loaves_per_day, people_max_waiting_time, required_baking_times):
    # Create the preprocessed lookup table
    lookup_table = preprocess(people_max_waiting_time, num_loaves_per_day)

    # For every day, compute the result
    results = []
    for today_baking_time in required_baking_times:
        # Use our fast lookup based algorithm now
        result = choose_first_n_preprocessed(lookup_table, today_baking_time)
        
        # Convert indices back to starting with 1, and 0 in error case, as
        # the original format was
        if result == len(people_max_waiting_time):
            results.append(0)
        else:
            results.append(result+1)
    return results

print(baker_queue(3,
                  [1, 4, 4, 3, 1, 2, 6, 1, 9, 4, 4, 3, 1, 2, 6, 9, 4, 5, 8],
                  [1, 2, 5, 4, 5, 4, 7]))
# [3, 4, 15, 7, 15, 7, 19]

理论分析

现在应该要快得多，特别是对很多天来说，对很多人来说也是如此

幼稚实现的复杂性令人担忧

O(days * people)

预处理实现的复杂性非常高

O(people * log(bread) + days * log(people))

这听起来没什么不同，但确实如此。它基本上说，如果限制因素是人，那么多少天无关紧要，如果限制因素是天，那么多少人无关紧要

基准测试结果

设置为：

• 每天900块面包
• 10,000人
• 10000天

结果:

• 天真：2.13秒
• 预处理：0.012秒

然后，我尝试将算法推到目前为止，它也需要2秒，并得到了这些数字：

• 每天90000个面包
• 一百万人
• 1000000天

我没有在naive算法上运行这些数字，但数学上说这需要大约2000000秒或23天

那花了一段时间，我希望这是值得的；）

我认为这是我迄今为止最大的一篇文章，这是一个非常有趣的任务

我希望你能感激

问候