从包含100,000个整数的列表中检索两个最高项

Question

如何从包含100,000个整数的列表中检索两个最高项,而不必先排序整个列表？

Answer 1

在Python中,使用heapq.nlargest.如果您想要处理的不仅仅是前两个元素,这是最灵活的方法.

这是一个例子.

>>> import heapq
>>> import random
>>> x = range(100000)
>>> random.shuffle(x)
>>> heapq.nlargest(2, x)
[99999, 99998]

文档:http: //docs.python.org/library/heapq.html#heapq.nlargest

Answer 2

JacobM的答案绝对是可行的方法.但是,在实现他描述的内容时,需要记住一些事项.这里有一个小小的家庭教程,指导您解决这个问题的棘手部分.

如果此代码仅供生产使用,请使用列出的更有效/简洁的答案之一.这个答案针对的是编程新手.

这个想法

这个想法很简单.

• 保留两个变量:largest和second_largest.
• 浏览列表.
  • 如果项目大于largest,则将其分配给largest.
  • 如果项目大于second_largest但小于largest,则将其分配给second_largest.

入门

开始吧.

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    for item in inlist:
        if item > largest:
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [3, 2, 1]
    print two_largest(inlist)

好的,我们现在将JacobM的答案作为Python函数.当我们尝试运行它时会发生什么？

Traceback (most recent call last):
  File "twol.py", line 10, in <module>
    print two_largest(inlist)
  File "twol.py", line 3, in two_largest
    if item > largest:
UnboundLocalError: local variable 'largest' referenced before assignment

显然,我们需要largest在开始循环之前设置.这可能意味着我们也应该second_largest这样做.

初始化变量

让我们设置largest和second_largest为0.

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    largest = 0 # NEW!
    second_largest = 0 # NEW!
    for item in inlist:
        if item > largest:
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [3, 2, 1]
    print two_largest(inlist)

好.我们来吧吧.

(3, 2)

大!现在,让我们用测试inlist是[1, 2, 3]

    inlist = [1, 2, 3] # CHANGED!

我们来试试吧.

(3, 0)

......哦,哦.

修复逻辑

最大值(3)似乎是正确的.但第二大值完全错误.这是怎么回事？

让我们来看看函数正在做什么.

• 当我们开始时,largest是0并且second_largest也是0.
• 我们看到的列表中的第一项是1,因此largest变为1.
• 下一项是2,所以largest变为2.

但那怎么样second_largest？

当我们为其分配新值时largest,最大值实际上变为第二大值.我们需要在代码中显示.

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    largest = 0
    second_largest = 0
    for item in inlist:
        if item > largest:
            second_largest = largest # NEW!
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [1, 2, 3]
    print two_largest(inlist)

我们来吧吧.

(3, 2)

太棒了.

初始化变量,第2部分

现在让我们尝试一下负数列表.

    inlist = [-1, -2, -3] # CHANGED!

我们来吧吧.

(0, 0)

这根本不对.这些零来自哪里？

事实证明,起点值largest和second_largest实际上比列表中的所有项目大.您可能会考虑的第一件事是在Python中设置largest和second_largest尽可能低的值.不幸的是,Python没有尽可能小的价值.这意味着,即使您将它们都设置为-1,000,000,000,000,000,000,您也可以拥有一个小于该值的列表.

那么最好的做法是什么？让我们尝试设置largest和second_largest在列表中的第一项,第二项.然后,为了避免重复计算列表中的任何项目,我们只在第二项之后查看列表中的部分.

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    largest = inlist[0] # CHANGED!
    second_largest = inlist[1] # CHANGED!
    # Only look at the part of inlist starting with item 2
    for item in inlist[2:]: # CHANGED!
        if item > largest:
            second_largest = largest
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [-1, -2, -3]
    print two_largest(inlist)

我们来吧吧.

(-1, -2)

大!让我们尝试另一个负数列表.

    inlist = [-3, -2, -1] # CHANGED!

我们来吧吧.

(-1, -3)

等等,什么？

初始化变量,第3部分

让我们再次逐步完善我们的逻辑.

• largest 设置为-3
• second_largest 设置为-2

在那儿等一下 这似乎是错的.-2大于-3.这是什么原因造成的？我们继续吧.

• largest设置为-1; second_largest设置为旧值largest,即-3

是的,这看起来是个问题.我们需要确保largest并second_largest正确设置.

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    if inlist[0] > inlist[1]: # NEW
        largest = inlist[0]
        second_largest = inlist[1]
    else: # NEW
        largest = inlist[1] # NEW
        second_largest = inlist[0] # NEW
    # Only look at the part of inlist starting with item 2
    for item in inlist[2:]:
        if item > largest:
            second_largest = largest
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [-3, -2, -1]
    print two_largest(inlist)

我们来吧吧.

(-1, -2)

优秀.

结论

所以这里是代码,很好地评论和格式化.它也有我可以找到的所有错误.请享用.

但是,假设这确实是一个家庭作业问题,我希望你从看到一段不完美的代码慢慢改进中获得一些有用的经验.我希望其中一些技术在将来的编程任务中有用.

效率

不是很有效率.但是对于大多数用途,它应该没问题:在我的计算机(Core 2 Duo)上,可以在0.27秒内处理10万个项目的列表(使用timeit,平均超过100次运行).

Answer 3

您遍历列表,维护包含到目前为止遇到的最高和第二高项的值的变量.遇到的每个新项目将替换新项目高于(如果有)的两个中的任何一项.

Answer 4

一个非常光滑的方式是使用heapq. 修改数组(O(n)),然后弹出你需要的许多元素(log(n)).(在一次采访中看到这个问题,要记住这个问题.)