在列表推导中使用 next
using next in a list comprehension
我正在尝试做一些非常简单的事情，但我可能过于复杂了：
这是问题所在：
假设您生活在一个受控制的经济体中，镇上有一位面包师，他每天都会烘烤一定数量的面包。镇上的人排队买一条面包（你只能买一条）。
排队的人比可用的面包多。队列中的每个人都会得到一张他们在队列中的号码的票，以防止插队，但他们每天的顺序都是一样的（保持简单）。面包每天在不同的时间准备好，队列中有些人需要上班，如果面包在他们必须离开之前没有准备好，他们就离开队列，让下一个排队的人代替他们.但是他们还有原来的排队票。原始列表中的值是队列中的人必须离开工作之前的小时数
我想知道面包师每天 运行 面包用完之前最后一张票的号码是多少。
我可以让我现有的代码为相对较少的人工作，但如果有数百万人，很多天（未来 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获得面包。我只关心谁每天吃到最后一条面包，这就是函数 returning.
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])
这将 return 符合预期
[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
希望得到一些关于如何处理列表理解生成器的帮助。谢谢
我想我明白你的问题了。
问题描述
给定：
num_items - 可用项目数targets - 潜在目标列表，每个都有一个值threshold - 截止限制
任务：
- 选择
targets的前num_items个元素，其值大于或等于threshold。
- Return 来自
targets（从 1 开始）的最后一个选择元素的数组索引，如果没有足够的目标可用，则为 0。 （奇怪的决定，如果找到 none，我会选择从 0 和 return 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]，因为它们是第一个 3 值，高于或等于 threshold.我们只搜索最后一个的索引，在本例中为 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.
使用堆是一个有趣的想法，但我认为我们不会以任何方式从中受益。堆只对项目 removal/insertion 非常快，我们不这样做。我们只是迭代它们。
我能想到的最快的方法是 pre-process 将 threshold 列表转换成更有效的东西，就好像创建最后一项的 'index' 一样。
示范：
我们使用我们之前的代码，根据阈值来看结果：
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
你可以看到，如果阈值上升，结果也会上升。阈值与结果呈线性递增关系
如果我们可以计算结果变化的值，我们可以直接通过 divide-and-conquer 搜索计算结果，这比遍历列表快很多。 （O(logn) 而不是 O(n)，以防您熟悉 Big-O 表示法）
这里要注意的一件事是最后的结果是 0，这使该方案失效。这就是为什么让索引以 0 而不是 1 开头并且 'error' 的情况是 len(targets) 而不是 0 是有益的原因。
预处理
最难的事情是进行映射的预处理。
让我们反过来看。
为简单起见，假设num_items为3，我们有10个目标。
所选目标是否在前5个目标内？
答案是：是的，如果前 5 个目标中至少有 3 个高于或等于阈值。或者换句话说，列表中的第三大数字是决定因素。如果阈值高于第 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 人
- 10,000 天
结果：
- 天真：2.13 秒
- 预处理：0.012 秒
然后我尝试将算法推到它也需要 2 秒的程度，并得到了这些数字：
- 每天 90,000 个面包
- 1,000,000 人
- 1,000,000 天
我没有 运行 天真的算法中的那些数字，但数学表明这将花费大约 2,000,000 秒或 23 天。
嗯，这花了一段时间，我希望这是值得的 ;)
我认为这是我最大的 post 然而，这是一项非常有趣的任务！
希望您能欣赏。
问候
我正在尝试做一些非常简单的事情，但我可能过于复杂了：
这是问题所在：
假设您生活在一个受控制的经济体中，镇上有一位面包师，他每天都会烘烤一定数量的面包。镇上的人排队买一条面包（你只能买一条）。
排队的人比可用的面包多。队列中的每个人都会得到一张他们在队列中的号码的票，以防止插队，但他们每天的顺序都是一样的（保持简单）。面包每天在不同的时间准备好，队列中有些人需要上班，如果面包在他们必须离开之前没有准备好，他们就离开队列，让下一个排队的人代替他们.但是他们还有原来的排队票。原始列表中的值是队列中的人必须离开工作之前的小时数
我想知道面包师每天 运行 面包用完之前最后一张票的号码是多少。
我可以让我现有的代码为相对较少的人工作，但如果有数百万人，很多天（未来 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获得面包。我只关心谁每天吃到最后一条面包，这就是函数 returning.
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])
这将 return 符合预期
[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
希望得到一些关于如何处理列表理解生成器的帮助。谢谢
我想我明白你的问题了。
问题描述
给定：
num_items- 可用项目数targets- 潜在目标列表，每个都有一个值threshold- 截止限制
任务：
- 选择
targets的前num_items个元素，其值大于或等于threshold。 - Return 来自
targets（从1开始）的最后一个选择元素的数组索引，如果没有足够的目标可用，则为0。 （奇怪的决定，如果找到 none，我会选择从0和 returnlen(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]，因为它们是第一个 3 值，高于或等于 threshold.我们只搜索最后一个的索引，在本例中为 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.
使用堆是一个有趣的想法，但我认为我们不会以任何方式从中受益。堆只对项目 removal/insertion 非常快，我们不这样做。我们只是迭代它们。
我能想到的最快的方法是 pre-process 将 threshold 列表转换成更有效的东西，就好像创建最后一项的 'index' 一样。
示范： 我们使用我们之前的代码，根据阈值来看结果：
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
你可以看到，如果阈值上升，结果也会上升。阈值与结果呈线性递增关系
如果我们可以计算结果变化的值，我们可以直接通过 divide-and-conquer 搜索计算结果，这比遍历列表快很多。 （O(logn) 而不是 O(n)，以防您熟悉 Big-O 表示法）
这里要注意的一件事是最后的结果是 0，这使该方案失效。这就是为什么让索引以 0 而不是 1 开头并且 'error' 的情况是 len(targets) 而不是 0 是有益的原因。
预处理
最难的事情是进行映射的预处理。
让我们反过来看。
为简单起见，假设num_items为3，我们有10个目标。 所选目标是否在前5个目标内？
答案是：是的，如果前 5 个目标中至少有 3 个高于或等于阈值。或者换句话说，列表中的第三大数字是决定因素。如果阈值高于第 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 人
- 10,000 天
结果：
- 天真：2.13 秒
- 预处理：0.012 秒
然后我尝试将算法推到它也需要 2 秒的程度，并得到了这些数字：
- 每天 90,000 个面包
- 1,000,000 人
- 1,000,000 天
我没有 运行 天真的算法中的那些数字，但数学表明这将花费大约 2,000,000 秒或 23 天。
嗯，这花了一段时间，我希望这是值得的 ;)
我认为这是我最大的 post 然而，这是一项非常有趣的任务！
希望您能欣赏。
问候