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

Question

我的问题是 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函数有关？

Answer 1

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

• 禁用垃圾回收:

  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.