问题 在python中的数字列表中立即获得最小值


如何获得python中提供的值的下一个最小值?它有内置功能吗?

>>>num_list=[1,2,3,4]
>>> min(num_list)
1
>>> max(num_list)
4

如何找到下一个最低到3或下一个最大到2?预期结果为2和3。


870
2018-04-06 13:03


起源

列表是否排序? - Juan Lopes


答案:


TL; DR 或 min(n for n in my_list if n>lower_bound) 要么 max(n for n in my_list if n<upper_bound)


寻找更快的替代方案 即刻最低限度 或者 立即最大化 是 numpy

>>> import numpy as np
>>> np.random.seed(10)
>>> a = np.random.random(10000)
>>> a[a>0.7].min()
0.69999533217645671
>>> a[a<0.7].max()
0.70003449227846715

如果你不舒服使用 numpy 机械 并希望简单地处理一个列表

>>> a = list(a)

那你就可以用了 min 和 max 内置与发电机一起 表达式

>>> min(n for n in a if n>0.7)
0.69999533217645671
>>> max(n for n in a if n<0.7)
0.70003449227846715
>>>

当然,使用列表可以获得相同的结果,但要注意性能存在差异:使用 ipython 和 %timeit 为了获得时间,我使用了871μs numpy 和13.8毫秒使用常规列表的100000元素阵列/前面的例子列表。

HTH,ciao


后圣经

我的答案中的解决方案都是O(n),与使用排序的方法的O(n log n)进行比较 - 此外,对于大型数据集 numpy 途径 应该 (斜体,因为我手边没有测试...)受到一个小的乘法因子的影响。


4
2018-04-06 13:33



运用 min(n for n in a if n>m) 解决了我的问题。我可以将常规列表转换为键入 np.random.random() 如果列表不是由...生成的 np.random.seed(n)? - cutteeth
根据我的理解,你问的是“我有一个 定期 列表,并且,出于速度原因,我想使用 numpy'...但在我看来你并不熟悉 numpy 所以我的建议是“留在常规名单”。如果您想学习相当多的新东西,这里是配方: import numpy as np, my_list = list_computing_function(), my_array = np.array(my_list) 并最终 nearmin5 = my_array[my_array>5].min() 但请不要盲目地应用它,在您的上下文中它甚至可能比列表解决方案慢。 - gboffi
请你删除答案中的numpy部分吗?每当我收到有关SO的通知时,我都会检查这个答案。我认为最好删除numpy部分或将其移动到下面 min and max part 这是问题的恰当答案。谢谢 :) - cutteeth


我看到你的问题被标记为[下限]和[上限]。如果您的列表已排序,则Python具有等效的C ++ <algorithm> lower_bound 和 upper_bound。他们在 bisect 模块。它们返回开始的索引,并在某个特定值的范围结束后立即返回。

In [1]: import bisect

In [2]: A = [0, 1, 3, 3, 5]

In [3]: A[bisect.bisect_left(A, 3)-1]
Out[3]: 1

In [4]: A[bisect.bisect_right(A, 3)]
Out[4]: 5

3
2018-04-06 13:14



对于延迟回复很抱歉,但是我可以知道复杂性吗? - cutteeth
@cutteeth O(log n),但您的列表必须已经排序。 - Juan Lopes


下一个最低到3:

max([x for x in num_list if x < 3])

下一个最大的2:

min([x for x in num_list if x > 2])

2
2018-04-06 13:12



你在这里不需要列表推导,即只是 max(x for x in num_list if x < 3) 足够(而且效率更高)。 - Frerich Raabe


您可以使用 sorted :

>>> l=sorted(num_list,reverse=True)
>>> l[l.index(3)+1]
2

但是,正如Frerich Raabe在评论中所说的那样,你不需要痛苦的整个列表,你可以找到低于3的元素的最大值:

>>> max(i for i in num_list if i<3)
2

对于2岁以后的下一个最大的你可以使用 min :

>>> min(i for i in num_list if i>2)
3

1
2018-04-06 13:06



对整个列表进行排序是过度的。请注意,您只需查看输入列表的每个元素一次即可查找,例如最小元素小于3。这可以在线性时间内完成。 - Frerich Raabe
请注意,这也是错误的,因为您可能会得到一个IndexError - Shashank
@FrerichRaabe是的,OP的问题让我更加优雅!谢谢你的提醒! - Kasrâmvd
@Shashank我删除了发电机解决方案! - Kasrâmvd


使用 heapq.nlargest 和 heapq.nsmallest

import heapq

num_list = [1, 2, 3, 4]

heapq.nlargest(2, num_list)
heapq.nsmallest(2, num_list)
#>>> [4, 3]
#>>> [1, 2]

1
2018-04-06 17:17





提供的答案很好,但如果我可以提出建议 - 如果有时可以重复这些值,例如

num_list = [2, 2, 4, 4, 6, 7, 8, 9]

...等等,只是排序列表并获得第一个索引可能不是您正在寻找的。

通过它传递 set() 首先,您将确保每个条目都是单身:

def sorted_ordered_list(sequence):
    return sorted(list(set(sequence)))

然后你可以索引返回的 list 无论您要寻找的是哪个值,从0的最低值到最高值。

例:

>>> my_list = [1, 5, 4, 3, 6, 3, 8, 3, 6, 7, 4, 2, 6, 7, 9, 8, 8]
>>> sorted_ordered_list(my_list)
[1, 2, 3, 4, 5, 6, 7, 8, 9] # now index the list for the desired value
>>> 

0
2018-04-06 13:12



这是一种方式,但成本高昂。考虑到原始问题可以在线性时间和固定空间中解决。 - wsysuper
当然,但它是一个单线,使用没有内置,有点像OP要求


您可以使用以下方法:

num_list = [1,2,3,4]   
inds = sorted(range(len(num_list)), key=lambda k: num_list[k])

然后,inds [1]将包含下一个最低元素的索引,依此类推。 此外,您可以使用以下代码而不进行排序:

minv = min(num_list)    
nmin = min(nm for nm in num_list if nm > minv)
maxv = max(num_list)
nmax = max(nm for nm in num_list if nm < maxv)

0
2018-04-06 13:07



运用 sorted 太过分了,第二个提案是O(n ^ 2)。 - Frerich Raabe
你是对的,我纠正了我的回答。 - kvorobiev