Skip to main content
 首页 » 编程设计

python之在 Python3 的一行中输入所有数字的最快方法

2024年10月25日11虾米姐

我的问题是 SPOJ 问题的“超出时间限制”错误。我认为这个错误是因为输入量大,所以我需要你的帮助来找到处理大输入量的最佳方法。

让我解释一下输入和我的代码。

Input

The first line of the input contains test cases t(1<=t<=100). It is followed by 2*t lines, 2 for each test case. The first line of input for each test case contains a number n (0<=n<=10^6), followed by n elements in the next line. Each number is from -10^3 to +10^3

这里是输入的例子

3 #number of test cases (t) 
 
4 #number of elements that will come to next line (n) (this can be 10^6) 
 
2 1 2 2 #this line may have 10^6 numbers 
 
6  
 
1 1 1 2 2 2 
 
5 
 
1 2 4 5 1 

问题是询问一个数字是否出现超过 n//2 次。 示例输出

YES 2  #because 2 appears 3 times. 
 
NO     # no number occurs more than n//2 times 
 
NO     # no number occurs more than n//2 times. 

关于问题的更多信息

Added by: Troika::Bytes Date: 2010-02-18 Time limit: 1s Source limit: 50000B Memory limit: 256MB Cluster: Pyramid (Intel Pentium III 733 MHz) Languages: All except: PERL 6

http://www.spoj.com/problems/MAJOR/

最后是我的代码。

from collections import Counter 
import re 
 
def major(n): 
    s = input().split() # get all the numbers one by one 
    y = (Counter(s)).most_common()[0]  # Count how many times a number occurs in the input and return the most occurence with its value in a pair. 
    if y[1]> n//2: #if the most occurence is more than half of the "n" 
        return "YES " + y[0] # return the value belongs to the most occurence 
    else: 
        return "NO" 
 
for i in range(int(input())): #get the number of test cases 
    print(major(int(input()))) # calling the function to get the "n" 

在想知道 s = input().split() 对于像一百万个数字来说可能太慢了。 但是,我再次收到“超出时间限制”的错误。会不会跟Counter函数有关?

请您参考如下方法:

您可以通过以下方式对其进行优化:

  • 禁用垃圾回收:

    import gc 
    gc.disable() 
    
  • 避免使用 string.split 并使用 re.finditer。

  • 避免使用 range 并使用 while 循环。

  • 使用 sys.stdin.readline() 代替 input(速度更快)和 sys.stdout.write intead打印量。

  • 当数字的出现次数大于 n//2 时停止(另外,只计算一次)。您可以使用 collections.defaultdict 并在更新前检查出现的次数。

  • 避免使用函数,将所有内容放在一个循环中。

  • 有时在 main 函数中导入库可以节省时间。

不幸的是Martijn Pieters注意,Python 3.x 没有公认的解决方案而且只有一个 Python 2.x ,并且根据解决它所花费的内存量,numerix 可以使用 psyco(PyPy 所基于的库,比 CPython 快得多)。不幸的是,由于 psyco 已经停止,它的支持已经在集群上被删除,问题被执行,所以可能没有人会设法发送接受的解决方案,直到他们重新启用 psyco 或 PyPy 支持。

例子

import gc 
gc.disable() 
 
# import psyco 
# psyco.full() 
 
def main(): 
    from collections import defaultdict 
    from sys import stdin, stdout 
    import re 
 
    pattern = re.compile(r'\d+') 
    times = int(stdin.readline()) 
 
    while times: 
        times -= 1 
        threshold = int(stdin.readline()) // 2 
        vals = defaultdict(int) 
        for x in pattern.finditer(stdin.readline()): 
            n = int(x.group(0)) 
            rep = vals[n] + 1 
            if rep > threshold: 
                stdout.write('YES ' + str(n) + '\n') 
                break 
            else: 
                vals[n] = rep 
        else: 
            stdout.write('NO\n') 
 
if __name__ == '__main__': 
    main() 

编辑

我给 numerix 发了一封电子邮件,他确认他的解决方案使用了 psyco:

Yes, my solution for MAJOR uses psyco. I didn't try without psyco, but as there is no other AC Python solution I guess it won't be possible or only with heavy i/o optimization.